分数: 333 分
问题陈述
高桥在市政府道路管理科工作。其管辖范围内的路面包括 N 瓷砖排列成行,编号瓷砖 1, 2, \ldots, N 从左到右。
其中, M 瓷砖损坏。损坏瓷砖的数量为 B_1, B_2, \ldots, B_M,所有这些都是不同的(不一定按升序排列)。
有一天, K 汽车沿着这条路行驶。的 i第车(1 \leq i \leq K) 在tile的连续部分中精确地传递每个tile一次 L_i 平铺 R_i (L_i \leq R_i)。每辆汽车的行驶不会影响其他汽车的行驶,并且当汽车经过时,瓷砖不会改变其状态。
每次汽车经过一块损坏的瓷砖时,都会发生一次震动。即,所产生的冲击总数 i第辆车的行程等于瓷砖部分中包含的损坏瓷砖的数量 L_i 平铺 R_i.
对于每辆车,Takahashi 计算其行驶过程中产生的震动总数,并且是否至少达到阈值 T,他报告汽车的行驶部分“需要修理”。在这里, T 作为正整数给出。
对于每个 K 汽车,确定其行驶部分是否报告为需要维修。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq N
- 1 \leq K \leq 2 \times 10^5
- 1 \leq T \leq N
- 1 \leq B_i \leq N (1 \leq i \leq M)
- 全部 B_i 是不同的
- 1 \leq L_i \leq R_i \leq N (1 \leq i \leq K)
- 所有输入值均为整数
输入
N M K T B_1 B_2 \ldots B_M L_1 R_1 L_2 R_2 \vdots L_K R_K
- 第一行包含瓷砖总数 N,损坏的瓷砖数量 M,汽车数量 K,以及冲击计数阈值 T,用空格分隔。
- 第二行包含损坏瓷砖的数量 B_1, B_2, \ldots, B_M,用空格分隔。它们不一定按升序排列。
- 以下 K 行给出了每辆车的行驶路段。
- 的 (2 + i)第行包含左端点 L_i 和右端点 R_i 的 i第辆车的行驶部分,以空格分隔。
输出
输出 K 行。上 i第行,打印 YES 如果 i第辆车的行驶部分报告需要维修,并且 NO 否则。
示例输入 1
10 3 3 2 2 5 8 1 6 3 4 4 9
示例输出 1
YES NO YES
示例输入 2
5 1 3 2 3 1 2 3 3 1 5
示例输出 2
NO NO NO
示例输入 3
20 6 8 3 3 7 10 12 15 18 1 20 1 5 5 15 10 18 1 2 14 16 6 13 11 14
示例输出 3
YES NO YES YES NO NO YES NO
示例输入 4
50 10 12 4 31 5 44 17 28 12 49 36 23 40 1 50 1 10 10 30 20 45 1 4 5 5 30 50 15 25 35 50 1 28 43 46 25 42
示例输出 4
YES NO YES YES NO NO YES NO YES YES NO YES
示例输入 5
1 1 1 1 1 1 1
示例输出 5
YES