问题

AtCoder国的一年有$Y$周，每周有$W$天。换句话说，一年有$Y \times W$天。而且，每个星期都有从$1$到$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$），星期$C_j$的第$B_j$次出现是假日。
• 如果第$x$天和第$y$天都是假日，并且满足$1 \leq y - x - 1 \leq D$，则从第$x + 1$天到第$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