Problem Statement

You are given a string S consisting of uppercase and lowercase English letters.
Here, exactly one character of S is uppercase, and the others are all lowercase.
Find the integer x such that the x-th character of S is uppercase.
Here, the initial character of S is considered the 1-st one.

Constraints

• S is a string of length between 2 and 100, inclusive, consisting of uppercase and lowercase English letters.
• S has exactly one uppercase letter.

Sample Input 1

aBc

Sample Output 1

2

The 1-st character of aBc is a, the 2-nd is B, and the 3-rd is c; the 2-nd character is uppercase.
Thus, 2 should be printed.

Sample Input 2

xxxxxxXxxx

Sample Output 2

7

An uppercase letter X occurs as the 7-th character of S=xxxxxxXxxx, so 7 should be printed.

Sample Input 3

Zz

Sample Output 3

1

Problem Statement

Let us assume that water pressure depends only on depth and is \dfrac{x}{100} megapascal at a depth of x meters.

What is the water pressure in megapascals at a depth of D meters?

Constraints

• 1 \leq D \leq 10000
• D is an integer.

Sample Input 1

1000

Sample Output 1

10

The water pressure at a depth of 1000 meters is 10 megapascal. Outputs such as 10.0 and 9.999999 would also be accepted.

Sample Input 2

50

Sample Output 2

0.5

Sample Input 3

3141

Sample Output 3

31.41

Problem Statement

You are given a 4-digit PIN: X_1X_2X_3X_4, which may begin with a 0. The PIN is said to be weak when it satisfies one of the following conditions:

• All of the four digits are the same.
• For each integer i such that 1\leq i\leq 3, X_{i+1} follows X_i. Here, j+1 follows j for each 0\leq j\leq 8, and 0 follows 9.

If the given PIN is weak, print Weak; otherwise, print Strong.

Constraints

• 0 \leq X_1, X_2, X_3, X_4 \leq 9
• X_1, X_2, X_3, and X_4 are integers.

Sample Input 1

7777

Sample Output 1

Weak

All four digits are 7, satisfying the first condition, so this PIN is weak.

Sample Input 2

0112

Sample Output 2

Strong

The first and second digits differ, and the third digit does not follow the second digit, so neither condition is satisfied.

Sample Input 3

9012

Sample Output 3

Weak

Note that 0 follows 9.

Problem Statement

There are N snakes.

Initially, the thickness of the i-th snake is T_i, and its length is L_i.

The weight of a snake is defined as the product of its thickness and length.

For each integer k satisfying 1 \leq k \leq D, find the weight of the heaviest snake when every snake's length has increased by k.

Constraints

• 1 \leq N, D \leq 100
• 1 \leq T_i, L_i \leq 100
• All input values are integers.

Sample Input 1

4 3
3 3
5 1
2 4
1 10

Sample Output 1

12
15
20

When every snake’s length has increased by 1, the snakes' weights become 12, 10, 10, 11, so print 12 on the first line.

When every snake’s length has increased by 2, the snakes' weights become 15, 15, 12, 12, so print 15 on the second line.

When every snake’s length has increased by 3, the snakes' weights become 18, 20, 14, 13, so print 20 on the third line.

Sample Input 2

1 4
100 100

Sample Output 2

10100
10200
10300
10400

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N and a positive integer K.

Find the sum of the integers between 1 and K, inclusive, that do not appear in the sequence A.

Constraints

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

Sample Input 1

4 5
1 6 3 1

Sample Output 1

11

Among the integers between 1 and 5, three numbers, 2, 4, and 5, do not appear in A.

Thus, print their sum: 2+4+5=11.

Sample Input 2

1 3
346

Sample Output 2

6

Sample Input 3

10 158260522
877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739

Sample Output 3

12523196466007058

Problem Statement

The programming contest World Tour Finals is underway, where N players are participating, and half of the competition time has passed. There are M problems in this contest, and the score A_i of problem i is a multiple of 100 between 500 and 2500, inclusive.

For each i = 1, \ldots, N, you are given a string S_i that indicates which problems player i has already solved. S_i is a string of length M consisting of o and x, where the j-th character of S_i is o if player i has already solved problem j, and x if they have not yet solved it. Here, none of the players have solved all the problems yet.

The total score of player i is calculated as the sum of the scores of the problems they have solved, plus a bonus score of i points.
For each i = 1, \ldots, N, answer the following question.

• At least how many of the problems that player i has not yet solved must player i solve to exceed all other players' current total scores?

Note that under the conditions in this statement and the constraints, it can be proved that player i can exceed all other players' current total scores by solving all the problems, so the answer is always defined.

Constraints

• 2\leq N\leq 100
• 1\leq M\leq 100
• 500\leq A_i\leq 2500
• A_i is a multiple of 100.
• S_i is a string of length M consisting of o and x.
• S_i contains at least one x.
• All numeric values in the input are integers.

Sample Input 1

3 4
1000 500 700 2000
xxxo
ooxx
oxox

Sample Output 1

0
1
1

The players' total scores at the halfway point of the competition time are 2001 points for player 1, 1502 points for player 2, and 1703 points for player 3.

Player 1 is already ahead of all other players' total scores without solving any more problems.

Player 2 can, for example, solve problem 4 to have a total score of 3502 points, which would exceed all other players' total scores.

Player 3 can also, for example, solve problem 4 to have a total score of 3703 points, which would exceed all other players' total scores.

Sample Input 2

5 5
1000 1500 2000 2000 2500
xxxxx
oxxxx
xxxxx
oxxxx
oxxxx

Sample Output 2

1
1
1
1
0

Sample Input 3

7 8
500 500 500 500 500 500 500 500
xxxxxxxx
oxxxxxxx
ooxxxxxx
oooxxxxx
ooooxxxx
oooooxxx
ooooooxx

Sample Output 3

7
6
5
4
3
2
0

Problem Statement

There is a H \times W-square grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
Each square is described by a character C_{i, j}, where C_{i, j} = . means (i, j) is an empty square, and C_{i, j} = # means (i, j) is a wall.

Takahashi is about to start walking in this grid. When he is on (i, j), he can go to (i, j + 1) or (i + 1, j). However, he cannot exit the grid or enter a wall square. He will stop when there is no more square to go to.

When starting on (1, 1), at most how many squares can Takahashi visit before he stops?

Constraints

• 1 \leq H, W \leq 100
• H and W are integers.
• C_{i, j} = . or C_{i, j} = #. (1 \leq i \leq H, 1 \leq j \leq W)
• C_{1, 1} = .

Sample Input 1

3 4
.#..
..#.
..##

Sample Output 1

4

For example, by going (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2), he can visit 4 squares.

He cannot visit 5 or more squares, so we should print 4.

Sample Input 2

1 1
.

Sample Output 2

1

Sample Input 3

5 5
.....
.....
.....
.....
.....

Sample Output 3

9

Problem Statement

There are N people numbered from 1 to N standing in a circle. Person 1 is to the right of person 2, person 2 is to the right of person 3, ..., and person N is to the right of person 1.

We will give each of the N people an integer between 0 and M-1, inclusive.
Among the M^N ways to distribute integers, find the number, modulo 998244353, of such ways that no two adjacent people have the same integer.

Constraints

• 2 \leq N,M \leq 10^6
• N and M are integers.

Sample Input 1

3 3

Sample Output 1

6

There are six desired ways, where the integers given to persons 1,2,3 are (0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0).

Sample Input 2

4 2

Sample Output 2

2

There are two desired ways, where the integers given to persons 1,2,3,4 are (0,1,0,1),(1,0,1,0).

Sample Input 3

987654 456789

Sample Output 3

778634319

Be sure to find the number modulo 998244353.

Problem Statement

There are N boxes numbered 1,2,\ldots,N, and 10^{100} balls numbered 1,2,\dots,10^{100}. Initially, box i contains just ball i.

Process a total of Q operations that will be performed.

There are three types of operations: 1, 2, and 3.

Type 1: Put all contents of box Y into box X. It is guaranteed that X \neq Y.

1 X Y

Type 2: Put ball k+1 into box X, where k is the current total number of balls contained in the boxes.

2 X

Type 3: Report the number of the box that contains ball X.

3 X

Constraints

• All values in the input are integers.
• 2 \le N \le 3 \times 10^5
• 1 \le Q \le 3 \times 10^5
• For each type-1 operation, 1 \le X,Y \le N and X \neq Y.
• For each type-2 operation, 1 \le X \le N.
• For each type-3 operation, ball X is contained in some box at that point.
• There is at least one type-3 operation.

Sample Input 1

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

Sample Output 1

5
4
3
1
3

This input contains ten operations.

• The first operation is of type 3. Ball 5 is in box 5.
• The second operation is of type 1. Put all contents of box 4 into box 1.
  • Box 1 now contains balls 1 and 4, and box 4 is now empty.
• The third operation is of type 2. Put ball 6 into box 1.
• The fourth operation is of type 2. Put ball 7 into box 4.
• The fifth operation is of type 3. Ball 7 is in box 4.
• The sixth operation is of type 1. Put all contents of box 1 into box 3.
  • Box 3 now contains balls 1, 3, 4, and 6, and box 1 is now empty.
• The seventh operation is of type 3. Ball 4 is in box 3.
• The eighth operation is of type 1. Put all contents of box 4 into box 1.
  • Box 1 now contains ball 7, and box 4 is now empty.
• The ninth operation is of type 3. Ball 7 is in box 1.
• The tenth operation is of type 3. Ball 6 is in box 3.