Problem Statement

There are N lights in Takahashi's room. Each light has a single switch that toggles it ON/OFF. Each time a switch is pressed, the state of that light is flipped (ON becomes OFF, and OFF becomes ON). Each light's switch only affects that light and does not change the state of any other light.

The initial state (ON or OFF) of each light is given by a string S_i. When S_i is Yes, the initial state of light i is ON, and when S_i is No, the initial state is OFF.

Takahashi will now press the switch of light i exactly K_i times for each light i (1 \leq i \leq N).

Determine the final state of each light after all switch operations are completed.

Constraints

• 1 \leq N \leq 10^5
• S_i is either Yes or No
• 1 \leq K_i \leq 10^9
• N, K_i are all integers

Sample Input 1

3
Yes 1
No 2
Yes 3

Sample Output 1

No
No
No

Sample Input 2

4
Yes 2
No 1
No 4
Yes 5

Sample Output 2

Yes
Yes
No
No

Sample Input 3

6
Yes 100
No 99
Yes 1000000
No 999999
Yes 42
No 7

Sample Output 3

Yes
Yes
Yes
Yes
Yes
Yes

Sample Input 4

10
Yes 1000000000
No 1000000000
Yes 999999999
No 999999999
Yes 1
No 1
Yes 2
No 2
Yes 500000000
No 500000001

Sample Output 4

Yes
No
No
Yes
No
Yes
Yes
No
Yes
Yes

Sample Input 5

1
No 1

Sample Output 5

Yes

Problem Statement

Takahashi is trying to walk through a long corridor consisting of N tiles arranged in a row. The tiles are numbered from left to right as Tile 1, Tile 2, \ldots, Tile N.

Each tile is covered with dust. Initially, Tile i has dust of thickness H_i. When Takahashi steps on Tile i, the dust thickness on that tile becomes \max(0,\; H_i - D_i), where D_i is a non-negative integer defined for Tile i. The dust thickness on tiles that Takahashi does not step on remains unchanged at the initial thickness H_i.

Takahashi starts at Tile 1, and Tile N is the goal. Takahashi always moves only to the right. Specifically, when he is currently on Tile j, he can choose Tile j+1 or Tile j+2 as his next destination. However, he cannot move beyond Tile N (he can move to Tile j+1 only if j+1 \leq N, and to Tile j+2 only if j+2 \leq N). Takahashi steps on a tile upon arriving at it. He also steps on Tile 1, the starting point. Takahashi ends his movement upon reaching Tile N.

Due to the above movement rules, Tile 1 and Tile N are always stepped on. Also, since Takahashi always moves to the right, he never steps on the same tile more than once.

After Takahashi walks through the corridor, Aoki inspects the corridor and counts the number of tiles with footprints. A footprint is left on Tile i if the dust thickness on Tile i after Takahashi's movement is strictly less than the initial thickness H_i.

• If Takahashi did not step on Tile i, the dust thickness remains H_i, so no footprint is left.
• If Takahashi stepped on Tile i, the dust thickness becomes \max(0,\; H_i - D_i). This is strictly less than H_i if and only if H_i > 0 and D_i > 0. Therefore, if H_i = 0 or D_i = 0, no footprint is left even if the tile is stepped on.

Takahashi wants to minimize the number of tiles with footprints. Find the minimum number of tiles with footprints when Takahashi moves along an optimal path.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq H_i \leq 10^9
• 0 \leq D_i \leq 10^9
• All input values are integers.

Sample Input 1

5
3 0 5 2 4
1 1 1 1 1

Sample Output 1

3

Sample Input 2

8
5 0 3 0 7 0 2 4
2 3 0 1 1 5 1 3

Sample Output 2

2

Sample Input 3

15
1 1 0 1 0 1 1 0 0 1 1 0 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

5

Problem Statement

Takahashi is the manager of a city. Along the main street, N street lights are lined up in a row, numbered from left to right as street light 1, street light 2, \ldots, street light N. The initial durability of street light i (1 \leq i \leq N) is H_i. A street light whose durability becomes 0 or less is considered to have collapsed.

This winter, M blizzards will come. The j-th blizzard (1 \leq j \leq M) decreases the durability of all street lights in the range from street light L_j to street light R_j by D_j.

The final durability of each street light is its initial durability minus the total decrease from all blizzards. That is, even if a street light's durability becomes 0 or less partway through, it is not exempt from the decreases caused by subsequent blizzards.

After all blizzards have passed, determine the number of street lights whose final durability is 1 or more (i.e., that have not collapsed).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
• 1 \leq D_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers.

Sample Input 1

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

Sample Output 1

3

Sample Input 2

3 2
3 2 1
1 3 2
1 1 1

Sample Output 2

0

Sample Input 3

10 5
100 50 30 80 60 40 90 20 70 10
1 5 20
3 8 15
6 10 25
1 10 10
2 4 30

Sample Output 3

5

Sample Input 4

15 6
1000000000 500 300 800 600 400 900 200 700 100 550 350 750 450 1000000000
1 15 100
1 8 200
5 12 150
3 10 50
7 15 100
1 15 50

Sample Output 4

10

Sample Input 5

1 1
1
1 1 1

Sample Output 5

0

Problem Statement

Takahashi is participating in an event at a game center. At the venue, cards are displayed in a grid of N rows and M columns, and each card has an integer point value from 0 to 9 written on it. The point value of the card at row i, column j (1 \leq i \leq N, 1 \leq j \leq M) of the grid is denoted as a_{i,j}.

Takahashi will select exactly one rectangular region from this grid and obtain all the cards within that region. A "rectangular region" refers to the set of all cards from row r_1 to row r_2 from the top, and from column c_1 to column c_2 from the left (1 \leq r_1 \leq r_2 \leq N, 1 \leq c_1 \leq c_2 \leq M). Letting the number of rows in this region be h = r_2 - r_1 + 1 and the number of columns be w = c_2 - c_1 + 1, the region contains h \times w cards. The sum of the point values written on the obtained cards becomes Takahashi's score.

However, this event has an "exact rule": the number of cards contained in the chosen rectangular region must be exactly K. In other words, the condition h \times w = K must be satisfied.

Find the maximum score Takahashi can achieve. If no rectangular region satisfying the exact rule exists, output -1.

Constraints

• 1 \leq N \leq 200
• 1 \leq M \leq 200
• 1 \leq K \leq N \times M
• N, M, K are all integers
• S_i (1 \leq i \leq N) is a string of length M, where each character is one of 0 through 9

Sample Input 1

3 4 6
1234
5678
9012

Sample Output 1

30

Sample Input 2

4 5 7
12345
67890
11111
99999

Sample Output 2

-1

Sample Input 3

5 6 12
193842
681937
274619
938271
526184

Sample Output 3

68

Problem Statement

Takahashi is organizing a quiz competition for his school's cultural festival. There are N students participating in the quiz competition, and student i (1 \leq i \leq N) has a skill value A_i. Even if some students have the same skill value, each student is distinguished as a different person.

Takahashi will select exactly K people from these N students to form one team. Each student can only be selected once. To make the competition fair, he wants the sum of the skill values of the selected K people to be a multiple of M.

Find the number of ways to select the students that satisfy the condition, modulo 10^9 + 7.

Here, a positive integer X is a multiple of M if there exists a positive integer k such that X = kM.

Constraints

• 1 \leq N \leq 30
• 1 \leq K \leq N
• 1 \leq M \leq 10^9
• 1 \leq A_i \leq 10^9
• All inputs are integers

Sample Input 1

4 2 3
1 2 3 4

Sample Output 1

2

Sample Input 2

6 3 5
1 2 3 4 5 6

Sample Output 2

4

Sample Input 3

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

Sample Output 3

36