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