A14423 | Jumping Around

There is an infinite pond that can be represented with a number line. There are $n$ rocks in the pond, numbered from $1$ to $n$ . The $i$ -th rock is located at an integer coordinate $a_i$ . The coordinates of the rocks are pairwise distinct. The rocks are numbered in the increasing order of the coordinate, so $a_1 < a_2 < \dots < a_n$ .

A robot frog sits on the rock number $s$ . The frog is programmable. It has a base jumping distance parameter $d$ . There also is a setting for the jumping distance range. If the jumping distance range is set to some integer $k$ , then the frog can jump from some rock to any rock at a distance from $d - k$ to $d + k$ inclusive in any direction. The distance between two rocks is an absolute difference between their coordinates.

You are assigned a task to implement a feature for the frog. Given two integers $i$ and $k$ determine if the frog can reach a rock number $i$ from a rock number $s$ performing a sequence of jumps with the jumping distance range set to $k$ . The sequence can be arbitrarily long or empty.

You will be given $q$ testcases for that feature, the $j$ -th testcase consists of two integers $i$ and $k$ . Print "Yes" if the $i$ -th rock is reachable and "No" otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes", "Yes" and 'YES"' will be recognized as a positive answer).

The first line contains four integers $n$ , $q$ , $s$ and $d$ ( $1 \le n, q \le 2 \cdot 10^5$ ; $1 \le s \le n$ ; $1 \le d \le 10^6$ ) — the number of rocks, the number of testcases, the starting rock and the base jumping distance parameter.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^6$ ) — the coordinates of the rocks. The coordinates of the rocks are pairwise distinct. The rocks are numbered in the increasing order of distance from the land, so $a_1 < a_2 < \dots < a_n$ .

Each of the next $q$ lines contains two integers $i$ and $k$ ( $1 \le i \le n$ ; $1 \le k \le 10^6$ ) — the parameters to the testcase.

For each of the testcases print an answer. If there is a sequence of jumps from a rock number $s$ to a rock number $i$ with the jumping distance range set to $k$ , then print "Yes". Otherwise, print "No".