有一个无限的池塘,可以用数轴表示。池塘里有 $$$n$$$ 块岩石,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 块岩石位于整数坐标 $$$a_i$$$ 处。岩石的坐标是两两不同的。岩石按坐标递增顺序编号,因此 $$$a_1 < a_2 < \dots < a_n$$$。
一只机器青蛙坐在编号 $$$s$$$ 的岩石上。青蛙是可编程的。它有一个基本跳跃距离参数$$$d$$$。还有跳跃距离范围的设置。如果跳跃距离范围设置为某个整数$$$k$$$,那么青蛙可以在任何方向上从某个岩石跳到$$$d - k$$$到$$$d + k$$$(包括$$$d - k$$$)之间的任何岩石。两块岩石之间的距离是它们坐标之间的绝对差。
您被分配了一项任务来实现青蛙的功能。给定两个整数 $$$i$$$ 和 $$$k$$$ 确定青蛙是否可以从编号为 $$$s$$$ 的岩石上到达编号为 $$$i$$$ 的岩石,执行一系列跳跃,跳跃距离范围设置为 $$$k$$$。该序列可以任意长或为空。
您将获得该功能的 $$$q$$$ 测试用例,第 $$$j$$$ 个测试用例由两个整数 $$$i$$$ 和 $$$k$$$ 组成。如果可以到达第 $$$i$$$ 块岩石,则打印“是”,否则打印“否”。
在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。
输入
第一行包含四个整数 $$$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 < a_2 < \dots < a_n$$$。
接下来的 $$$q$$$ 行包含两个整数 $$$i$$$ 和 $$$k$$$ ($$$1 \le i \le n$$$; $$$1 \le k \le 10^6$$$) - 测试用例的参数。
输出
为每个测试用例打印一个答案。如果存在从岩石编号 $$$s$$$ 到岩石编号 $$$i$$$ 的跳跃序列,且跳跃距离范围设置为 $$$k$$$,则打印“Yes”。否则,打印“否”。
示例
输入 #1
7 4 4 5 1 5 10 13 20 22 28 4 1 7 2 7 3 3 2
输出 #1
Yes No Yes Yes
输入 #2
10 8 6 11 1 2 4 7 8 9 11 13 19 20 2 13 5 8 8 1 6 15 1 15 2 7 7 6 8 9
输出 #2
Yes Yes No Yes Yes Yes Yes Yes
输入 #3
6 9 6 6 1 2 4 9 18 19 2 17 1 18 5 4 2 11 5 17 6 8 4 3 3 3 6 6
输出 #3
Yes Yes Yes Yes Yes Yes No No Yes
输入#4
4 1 1 10 1 8 10 19 2 1
输出#4
Yes
注意
第一个例子的解释:
在第一个测试用例中,目标岩石与起始岩石相同,因此不需要跳跃即可到达它。
在第二个测试用例中,青蛙可以跳跃 $$$[5 - 2; 范围内的任意距离; 5 + 2]$$$。因此,它可以到达岩石编号$$$5$$$(通过向右跳跃$$$7$$$)和岩石编号$$$3$$$(通过向左跳跃$$$3$$$)。从编号 $$$3$$$ 的岩石可以到达编号 $$$2$$$ 的岩石(通过向左跳跃 $$$5$$$)。从编号为$$$2$$$的岩石可以到达编号为$$$1$$$的岩石(通过向左跳跃$$$4$$$)。然而,没有办法达到岩石编号$$$7$$$。
在第三个测试用例中,青蛙可以跳跃 $$$[5 - 3; 范围内的任意距离; 5 + 3]$$$。因此,它可以通过先跳到岩石 $$$5$$$ 然后再跳到 $$$7$$$ 来到达岩石编号 $$$7$$$。
第四个测试用例显示在第二个测试用例的说明中。