Problem Statement

You are given three digits A,B,C between 1 and 9, inclusive.

Find the maximum value among all 3-digit integers that can be formed by arranging A,B,C in any order and concatenating them.

Constraints

• A,B,C are digits between 1 and 9, inclusive.

Sample Input 1

3 2 4

Sample Output 1

432

There are six 3-digit integers that can be formed by arranging A,B,C in any order and concatenating them: 324, 342, 234, 243, 432, 423; the maximum value among them is 432.

Sample Input 2

7 7 7

Sample Output 2

777

Only 777 can be formed.

Sample Input 3

9 1 9

Sample Output 3

991

Problem Statement

You are given an integer N. Compute and output the value of 2^N-2N.

Constraints

• N is an integer between 1 and 11, inclusive.

Sample Input 1

1

Sample Output 1

0

The value of N given in this input is 1, so output the value of 2^1 - 2 \times 1, which is 0.

Sample Input 2

2

Sample Output 2

0

The value of N given in this input is 2, so output the value of 2^2 - 2 \times 2, which is 0.

Sample Input 3

11

Sample Output 3

2026

The value of N given in this input is 11, so output the value of 2^{11} - 2 \times 11, which is 2026.

Problem Statement

Takahashi is at the origin of a number line. He wants to reach a goal at coordinate X.

There is a wall at coordinate Y, which Takahashi cannot go beyond at first.
However, after picking up a hammer at coordinate Z, he can destroy that wall and pass through.

Determine whether Takahashi can reach the goal. If he can, find the minimum total distance he needs to travel to do so.

Constraints

• -1000 \leq X,Y,Z \leq 1000
• X, Y, and Z are distinct, and none of them is 0.
• All values in the input are integers.

Sample Input 1

10 -10 1

Sample Output 1

10

Takahashi can go straight to the goal.

Sample Input 2

20 10 -10

Sample Output 2

40

The goal is beyond the wall. He can get there by first picking up the hammer and then destroying the wall.

Sample Input 3

100 1 1000

Sample Output 3

-1

Problem Statement

You are given a grid with N rows and N columns. An integer A_{i, j} is written on the square at the i-th row from the top and j-th column from the left. Here, it is guaranteed that A_{i,j} is either 0 or 1.

Shift the integers written on the outer squares clockwise by one square each, and print the resulting grid.

Here, the outer squares are those in at least one of the 1-st row, N-th row, 1-st column, and N-th column.

Constraints

• 2 \le N \le 100
• 0 \le A_{i,j} \le 1(1 \le i,j \le N)
• All input values are integers.

Sample Input 1

4
0101
1101
1111
0000

Sample Output 1

1010
1101
0111
0001

We denote by (i,j) the square at the i-th row from the top and j-th column from the left.

The outer squares, in clockwise order starting from (1,1), are the following 12 squares: (1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4),(4,3),(4,2),(4,1),(3,1), and (2,1).

The sample output shows the resulting grid after shifting the integers written on those squares clockwise by one square.

Sample Input 2

2
11
11

Sample Output 2

11
11

Sample Input 3

5
01010
01001
10110
00110
01010

Sample Output 3

00101
11000
00111
00110
10100

Problem Statement

We will call a sequence of length N where each of 1,2,\dots,N occurs once as a permutation of length N.
Given a permutation of length N, P = (p_1, p_2,\dots,p_N), print a permutation of length N, Q = (q_1,\dots,q_N), that satisfies the following condition.

• For every i (1 \leq i \leq N), the p_i-th element of Q is i.

It can be proved that there exists a unique Q that satisfies the condition.

Constraints

• 1 \leq N \leq 2 \times 10^5
• (p_1,p_2,\dots,p_N) is a permutation of length N (defined in Problem Statement).
• All values in input are integers.

Sample Input 1

3
2 3 1

Sample Output 1

3 1 2

The permutation Q=(3,1,2) satisfies the condition, as follows.

• For i = 1, we have p_i = 2, q_2 = 1.
• For i = 2, we have p_i = 3, q_3 = 2.
• For i = 3, we have p_i = 1, q_1 = 3.

Sample Input 2

3
1 2 3

Sample Output 2

1 2 3

If p_i = i for every i (1 \leq i \leq N), we will have P = Q.

Sample Input 3

5
5 3 2 4 1

Sample Output 3

5 3 2 4 1

Problem Statement

You are given a string S consisting of uppercase English letters.
Apply the following procedure to S, and then output the resulting string:

As long as the string contains WA as a (contiguous) substring, repeat the following operation:

• Among all occurrences of WA in the string, replace the leftmost one with AC.

It can be proved under the constraints of this problem that this operation is repeated at most a finite number of times.

Constraints

• S is a string of uppercase English letters with length between 1 and 3\times 10^5, inclusive.

Sample Input 1

WACWA

Sample Output 1

ACCAC

Initially, the string is S= WACWA.
This string contains WA as a substring in two places: from the 1st to the 2nd character, and from the 4th to the 5th character.
In the first operation, we replace the leftmost occurrence (the substring from the 1st to the 2nd character) with AC, resulting in ACCWA.
After the first operation, the string contains WA as a substring in exactly one place: from the 4th to the 5th character.
In the second operation, we replace it with AC, resulting in ACCAC.
Since ACCAC does not contain WA as a substring, the procedure ends. Therefore, we output ACCAC.

Sample Input 2

WWA

Sample Output 2

ACC

Initially, the string is S= WWA.
This string contains WA as a substring in exactly one place: from the 2nd to the 3rd character.
In the first operation, we replace it with AC, resulting in WAC.
Then, after the first operation, the string contains WA in exactly one place: from the 1st to the 2nd character.
In the second operation, we replace it with AC, resulting in ACC.
Since ACC does not contain WA as a substring, the procedure ends. Therefore, we output ACC.

Sample Input 3

WWWWW

Sample Output 3

WWWWW

Since S does not contain WA as a substring from the start, no operations are performed and the procedure ends immediately. Therefore, we output WWWWW.

Problem Statement

There is a sequence A = (A_0, A_1, \dots, A_{N - 1}) with N = 2^{20} terms. Initially, every term is -1.

Process Q queries in order. The i-th query (1 \leq i \leq Q) is described by an integer t_i such that t_i = 1 or t_i = 2, and another integer x_i, as follows.

• If t_i = 1, do the following in order.
  1. Define an integer h as h = x_i.
  2. While A_{h \bmod N} \neq -1, keep adding 1 to h. We can prove that this process ends after finite iterations under the Constraints of this problem.
  3. Replace the value of A_{h \bmod N} with x_i.
• If t_i = 2, print the value of A_{x_i \bmod N} at that time.

Here, for integers a and b, a \bmod b denotes the remainder when a is divided by b.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• t_i \in \{ 1, 2 \} \, (1 \leq i \leq Q)
• 0 \leq x_i \leq 10^{18} \, (1 \leq i \leq Q)
• There is at least one i (1 \leq i \leq Q) such that t_i = 2.
• All values in input are integers.

Sample Input 1

4
1 1048577
1 1
2 2097153
2 3

Sample Output 1

1048577
-1

We have x_1 \bmod N = 1, so the first query sets A_1 = 1048577.

In the second query, initially we have h = x_2, for which A_{h \bmod N} = A_{1} \neq -1, so we add 1 to h. Now we have A_{h \bmod N} = A_{2} = -1, so this query sets A_2 = 1.

In the third query, we print A_{x_3 \bmod N} = A_{1} = 1048577.

In the fourth query, we print A_{x_4 \bmod N} = A_{3} = -1.

Note that, in this problem, N = 2^{20} = 1048576 is a constant and not given in input.

Problem Statement

Given integers A, X, and M, find \displaystyle \sum_{i = 0}^{X-1} A^i, modulo M.

Constraints

• 1 \leq A, M \leq 10^9
• 1 \leq X \leq 10^{12}
• All values in the input are integers.

Sample Input 1

3 4 7

Sample Output 1

5

3^0 + 3^1 + 3^2 + 3^3 = 40, which equals 5 modulo 7, so 5 should be printed.

Sample Input 2

8 10 9

Sample Output 2

0

Sample Input 3

1000000000 1000000000000 998244353

Sample Output 3

919667211

Problem Statement

There is a tree T with N vertices. The vertices are labeled as vertex 1, vertex 2, \ldots, vertex N, and the edges are labeled as edge 1, edge 2, \ldots, edge (N-1).
Edge i (1\leq i\leq N-1) connects vertices U_i and V_i.
Each vertex has a weight; initially, the weight of every vertex is 1.

You are given Q queries to process in order. Each query is of one of the following two types:

• 1 x w : Increase the weight of vertex x by w.
• 2 y : If edge y were removed, the tree T would be split into two subtrees (connected components). For each subtree, let its weight be the sum of the weights of its vertices. Output the difference between the weights of the two subtrees.

For a query of the second type, it can be proved that removing any edge of T always splits it into exactly two subtrees.
Note that queries of the second type do not actually delete remove the edge.

Constraints

• 2 \leq N \leq 3 \times 10^5
• 1 \leq U_i, V_i \leq N
• 1 \leq Q \leq 3 \times 10^5
• 1 \leq x \leq N
• 1 \leq w \leq 1000
• 1 \leq y \leq N-1
• All input values are integers.
• The given graph is a tree.
• There is at least one query of the second type.

Sample Input 1

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

Sample Output 1

2
1
17

The structure of the tree T and the vertex numbering are as shown on the left of the figure below. Initially, the weight of every vertex is 1.

In the 1st query, consider deleting edge 1.
The tree splits into the subtree containing vertex 1 and the subtree containing vertex 2. The subtree with vertex 1 has weight 2; the subtree with vertex 2 has weight 4. Output the difference, 2 (figure below, right).

The 2nd query increases the weight of vertex 1 by 3.

In the 3rd query, consider deleting edge 1.
The subtree with vertex 1 has weight 5; the subtree with vertex 2 has weight 4. Output the difference, 1 (figure below, left).

The 4th query increases the weight of vertex 4 by 10.

In the 5th query, consider deleting edge 5.
The tree splits into the subtree containing vertex 4 and the subtree consisting only of vertex 6.
The subtree with vertex 4 has weight 18; the subtree with vertex 6 has weight 1. Output the difference, 17 (figure below, right).

Thus, output the answers to the queries of second type in order: 2, 1, and 17, separated by newlines.