CF1550F.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 \lt a_2 \lt \dots \lt 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).

存在一个可以用数轴表示的无限池塘。池塘中有 $n$ 块石头，编号从 $1$ 到 $n$。第 $i$ 块石头位于整数坐标 $a_i$ 处。所有石头的坐标两两不同，且石头按坐标递增顺序编号，即满足 $a_1 \lt a_2 \lt \dots \lt a_n$。

一只机器人青蛙坐在编号为 $s$ 的石头上。该青蛙是可编程的，它具有一个基础跳跃距离参数 $d$。此外，还有一个跳跃距离范围设置：若将跳跃距离范围设为某个整数 $k$，则青蛙可以从某块石头向任意方向跳跃至另一块石头，只要两块石头之间的距离（即其坐标之差的绝对值）在区间 $[d - k,\, d + k]$ 内（含端点）。

你需要为该青蛙实现一项功能：给定两个整数 $i$ 和 $k$，判断青蛙能否从编号为 $s$ 的石头出发，在跳跃距离范围设为 $k$ 的前提下，经过若干次（可以为零次或任意多次）跳跃到达编号为 $i$ 的石头。

你将收到 $q$ 组测试用例，其中第 $j$ 个测试用例包含两个整数 $i$ 和 $k$。若编号为 $i$ 的石头可达，则输出 "Yes"；否则输出 "No"。

你可以以任意大小写形式输出 "YES" 和 "NO"（例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均会被识别为肯定回答）。

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 \lt a_2 \lt \dots \lt 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.

第一行包含四个整数 $n$、$q$、$s$ 和 $d$（$1 \le n, q \le 2 \cdot 10^5$；$1 \le s \le n$；$1 \le d \le 10^6$）——分别表示岩石数量、测试用例数量、起始岩石编号以及基础跳跃距离参数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）——表示各岩石的坐标。所有岩石坐标两两不同，且岩石按其到岸边的距离递增顺序编号，即满足 $a_1 \lt a_2 \lt \dots \lt a_n$。

接下来的 $q$ 行中，每行包含两个整数 $i$ 和 $k$（$1 \le i \le n$；$1 \le k \le 10^6$）——表示该测试用例的参数。

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".

对每个测试用例输出一个答案。如果存在一条从编号为 $s$ 的岩石跳到编号为 $i$ 的岩石的跳跃序列，且跳跃距离范围设定为 $k$，则输出“Yes”；否则输出“No”。

Explanation of the first example:

In the first testcase the destination rock is the same as the starting rock, thus no jumps are required to reach it.

In the second testcase the frog can jump any distance in the range $[5 - 2; 5 + 2]$. Thus, it can reach rock number $5$ (by jumping $7$ to the right) and rock number $3$ (by jumping $3$ to the left). From rock number $3$ it can reach rock number $2$ (by jumping $5$ to the left). From rock number $2$ it can reach rock number $1$ (by jumping $4$ to the left). However, there is no way to reach rock number $7$.

In the third testcase the frog can jump any distance in the range $[5 - 3; 5 + 3]$. Thus, it can reach rock number $7$ by jumping to rock $5$ first and to $7$ afterwards.

The fourth testcase is shown in the explanation for the second testcase.

第一个样例的解释：

在第一个测试用例中，目标石头与起始石头相同，因此无需跳跃即可到达。

在第二个测试用例中，青蛙可跳跃的距离范围为 $[5 - 2; 5 + 2]$。因此，它可以到达编号为 $5$ 的石头（向右跳 $7$ 单位）以及编号为 $3$ 的石头（向左跳 $3$ 单位）。从编号为 $3$ 的石头出发，它可以到达编号为 $2$ 的石头（向左跳 $5$ 单位）；再从编号为 $2$ 的石头出发，它可以到达编号为 $1$ 的石头（向左跳 $4$ 单位）。然而，不存在任何方式能到达编号为 $7$ 的石头。

在第三个测试用例中，青蛙可跳跃的距离范围为 $[5 - 3; 5 + 3]$。因此，它可先跳至编号为 $5$ 的石头，再跳至编号为 $7$ 的石头，从而到达目标。

第四个测试用例的说明同第二个测试用例。