Problem Description

In the country of AtCoder, a year consists of $ Y $ weeks, and each week consists of $ W $ days. That is, a year consists of $Y \times W$ days. Additionally, the days of the week are numbered sequentially from $ 1 $ to $ W $. Specifically, for each $ i $ ($1 \leq i < W$), the day following day $ i $ is day $ i + 1 $, and the day following day $ W $ is day $ 1 $.

The holidays in AtCoder are defined as follows:

• For each $ i $ ($1 \leq i \leq N$), the $ A_i $-th day of the year is a holiday.
• For each $ j $ ($1 \leq j \leq M$), the $ B_j $-th occurrence of day $ C_j $ in the year is a holiday.
• If the $ x $-th day and the $ y $-th day of the year are holidays, and $1 \leq y - x - 1 \leq D$ holds, then the $ x + 1 $-th, $ x + 2 $-th, ..., $ y - 1 $-th days of the year are all holidays.
• Any day not designated as a holiday by the above rules is not a holiday.

Determine the number of holidays in the year for each starting day of the week $ d = 1, 2, ..., W $ when the first day of the year is day $ d $.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output $ W $ lines. The $ i $-th line ($1 \leq i \leq W$) should contain the answer when $ d = i $.

Sample Input and Output

Sample Input #1

3 4
0 3 1
1 2
2 4
3 3

Sample Output #1

3
3
4
4

Sample Input #2

100 5
0 2 496
100 5
1 1

Sample Output #2

2
495
495
495
495

Sample Input #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

Sample Output #3

16
16
15
16
17
16
16

Sample Input #4

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

Sample Output #4

7
9
11
9
9
10
8
8
7
8

Notes/Hints

Constraints

• $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$)
• $A_i \neq A_j$ for $i \neq j$
• $1 \leq B_i \leq Y$ ($1 \leq i \leq M$)
• $1 \leq C_i \leq W$ ($1 \leq i \leq M$)
• $B_i \neq B_j$ or $C_i \neq C_j$ for $i \neq j$

Partial Points

• Correctly answering the dataset where $ N = 0 $ will award $ 600 $ points.

Sample Explanation 1

For example, if the first day of the year is day $ 3 $, the $ 4 $-th, $ 5 $-th, $ 6 $-th, and $ 9 $-th days of the year will be holidays.

见题面 Input 部分

见题面 Output 部分