Problem Statement

In the ceremony commemorating ABC400, we want to arrange 400 people in a rectangular formation of A rows and B columns without any gaps.

You are given a positive integer A. Print the value of a positive integer B for which such an arrangement is possible. If there is no such positive integer B, print -1.

Constraints

• A is an integer between 1 and 400, inclusive.

Sample Input 1

10

Sample Output 1

40

We can arrange 400 people in 10 rows and 40 columns.

Sample Input 2

11

Sample Output 2

-1

Sample Input 3

400

Sample Output 3

1

Problem Statement

There was a contest with N problems. The i-th (1\leq i\leq N) problem was worth A_i points.

Snuke took part in this contest and solved M problems: the B_1-th, B_2-th, \ldots, and B_M-th ones. Find his total score.

Here, the total score is defined as the sum of the points for the problems he solved.

Constraints

• 1\leq M \leq N \leq 100
• 1\leq A_i \leq 100
• 1\leq B_1 < B_2 < \ldots < B_M \leq N
• All values in the input are integers.

Sample Input 1

3 2
10 20 30
1 3

Sample Output 1

40

Snuke solved the 1-st and 3-rd problems, which are worth 10 and 30 points, respectively. Thus, the total score is 10+30=40 points.

Sample Input 2

4 1
1 1 1 100
4

Sample Output 2

100

Sample Input 3

8 4
22 75 26 45 72 81 47 29
4 6 7 8

Sample Output 3

202

Problem Statement

Given a positive integer N, find the maximum integer k such that 2^k \le N.

Constraints

• N is an integer satisfying 1 \le N \le 10^{18}.

Sample Input 1

6

Sample Output 1

2

• k=2 satisfies 2^2=4 \le 6.
• For every integer k such that k \ge 3, 2^k > 6 holds.

Therefore, the answer is k=2.

Sample Input 2

1

Sample Output 2

0

Note that 2^0=1.

Sample Input 3

1000000000000000000

Sample Output 3

59

The input value may not fit into a 32-bit integer.

Problem Statement

For a positive integer x, define f(x) as follows:

• Let s_x be the string obtained by representing x in decimal notation (without leading zeros), and let \text{rev}(s_x) be the string obtained by reversing s_x. The value of f(x) is the integer obtained by interpreting \text{rev}(s_x) as a decimal representation of an integer.

For example, when x=13, we have \text{rev}(s_x)= 31, so f(x)=31; when x=10, we have \text{rev}(s_x)= 01, so f(x)=1. Particularly, for any positive integer x, the value of f(x) is a positive integer.

You are given positive integers X and Y. Define a sequence of positive integers A=(a_1,a_2,\dots,a_{10}) as follows:

• a_1 = X
• a_2 = Y
• a_i = f(a_{i-1}+a_{i-2})\ (i\geq 3)

Find the value of a_{10}.

Constraints

• 1\leq X,Y \leq 10^5
• All input values are integers.

Sample Input 1

1 1

Sample Output 1

415

The values of the elements of A are as follows:

• a_1=1
• a_2=1
• a_3=2
• a_4=3
• a_5=5
• a_6=8
• a_7=31
• a_8=93
• a_9=421
• a_{10}=415

Thus, print 415.

Sample Input 2

3 7

Sample Output 2

895

Sample Input 3

90701 90204

Sample Output 3

9560800101

Problem Statement

We have an empty box.
Takahashi can cast the following two spells any number of times in any order.

• Spell A: puts one new ball into the box.
• Spell B: doubles the number of balls in the box.

Tell us a way to have exactly N balls in the box with at most \mathbf{120} casts of spells.
It can be proved that there always exists such a way under the Constraints given.

There is no way other than spells to alter the number of balls in the box.

Constraints

• 1 \leq N \leq 10^{18}
• All values in input are integers.

Sample Input 1

5

Sample Output 1

AABA

This changes the number of balls as follows: 0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5.
There are also other acceptable outputs, such as AAAAA.

Sample Input 2

14

Sample Output 2

BBABBAAAB

This changes the number of balls as follows: 0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14.
It is not required to minimize the length of S.

Problem Statement

There is a 3\times3 grid with numbers between 1 and 9, inclusive, written in each square. The square at the i-th row from the top and j-th column from the left (1\leq i\leq3,1\leq j\leq3) contains the number c _ {i,j}.

The same number may be written in different squares, but not in three consecutive cells vertically, horizontally, or diagonally. More precisely, it is guaranteed that c _ {i,j} satisfies all of the following conditions.

• c _ {i,1}=c _ {i,2}=c _ {i,3} does not hold for any 1\leq i\leq3.
• c _ {1,j}=c _ {2,j}=c _ {3,j} does not hold for any 1\leq j\leq3.
• c _ {1,1}=c _ {2,2}=c _ {3,3} does not hold.
• c _ {3,1}=c _ {2,2}=c _ {1,3} does not hold.

Takahashi will see the numbers written in each cell in random order. He will get disappointed when there is a line (vertical, horizontal, or diagonal) that satisfies the following condition.

• The first two squares he sees contain the same number, but the last square contains a different number.

Find the probability that Takahashi sees the numbers in all the squares without getting disappointed.

Constraints

• c _ {i,j}\in\lbrace1,2,3,4,5,6,7,8,9\rbrace\ (1\leq i\leq3,1\leq j\leq3)
• c _ {i,1}=c _ {i,2}=c _ {i,3} does not hold for any 1\leq i\leq3.
• c _ {1,j}=c _ {2,j}=c _ {3,j} does not hold for any 1\leq j\leq3.
• c _ {1,1}=c _ {2,2}=c _ {3,3} does not hold.
• c _ {3,1}=c _ {2,2}=c _ {1,3} does not hold.

Sample Input 1

3 1 9
2 5 6
2 7 1

Sample Output 1

0.666666666666666666666666666667

For example, if Takahashi sees c _ {3,1}=2,c _ {2,1}=2,c _ {1,1}=3 in this order, he will get disappointed.

On the other hand, if Takahashi sees c _ {1,1},c _ {1,2},c _ {1,3},c _ {2,1},c _ {2,2},c _ {2,3},c _ {3,1},c _ {3,2},c _ {3,3} in this order, he will see all numbers without getting disappointed.

The probability that Takahashi sees all the numbers without getting disappointed is \dfrac 23. Your answer will be considered correct if the absolute error from the true value is at most 10 ^ {-8}, so outputs such as 0.666666657 and 0.666666676 would also be accepted.

Sample Input 2

7 7 6
8 6 8
7 7 6

Sample Output 2

0.004982363315696649029982363316

Sample Input 3

3 6 7
1 9 7
5 7 5

Sample Output 3

0.4

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

There are N pieces of trash on the grid; the i-th piece is at cell (X_i, Y_i).

You are given Q queries, which you must process in order. Each query is of one of the following types:

• Type 1: Given in the format 1 x in the input. Report the number of trash pieces in the x-th row. Then, all trash pieces in the x-th row are removed from the grid.

• Type 2: Given in the format 2 y in the input. Report the number of trash pieces in the y-th column. Then, all trash pieces in the y-th column are removed from the grid.

Constraints

• 1 \leq H, W, N \leq 2 \times 10^5
• 1 \leq X_i \leq H
• 1 \leq Y_i \leq W
• If i \neq j, then (X_i, Y_i) \neq (X_j, Y_j).
• 1 \leq Q \leq 2 \times 10^5
• For a type 1 query, 1 \leq x \leq H.
• For a type 2 query, 1 \leq y \leq W.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
1
0
1
0

Initially, trash pieces are at cells (1, 2), (1, 3), (3, 4), (3, 1), (2, 2).

In the 1st query, the 1st row contains two pieces of trash at (1, 2) and (1, 3), so report 2. These pieces are then removed; the remaining trash is at (3, 4), (3, 1), (2, 2).

In the 2nd query, the 2nd row contains one piece of trash at (2, 2), so report 1. This piece is then removed; the remaining trash is at (3, 4), (3, 1).

In the 3rd query, the 2nd column contains no trash, so report 0.

In the 4th query, the 4th column contains one piece of trash at (3, 4), so report 1. This piece is then removed; the remaining trash is at (3, 1).

In the 5th query, the 2nd row contains no trash, so report 0.

Sample Input 2

1 2 1
1 2
7
2 1
2 1
2 1
2 1
2 1
2 1
2 1

Sample Output 2

0
0
0
0
0
0
0

Sample Input 3

4 4 16
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
7
2 1
1 1
2 2
1 2
2 3
1 3
2 4

Sample Output 3

4
3
3
2
2
1
1

Problem Statement

You are given a simple connected undirected graph G with N vertices and M edges.
The vertices and edges of G are numbered as vertices 1,2,\ldots,N and edges 1,2,\ldots,M, respectively, and edge i connects vertices U_i and V_i.
You can move bidirectionally between vertices connected by an edge in time 1.

Additionally, each vertex is either safe or dangerous, and this state is given by a string S of length N consisting of S and D.
Specifically, vertex i is safe when the i-th character (1\leq i\leq N) of S is S, and vertex i is dangerous when it is D.
It is guaranteed that there are at least two safe vertices and at least one dangerous vertex.

For each dangerous vertex v, find the following value:

The minimum possible time to start from some safe vertex, pass through v, and move to a safe vertex different from the starting vertex.

Constraints

• 3\leq N\leq 2\times 10^5
• N-1\leq M\leq 2\times 10^5
• 1\leq U_i,V_i\leq N
• U_i\neq V_i
• If i\neq j, then \{ U_i,V_i \}\neq \{ U_j,V_j \}.
• S is a string of length N consisting of S and D.
• N,M,U_i,V_i are all integers.
• G is connected.
• There are at least two safe vertices.
• There is at least one dangerous vertex.

Sample Input 1

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

Sample Output 1

2
3

The dangerous vertices are (in ascending order of vertex number) vertices 3 and 4.

For vertex 3, moving from vertex 1 \to vertex 3 \to vertex 2 (for example) satisfies the condition.
The time required for this movement is 2, and this is the minimum.
Therefore, print 2 on the 1st line.

For vertex 4, moving from vertex 1 \to vertex 3 \to vertex 4 \to vertex 5 (for example) satisfies the condition.
The time required for this movement is 3, and there is no way to move that satisfies the condition with time 2 or less, so this is the minimum.
Therefore, print 3 on the 2nd line.

Sample Input 2

3 2
1 2
2 3
SSD

Sample Output 2

3

The dangerous vertex is vertex 3.

Moving from vertex 1 \to vertex 2 \to vertex 3 \to vertex 2 (for example) satisfies the condition.
The time required for this movement is 3, and this is the minimum.
Note that movements such as vertex 2 \to vertex 3 \to vertex 2 do not satisfy the condition that the destination is "different from the starting vertex".

Problem Statement

You are given a sequence of N positive integers A = (A_1, A_2, \dots ,A_N), where each element is at least 2. Anna and Bruno play a game using these integers. They take turns, with Anna going first, performing the following operation.

• Choose an integer i \ (1 \leq i \leq N) freely. Then, freely choose a positive divisor x of A_i that is not A_i itself, and replace A_i with x.

The player who cannot perform the operation loses, and the other player wins. Determine who wins assuming both players play optimally for victory.

Constraints

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

Sample Input 1

3
2 3 4

Sample Output 1

Anna

For example, the game might proceed as follows. Note that this example may not necessarily represent optimal play by both players:

• Anna changes A_3 to 2.
• Bruno changes A_1 to 1.
• Anna changes A_2 to 1.
• Bruno changes A_3 to 1.
• Anna cannot operate on her turn, so Bruno wins.

Actually, for this sample, Anna always wins if she plays optimally.

Sample Input 2

4
2 3 4 6

Sample Output 2

Bruno