Platforms of the New Babylon
Kostya has finally arrived at the new Babylon, guided by his map.
In the heart of the city, he discovers n platforms.
To unravel the mystery of the fall of the new Babylon, he must explore these platforms.
The height of the i-th platform is denoted as h[i]. You can move between platforms if the following conditions are met (1 ≤ i, j ≤ n):
Platforms i and j have the same height.
Platforms i and j are adjacent (i.e., |i-j| = 1) and the height difference |
h[i]-h[j]| is less than or equal to d.
Kostya has q questions of the form i j - is it possible to reach platform i from platform j?
Input
The first line contains the integers n, q, and d. (1 ≤ n, q ≤ 2*10^5)The second line contains n integers representing the array h (1 ≤ h[i] ≤ 3*10^6).The next q lines contain the questions.
Output
Provide the answers to the questions.