Problem Statement

Takahashi's sports gym has N members. The gym is open every day, and each member visits the gym every week according to a fixed weekly pattern of days.

A week consists of 7 days, and each day of the week is numbered from 1 to 7. We call day number d the "d-th day." The days member i visits every week are determined by a pair of integers (L_i, R_i) as follows:

• When L_i \leq R_i: Every week, they visit on consecutive days from the L_i-th day to the R_i-th day (both inclusive), for a total of R_i - L_i + 1 days. For example, if L_i = 2, R_i = 4, they visit on the 2nd, 3rd, and 4th days every week.
• When L_i > R_i: Every week, they visit from the L_i-th day to the 7th day, and from the 1st day to the R_i-th day (both inclusive), for a total of 7 - L_i + 1 + R_i days. This represents a contiguous interval when the week is viewed cyclically. For example, if L_i = 6, R_i = 2, they visit on the 6th, 7th, 1st, and 2nd days every week.

Takahashi operates the gym for W weeks (a total of 7 \times W days). We assign sequential numbers from 1 to 7W to the days over the entire operating period, and call sequential number k the "overall k-th day." The overall 1st day is the 1st day of week 1. In general, the overall k-th day (1 \leq k \leq 7W) corresponds to the ((k - 1) \bmod 7) + 1-th day of week \lceil k/7 \rceil. Each member visits the gym following the above pattern in every week without exception (no absences).

During this W-week operating period, M campaigns are scheduled. For the j-th campaign (1 \leq j \leq M), the campaign period runs from the overall S_j-th day to the overall E_j-th day (both inclusive). All campaign periods fall within the operating period. Campaign periods may overlap with each other.

The training points earned by a member who visits the gym on the overall k-th day are determined as follows: Let c (c \geq 0) be the number of campaigns whose campaign period includes the overall k-th day. Then the member earns 1 + c points for that visit. In other words, a visit earns 1 point even on days with no campaigns, and each active campaign grants an additional 1 point.

After the W weeks of operation are over, determine the total training points earned by each of the N members.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq W \leq 10^9
• 0 \leq M \leq 2 \times 10^5
• 1 \leq L_i \leq 7 (1 \leq i \leq N)
• 1 \leq R_i \leq 7 (1 \leq i \leq N)
• 1 \leq S_j \leq E_j \leq 7 \times W (1 \leq j \leq M)
• All input values are integers
• The total points earned by each member fits in a 64-bit signed integer

Sample Input 1

3 2 2
1 3
5 2
7 7
2 3
8 10

Sample Output 1

11
13
2

Sample Input 2

4 1 0
1 1
2 4
6 3
1 7

Sample Output 2

1
3
5
7

Sample Input 3

8 10 6
1 5
3 7
6 2
4 4
7 3
2 6
5 1
1 7
1 7
10 20
15 35
36 36
50 70
63 65

Sample Output 3

96
95
77
19
77
95
77
134

Sample Input 4

20 1000000000 15
1 1
2 2
3 3
4 4
5 5
6 6
7 7
1 3
2 5
3 7
5 2
6 1
7 4
1 7
4 2
2 1
6 6
3 5
7 1
5 5
1 1
2 100
50 1000
999999 1000005
7000000 7000100
123456789 123456999
999999999 1000000020
3500000000 3500000100
4999999999 5000000005
6000000000 6000001000
6999999990 7000000000
1 7000000000
2500000000 2500000000
3333333333 4444444444
123 456789

Sample Output 4

2158795759
2158795757
2158795754
2158795756
2158795756
2158795755
2158795755
6476387270
8635183023
10793978776
10793978782
6476387269
10793978781
15111570292
12952774538
15111570292
2158795755
6476387266
4317591514
2158795756

Sample Input 5

1 1000000000 2
1 7
1 7000000000
7000000000 7000000000

Sample Output 5

14000000001