E - 祝日

Time Limit: 5 sec / Memory Limit: 256 MB

配点 : 700

問題文

AtCoder 国の 1 年は Y 週間からなり、1 週間は W 日間からなります。 すなわち、1 年は Y \times W 日間からなります。 また、曜日には順に 1, 2, ..., W の番号がついています。 すなわち、各 i (1 \leq i < W) に対して曜日 i の日の翌日は曜日 i + 1 で、 曜日 W の日の翌日は曜日 1 です。

AtCoder 国の祝日は以下のように定められています。

  • i (1 \leq i \leq N) に対して、一年のうち A_i 日目は祝日である。
  • j (1 \leq j \leq M) に対して、一年のうち B_j 回目の曜日 C_j の日は祝日である。
  • 一年のうち x 日目および y 日目が祝日であり、1 \leq y - x - 1 \leq D が成り立つとき、 一年のうち x + 1, x + 2, ..., y - 1 日目はすべて祝日である。
  • 上記で祝日とならなかった日はすべて祝日ではない。

AtCoder 国の一年の最初の日が曜日 d であった場合の一年間の祝日の日数を各 d = 1, 2, ..., W に対して求めてください。

制約

  • 1 \leq Y \leq 10^9
  • 1 \leq W \leq 10^5
  • 0 \leq N \leq 50
  • 0 \leq M \leq 10^5
  • 0 \leq D \leq Y \times W
  • 1 \leq A_i \leq Y \times W (1 \leq i \leq N)
  • i \neq j のとき、A_i \neq A_j
  • 1 \leq B_i \leq Y (1 \leq i \leq M)
  • 1 \leq C_i \leq W (1 \leq i \leq M)
  • i \neq j のとき、B_i \neq B_j または C_i \neq C_j

部分点

  • N = 0 を満たすデータセットに正答すると、600 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

Y W
N M D
A_1
A_2
:
A_N
B_1 C_1
B_2 C_2
:
B_M C_M

出力

W 行出力せよ。i 行目 (1 \leq i \leq W) には、d = i のときの答えを出力せよ。


入力例 1

3 4
0 3 1
1 2
2 4
3 3

出力例 1

3
3
4
4

たとえば、一年の最初の日の曜日が 3 であった場合、一年の 4, 5, 6, 9 日目が祝日となります。


入力例 2

100 5
0 2 496
100 5
1 1

出力例 2

2
495
495
495
495

入力例 3

52 7
12 4 1
1
42
80
119
123
124
125
126
266
307
327
357
2 2
29 2
38 2
41 2

出力例 3

16
16
15
16
17
16
16

入力例 4

3 10
2 5 1
29
9
2 6
1 9
3 9
3 7
2 8

出力例 4

7
9
11
9
9
10
8
8
7
8