← 返回题目列表

AtCoder · bitflyer2018_qual_e

E. 祝日

中文机器翻译题面 查看原题

配点 : 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