C - 道路の穴ぼこ調査 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 333 点

問題文

高橋君は市役所の道路管理課で働いています。管轄する道路の路面は N 枚のタイルが一列に並んで構成されており、左から順にタイル 1, 2, \ldots, N と番号がついています。

このうち M 枚のタイルは損傷しています。損傷したタイルの番号は B_1, B_2, \ldots, B_M で、これらはすべて異なります（昇順とは限りません）。

ある日、K 台の車がこの道路を通行しました。i 番目の車（1 \leq i \leq K）はタイル L_i からタイル R_i まで（L_i \leq R_i）の連続する区間に含まれるすべてのタイルをちょうど 1 回ずつ通過します。各車の通行は他の車の通行に影響を与えず、また車が通過してもタイルの状態は変化しません。

車が損傷したタイルを 1 枚通過するごとに衝撃が 1 回発生します。すなわち、i 番目の車の通行で発生する衝撃の合計回数は、タイル L_i からタイル R_i までの区間に含まれる損傷したタイルの枚数に等しくなります。

高橋君は、各車について通行で発生した衝撃の合計回数を求め、それが閾値 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
  • 1 行目には、タイルの総枚数 N 、損傷したタイルの枚数 M 、車の台数 K 、衝撃回数の閾値 T がスペース区切りで与えられる。
  • 2 行目には、損傷したタイルの番号 B_1, B_2, \ldots, B_M がスペース区切りで与えられる。昇順とは限らない。
  • 3 行目から K 行にわたって、各車の通行区間が与えられる。
  • 2 + i 行目には、i 番目の車の通行区間の左端 L_i と右端 R_i がスペース区切りで与えられる。

出力

K 行出力せよ。i 行目には、i 番目の車の通行区間が要修繕として報告される場合は YES を、そうでない場合は 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

Score : 333 pts

Problem Statement

Takahashi works at the road management division of the city hall. The road surface under his jurisdiction consists of N tiles arranged in a row, numbered tile 1, 2, \ldots, N from left to right.

Among these, M tiles are damaged. The numbers of the damaged tiles are B_1, B_2, \ldots, B_M, all of which are distinct (not necessarily in ascending order).

One day, K cars traveled along this road. The i-th car (1 \leq i \leq K) passes over every tile exactly once in the contiguous section from tile L_i to tile R_i (L_i \leq R_i). Each car's travel does not affect the travel of other cars, and tiles do not change their state when a car passes over them.

Each time a car passes over one damaged tile, one shock occurs. That is, the total number of shocks generated by the i-th car's travel equals the number of damaged tiles contained in the section from tile L_i to tile R_i.

For each car, Takahashi calculates the total number of shocks generated during its travel, and if it is at least the threshold T, he reports that car's travel section as "needs repair." Here, T is given as a positive integer.

For each of the K cars, determine whether its travel section is reported as needing repair.

Constraints

  • 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)
  • All B_i are distinct
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq K)
  • All input values are integers

Input

N M K T
B_1 B_2 \ldots B_M
L_1 R_1
L_2 R_2
\vdots
L_K R_K
  • The first line contains the total number of tiles N, the number of damaged tiles M, the number of cars K, and the shock count threshold T, separated by spaces.
  • The second line contains the numbers of the damaged tiles B_1, B_2, \ldots, B_M, separated by spaces. They are not necessarily in ascending order.
  • The following K lines give the travel section of each car.
  • The (2 + i)-th line contains the left endpoint L_i and right endpoint R_i of the i-th car's travel section, separated by spaces.

Output

Output K lines. On the i-th line, print YES if the i-th car's travel section is reported as needing repair, and NO otherwise.

Sample Input 1

10 3 3 2
2 5 8
1 6
3 4
4 9

Sample Output 1

YES
NO
YES

Sample Input 2

5 1 3 2
3
1 2
3 3
1 5

Sample Output 2

NO
NO
NO

Sample Input 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

Sample Output 3

YES
NO
YES
YES
NO
NO
YES
NO

Sample Input 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

Sample Output 4

YES
NO
YES
YES
NO
NO
YES
NO
YES
YES
NO
YES

Sample Input 5

1 1 1 1
1
1 1

Sample Output 5

YES