Problem Statement

You are given a string S of even length consisting of lowercase English letters. Let |S| be the length of S, and S_i be the i-th character of S.

Perform the following operation for each i = 1, 2, \ldots, \frac{|S|}{2} in this order, and print the final S.

• Swap S_{2i-1} and S_{2i}.

Constraints

• S is a string of even length consisting of lowercase English letters.
• The length of S is at most 100.

Sample Input 1

abcdef

Sample Output 1

badcfe

Initially, S = abcdef.
Performing the operation for i = 1 swaps S_1 and S_2, making S = bacdef.
Performing the operation for i = 2 swaps S_3 and S_4, making S = badcef.
Performing the operation for i = 3 swaps S_5 and S_6, making S = badcfe.
Thus, badcfe should be printed.

Sample Input 2

aaaa

Sample Output 2

aaaa

Sample Input 3

atcoderbeginnercontest

Sample Output 3

taocedbrgeniencrnoetts

Problem Statement

There are N people whose IDs are 1, 2, \ldots, and N.

Each of person 1, person 2, \ldots, and person N performs the following action once in this order:

• If person i's ID has not been called out yet, call out person A_i's ID.

Enumerate the IDs of all the people whose IDs are never called out until the end in ascending order.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq N
• A_i \neq i
• All values in the input are integers.

Sample Input 1

5
3 1 4 5 4

Sample Output 1

2
2 4

The five people's actions are as follows.

• Person 1's ID has not been called out yet, so person 1 calls out person 3's ID.
• Person 2's ID has not been called out yet, so person 2 calls out person 1's ID.
• Person 3's ID has already been called out by person 1, so nothing happens.
• Person 4's ID has not been called out yet, so person 4 calls out person 5's ID.
• Person 5's ID has already been called out by person 4, so nothing happens.

Therefore, person 2 and 4's IDs are not called out until the end.

Sample Input 2

20
9 7 19 7 10 4 13 9 4 8 10 15 16 3 18 19 12 13 2 12

Sample Output 2

10
1 2 5 6 8 11 14 17 18 20

Problem Statement

There is a grid with H horizontal rows and W vertical columns. For two integers i and j such that 1 \leq i \leq H and 1 \leq j \leq W, the square at the i-th row from the top and j-th column from the left (which we denote by (i, j)) has an integer A_{i, j} written on it.

Takahashi is currently at (1,1). From now on, he repeats moving to an adjacent square to the right of or below his current square until he reaches (H, W). When he makes a move, he is not allowed to go outside the grid.

Takahashi will be happy if the integers written on the squares he visits (including initial (1, 1) and final (H, W)) are distinct. Find the number of his possible paths that make him happy.

Constraints

• 2 \leq H, W \leq 10
• 1 \leq A_{i, j} \leq 10^9
• All values in the input are integers.

Sample Input 1

3 3
3 2 2
2 1 3
1 5 4

Sample Output 1

3

There are six possible paths:

• (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 2, 3, 4, so he will not be happy.
• (1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
• (1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
• (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
• (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
• (1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.

Thus, the third, fifth, and sixth paths described above make him happy.

Sample Input 2

10 10
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

Sample Output 2

48620

In this example, every possible path makes him happy.

Problem Statement

There are N ropes numbered 1 through N. One end of each rope is painted red, and the other is painted blue.

You are going to perform M operations of tying ropes. In the i-th operation, you tie the end of rope A_i painted B_i with the end of rope C_i painted D_i, where R means red and B means blue. For each rope, an end with the same color is not tied multiple times.

Find the number of groups of connected ropes that form cycles, and the number of those that do not, after all the operations.

Here, a group of connected ropes \lbrace v_0, v_1, \ldots, v_{x-1} \rbrace is said to form a cycle if one can rearrange the elements of v so that, for each 0 \leq i < x, rope v_i is tied to rope v_{(i+1) \bmod x}.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i, C_i \leq N
• (A_i, B_i) \neq (A_j, B_j), (C_i, D_i) \neq (C_j, D_j) (i \neq j)
• (A_i, B_i) \neq (C_j, D_j)
• N, M, A_i, and C_i are integers.
• B_i is R or B, and so is D_i.

Sample Input 1

5 3
3 R 5 B
5 R 3 B
4 R 2 B

Sample Output 1

1 2

There are three groups of connected ropes: \lbrace 1 \rbrace, \lbrace 2,4 \rbrace, and \lbrace 3,5 \rbrace.

The group of ropes \lbrace 3,5 \rbrace forms a cycle, while the groups of rope \lbrace 1 \rbrace and ropes \lbrace 2,4 \rbrace do not. Thus, X = 1 and Y = 2.

Sample Input 2

7 0

Sample Output 2

0 7

Sample Input 3

7 6
5 R 3 R
7 R 4 R
4 B 1 R
2 R 3 B
2 B 5 B
1 B 7 B

Sample Output 3

2 1

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

Given an integer N not less than 2, find the number of integers b not less than 2 such that:

• when N is written in base b, every digit is 0 or 1.

Find the answer for T independent test cases.

It can be proved that there is a finite number of desired integers b not less than 2 under the constraints of this problem.

Constraints

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

Sample Input 1

3
12
2
36

Sample Output 1

4
1
5

For the first test case, four b's satisfy the condition in the problem statement: b = 2, 3, 11, 12. Indeed, when N=12 is written in base 2, 3, 11, and 12, it becomes 1100, 110, 11 and 10, respectively.

Problem Statement

You are given a length-N sequence (A_1, A_2, \ldots, A_N) of positive integers, and Q queries about the sequence.

For each q = 1, 2, \ldots, Q, the q-th query gives you an integer pair (l_q, r_q);
print the number of integer triplets (i, j, k) such that

• l_q \leq i \lt j \lt k \leq r_q, and
• A_i = A_j = A_k.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq 2 \times 10^5
• 1 \leq l_q \leq r_q \leq N
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

5
2
4
0

For the first query, there are five triplets of integers that satisfy the conditions in the problem statement: (1, 5, 9), (4, 6, 8), (4, 6, 10), (4, 8, 10), and (6, 8, 10).

Sample Input 2

20 10
2 2 2 2 1 1 2 2 1 1 1 2 1 2 1 2 2 1 2 1
12 16
17 18
12 18
4 9
13 13
2 5
6 13
2 14
7 14
8 12

Sample Output 2

1
0
5
2
0
1
11
55
8
1

Problem Statement

You are given a tree with N vertices numbered 1 through N. The i-th edge connects vertex A_i and vertex B_i.

Find the minimum integer K such that you can paint each vertex in a color so that the following two conditions are satisfied. You may use any number of colors.

• For each color, the set of vertices painted in the color is connected and forms a simple path.
• For all simple paths on the tree, there are at most K distinct colors of the vertices in the path.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• The given graph is a tree.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

3

If K=3, the conditions can be satisfied by painting vertices 1,2,3,4, and 5 in color 1, vertex 6 in color 2, and vertex 7 in color 3. If K \leq 2, there is no way to paint the vertices to satisfy the conditions, so the answer is 3.

Sample Input 2

6
3 5
6 4
6 3
4 2
1 5

Sample Output 2

1

Sample Input 3

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

Sample Output 3

3