Yeni Babilonun Platformaları

Kostya, xəritədən istifadə edərək nəhayət yeni Babilə çatdı.

Şəhərin mərkəzində o, n platforma tapdı.

Yeni Babilin süqutu haqqında əfsanəni araşdırmaq üçün onları tədqiq etməlidir.

i-ci platformanın hündürlüyü - h[i].Platformalar arasında hərəkət etmək mümkündür, əgər (1 ≤ i, j ≤ n):

1. i və j platformaları eyni hündürlükdədir.

2. i və j platformaları qonşudur (yəni |i-j| = 1) və |h[i]-h[j]| ≤ d

Kostya q tipli i j suallarını verdi - i platformasından j platformasına keçmək mümkündürmü?

Giriş məlumatları:

Birinci sətirdə n, q və d ədədləri yazılıb. (1 ≤ n, q ≤ 2*10^5)Növbəti sətirdə n ədəd - h massivi (1 ≤ h[i] ≤ 3*10^6)Növbəti q sətirdə suallar yazılıb.

Çıxış məlumatları:

Suallara cavab verin.

Nümunələr