問題文

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 点が与えられる。

入力例 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