Problem Statement

Takahashi will visit his friends' houses in the order of Friend 1, Friend 2, ..., Friend N to deliver presents to his N friends.

Takahashi initially holds N presents. However, there are obstacles on the way to each friend's house, and he may stumble and drop presents.

On the way to Friend i's house, Takahashi stumbles exactly F_i times. Each time he stumbles, if he holds at least 1 present at that moment, he drops and loses 1 present, reducing the number of presents he holds by 1. If he stumbles while holding 0 presents, nothing happens.

Upon arriving at Friend i's house, if Takahashi holds at least 1 present, he gives 1 present to the friend. In this case, the number of presents he holds decreases by 1. If he holds no presents, he cannot give anything.

Find the number of friends who received a present after Takahashi has visited all his friends.

Constraints

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

Sample Input 1

5
0
1
0
2
0

Sample Output 1

3

Sample Input 2

4
0
0
0
0

Sample Output 2

4

Sample Input 3

10
0
2
0
1
0
3
0
0
1
0

Sample Output 3

5

Sample Input 4

25
0
0
1
0
2
0
0
1
3
0
0
0
2
1
0
4
0
0
1
0
2
0
0
5
0

Sample Output 4

15

Sample Input 5

1
1000000000

Sample Output 5

0

Problem Statement

Takahashi works as a librarian and handles inquiries from patrons about the titles of books arranged on a bookshelf.

The bookshelf managed by Takahashi has N books lined up in a row, and the title of the i-th book from the left is the string S_i (1 \leq i \leq N). Note that there may be multiple books with the same title. One day, Aoki visits the library and makes Q inquiries about the books on the bookshelf.

In the j-th inquiry (1 \leq j \leq Q), Aoki specifies two integers L_j, R_j and one string T_j. Takahashi must answer how many books among those from the L_j-th to the R_j-th from the left (inclusive) have a title that exactly matches the string T_j.

Find the answers to all inquiries.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• N, Q are integers
• S_i is a string of lowercase English letters with length between 1 and 10 inclusive (1 \leq i \leq N)
• 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
• L_j, R_j are integers
• T_j is a string of lowercase English letters with length between 1 and 10 inclusive (1 \leq j \leq Q)

Sample Input 1

5 3
apple banana apple orange apple
1 5 apple
2 4 apple
1 3 grape

Sample Output 1

3
1
0

Sample Input 2

8 5
cat dog cat bird dog cat dog cat
1 8 cat
3 6 dog
1 4 bird
5 8 cat
2 2 dog

Sample Output 2

4
1
1
2
1

Sample Input 3

15 8
book pen book note pen book desk pen note book lamp pen book note desk
1 15 book
1 15 pen
3 10 book
5 12 pen
1 1 book
7 7 desk
10 15 note
1 15 chair

Sample Output 3

5
4
3
3
1
1
1
0

Problem Statement

Takahashi has N blocks arranged in a row from left to right. The height of the i-th block from the left is H_i.

Takahashi performs a reorganization on this row of blocks using the following procedure. The reorganization consists of multiple rounds.

Procedure of one round:

1. Let M be the number of blocks currently in the row, and number the blocks in the row from left to right as positions 1, 2, \ldots, M.
2. Set a cursor k to M.
3. While k \geq 2, repeat the following:

• If the height of the block at position k is strictly greater than the height of the block at position k-1:
• Remove the block at position k-1 from the row. Shift the remaining blocks to the left and re-index them. As a result, the position index of each block to the right of the removed block decreases by 1. In particular, the block that was at position k just before this step moves to position k-1.
• Decrease k by 1. As a result, in the next step, the cursor will point to the block that caused the removal in this step. Thus, the same block will be compared with its new left neighbor.
• Otherwise (if the height of the block at position k is less than or equal to the height of the block at position k-1):
• Do nothing, and decrease k by 1.

1. When k < 2, the round ends.

Repetition of rounds and termination of reorganization:

• If one or more blocks were removed during the round, start a new round (return to Step 1).
• If no blocks were removed during the round, the reorganization ends.

Note that if there is 1 or fewer blocks in the current row, we will have k \leq 1 in Step 2, which does not satisfy the condition k \geq 2 in Step 3. Thus, no blocks will be removed in that round, and the reorganization will end.

Find the number of blocks remaining in the row when the reorganization ends.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers.

Sample Input 1

5
3 1 4 2 5

Sample Output 1

1

Sample Input 2

6
9 7 7 5 3 1

Sample Output 2

6

Sample Input 3

12
4 2 6 3 5 1 7 7 2 8 4 6

Sample Output 3

2

Sample Input 4

30
15 3 20 18 7 25 10 10 30 5 12 28 1 35 22 22 40 6 9 33 14 50 2 45 45 11 60 8 55 13

Sample Output 4

3

Sample Input 5

1
1000000000

Sample Output 5

1

Problem Statement

Takahashi manages N factories. Each factory i (1 \leq i \leq N) has a positive integer P_i representing its production efficiency.

The total production of all N factories is evaluated as the product of the production efficiencies of all factories P_1 \times P_2 \times \cdots \times P_N taken modulo a prime number M.

Takahashi wants to perform Q simulations. In the j-th simulation (1 \leq j \leq Q), only the production efficiency of factory X_j is changed to a non-negative integer V_j, while the production efficiencies of all other factories remain unchanged. That is, find

P_1 \times \cdots \times P_{X_j - 1} \times V_j \times P_{X_j + 1} \times \cdots \times P_N

modulo M.

Each simulation is independent. Changes made in one simulation do not affect other simulations; each simulation starts from the original production efficiencies P_1, P_2, \ldots, P_N.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 2 \leq M \leq 10^9
• M is a prime number
• 1 \leq P_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq X_j \leq N (1 \leq j \leq Q)
• 0 \leq V_j \leq 10^9 (1 \leq j \leq Q)
• All inputs are integers

Sample Input 1

3 4 7
2 3 4
1 5
2 0
3 6
2 3

Sample Output 1

4
0
1
3

Sample Input 2

4 5 5
1 5 2 3
2 4
1 7
3 10
4 0
2 5

Sample Output 2

4
0
0
0
0

Sample Input 3

10 10 17
3 8 17 5 21 1 34 9 2 11
3 4
7 6
1 0
5 100
10 17
2 19
8 8
4 12
6 13
9 51

Sample Output 3

0
0
0
0
0
0
0
0
0
0

Sample Input 4

30 25 998244353
123456789 987654321 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 999999999 998244353 1 2 3 4 5 6 7 8 9 10 314159265 271828182 161803398 42 1000000000 999999937 12345 54321
12 7
1 1000000000
30 0
27 998244353
13 123456789
20 876543210
5 5
18 18
22 22
24 314159265
2 1
11 999999999
14 0
25 271828182
28 999999937
3 333333333
7 777777777
16 4
26 42
29 12345
10 888888888
4 222222222
19 7
21 9
6 444444444

Sample Output 4

643945267
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

Sample Input 5

1 1 2
1000000000
1 0

Sample Output 5

0

Problem Statement

Takahashi has N cards numbered from 1 to N. He wants to know how many of these cards have a fluctuation value of exactly K.

Here, the "fluctuation value" of a positive integer is defined as follows:

Let L be the number of digits when a positive integer is represented in standard decimal notation (without leading zeros), and let the digits from the most significant to the least significant be d_1, d_2, \ldots, d_L (d_1 \geq 1). The fluctuation value is defined as:

\sum_{i=1}^{L-1} |d_i - d_{i+1}|

For a single-digit number (L = 1), there are no terms in this sum, so the fluctuation value is 0.

For example, 3517 has 4 digits with d_1 = 3, d_2 = 5, d_3 = 1, d_4 = 7, so its fluctuation value is |3-5| + |5-1| + |1-7| = 2 + 4 + 6 = 12. Also, 7 is a single-digit number, so its fluctuation value is 0.

Find the number of integers between 1 and N, inclusive, whose fluctuation value is exactly K.

Constraints

• 1 \leq N \leq 10^{18}
• 0 \leq K \leq 153
• N and K are integers.

Sample Input 1

20 1

Sample Output 1

2

Sample Input 2

100 0

Sample Output 2

18

Sample Input 3

1234567 12

Sample Output 3

73745

Sample Input 4

987654321012345678 80

Sample Output 4

3107339199338170

Sample Input 5

1 0

Sample Output 5

1