Problem Statement

You are given a three-digit integer N where each digit is an integer between 1 and 9, inclusive.

Let a, b, c be the hundreds, tens, ones digits of N, respectively. Print an integer formed by arranging b, c, a in this order, and an integer formed by arranging c, a, b in this order.

Constraints

• N is a three-digit integer where each digit is an integer between 1 and 9, inclusive.

Sample Input 1

379

Sample Output 1

793 937

The hundreds, tens, ones digits of 379 are 3, 7, 9, respectively, so print 793 and 937.

Sample Input 2

919

Sample Output 2

199 991

The hundreds, tens, ones digits of 919 are 9, 1, 9, respectively, so print 199 and 991.

Problem Statement

Takahashi has N teeth arranged in a single row from left to right. The current condition of his teeth is represented by a string S.

If the i-th character of S is O, it means that the i-th tooth from the left is healthy. If it is X, it means that the i-th tooth has a cavity. Healthy teeth do not have cavities.

When he has K consecutive healthy teeth, he can eat one strawberry using those K teeth. After eating a strawberry, those K teeth develop cavities and become unhealthy.

Find the maximum number of strawberries he can eat.

Constraints

• 1 \leq K \leq N \leq 100
• N and K are integers.
• S is a string of length N consisting of O and X.

Sample Input 1

7 3
OOXOOOO

Sample Output 1

1

He can eat one strawberry by using the three consecutive healthy teeth from the 4th to 6th tooth from the left. After this, he cannot eat any more strawberries. Besides, there is no way for him to eat more than one strawberry. Therefore, print 1.

Sample Input 2

12 2
OXXOOOXOOOOX

Sample Output 2

3

Sample Input 3

22 5
XXOOOOOOOOXXOOOOOXXXXX

Sample Output 3

2

Problem Statement

There are N cells numbered from 1 to N in a row. Initially, M cells contain stones, and cell X_i contains A_i stones (1 \leq i \leq M).

You can perform the following operation any number of times (possibly zero):

• If cell i (1 \leq i \leq N-1) contains a stone, move one stone from cell i to cell i+1.

Find the minimum number of operations required to reach a state where each of the N cells contains exactly one stone. If it is impossible, print -1.

Constraints

• 2 \leq N \leq 2 \times 10^{9}
• 1 \leq M \leq 2 \times 10^{5}
• M \leq N
• 1 \leq X_i \leq N (1 \leq i \leq M)
• X_i \neq X_j (1 \leq i < j \leq M)
• 1 \leq A_i \leq 2 \times 10^{9} (1 \leq i \leq M)
• All input values are integers.

Sample Input 1

5 2
1 4
3 2

Sample Output 1

4

You can reach a state where each of the five cells contains exactly one stone with four operations as follows:

• Move one stone from cell 1 to cell 2.
• Move one stone from cell 2 to cell 3.
• Move one stone from cell 4 to cell 5.
• Move one stone from cell 1 to cell 2.

It is impossible to achieve the goal in three or fewer operations. Therefore, print 4.

Sample Input 2

10 3
1 4 8
4 2 4

Sample Output 2

-1

No matter how you perform the operations, you cannot reach a state where all ten cells contain exactly one stone. Therefore, print -1.

Problem Statement

Takahashi has 10^{100} flower pots. Initially, he is not growing any plants.

You are given Q queries to process in order.

There are three types of queries as follows.

• 1: Prepare one empty flower pot and put a plant in it. Here, the plant's height is 0.
• 2 T: Wait for T days. During this time, the height of every existing plants increases by T.
• 3 H: Harvest all plants with a height of at least H, and output the number of plants harvested. The harvested plants are removed from their flower pots.

Assume that performing queries of the first and third types takes zero time.

Constraints

• 1 \leq Q \leq 2 \times 10^{5}
• 1 \leq T,H \leq 10^{9}
• There is at least one query of the third type.
• All input values are integers.

Sample Input 1

6
1
2 15
1
3 10
2 20
3 20

Sample Output 1

1
1

Queries are processed in the following order:

• In the first query, a plant of height 0 is planted.
• In the second query, the height of the plant increases to 15.
• In the third query, another plant of height 0 is planted. Now there is one plant of height 15 and one plant of height 0.
• In the fourth query, all plants with height at least 10 are harvested. Here, one plant of height 15 gets harvested, and one plant of height 0 remains. Since one plant was harvested, print 1 on the first line.
• In the fifth query, the height of the remaining plant increases to 20.
• In the sixth query, all plants with height at least 20 are harvested. Here, one plant of height 20 gets harvested. Thus, print 1 on the second line.

Sample Input 2

15
1
1
2 226069413
3 1
1
1
2 214168203
1
3 214168203
1
1
1
2 314506461
2 245642315
3 1

Sample Output 2

2
2
4

Problem Statement

You are given a string S of length N consisting of digits from 1 through 9.

For each pair of integers (i,j) \ (1\leq i\leq j\leq N), define f(i, j) as the value obtained by interpreting the substring of S from the i-th through the j-th character as a decimal integer. Find \displaystyle \sum_{i=1}^N \sum_{j=i}^N f(i, j).

Constraints

• 1 \leq N \leq 2 \times 10^5
• N is an integer.
• S is a string of length N consisting of digits from 1 through 9.

Sample Input 1

3
379

Sample Output 1

514

The answer is f(1,1) + f(1,2) + f(1,3) + f(2,2) + f(2,3) + f(3,3) = 3 + 37 + 379 + 7 + 79 + 9 = 514.

Sample Input 2

30
314159265358979323846264338327

Sample Output 2

369673254065355789035427227741

Problem Statement

There are N buildings, building 1, building 2, \ldots, building N, arranged in this order in a straight line from west to east. Building 1 is the westernmost, and building N is the easternmost. The height of building i\ (1\leq i\leq N) is H_i.

For a pair of integers (i,j)\ (1\leq i\lt j\leq N), building j can be seen from building i if the following condition is satisfied.

• There is no building taller than building j between buildings i and j. In other words, there is no integer k\ (i\lt k\lt j) such that H_k > H_j.

You are given Q queries. In the i-th query, given a pair of integers (l_i,r_i)\ (l_i\lt r_i), find the number of buildings to the east of building r_i (that is, buildings r_i + 1, r_i + 2, \ldots, N) that can be seen from both buildings l_i and r_i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq H_i \leq N
• H_i\neq H_j\ (i\neq j)
• 1 \leq l_i < r_i \leq N
• All input values are integers.

Sample Input 1

5 3
2 1 4 3 5
1 2
3 5
1 4

Sample Output 1

2
0
1

• For the first query, among the buildings to the east of building 2, buildings 3 and 5 can be seen from both buildings 1 and 2, so the answer is 2.
• For the second query, there are no buildings to the east of building 5.
• For the third query, among the buildings to the east of building 4, building 5 can be seen from both buildings 1 and 4, so the answer is 1.

Sample Input 2

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

Sample Output 2

1
3
1
2
1
0
1
1
0
0

Problem Statement

You are given a grid S with H rows and W columns consisting of 1, 2, 3, and ?. The character at the i-th row and j-th column is S_{i,j}.

By replacing each ? in S with 1, 2, or 3, we can obtain 3^q different grids, where q is the number of ?. Among these grids, how many satisfy the following condition? Print the count modulo 998244353.

• Any two adjacent (edge-sharing) cells contain different digits.

Constraints

• 1 \leq H, W
• H \times W \leq 200
• H and W are integers.
• S is a grid with H rows and W columns consisting of 1, 2, 3, and ?.

Sample Input 1

2 2
1?
??

Sample Output 1

6

Among the grids obtained by replacing each ? in S with 1, 2, or 3, the following six grids satisfy the condition.

12  12  12  13  13  13
21  23  31  21  31  32

Sample Input 2

2 3
123
3?1

Sample Output 2

0

None of the grids obtained by replacing ? satisfies the condition.

Sample Input 3

8 8
3?1?????
???1????
??????2?
????????
????????
????13??
??13?1??
????????

Sample Output 3

779135038