Костя, використовуючи карту, нарешті добрався до нового Вавилону.

У центрі міста він знайшов n платформ.

Для дослыдження легенди про падіння нового Вавилону йому потрібно дослідити їх.

Висота і-ної платформи - hi. Між платформами можна переміщатися, якщо(**1 ≤ i, j ≤ n**):

1. Платформи і та j однакові по висоті.
2. Платформи і та j сусідніі(тобто |i-j| = 1) і |hi-hj| d

Костя задав q запитань типу i j - чи можна добратися з платформи і до j?

Вхідні данні:

У першому рядку записано числа n, q та d.(1 ≤ n,q ≤ 2*105) У наступному рядку знаходяться n чисел - масив h (1 ≤ ai ≤ 3*106) У наступних q рядках записані запитання.

Вихідні данні:

Відповідь на запитання.