Problem Statement

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

Each cell contains an integer. Initially, cell (i,j) contains the integer A_{i,j}.

You can repeatedly perform the following operation:

• Choose integers i and j such that 1\leq i, j\leq N and an integer x, and add x to A_{i,j}. The cost of this operation is |x|.

You are given a positive integer d. Your goal is to satisfy the following condition:

• The difference between the integers written in any two cells that are vertically or horizontally adjacent is at least d. More formally, the following two conditions are satisfied:
  • |A_{i,j}-A_{i+1,j}|\geq d for all integers i and j such that 1\leq i\leq N-1 and 1\leq j\leq N.
  • |A_{i,j}-A_{i,j+1}|\geq d for all integers i and j such that 1\leq i\leq N and 1\leq j\leq N-1.

Achieve this goal with a total cost of \frac12 dN^2 or less.

Constraints

• 2\leq N\leq 500
• 1\leq d\leq 1000
• -1000\leq A_{i,j}\leq 1000

Sample Input 1

3 5
-2 1 3
3 -4 -4
0 1 3

Sample Output 1

-2 8 3
3 -9 -4
-2 8 3

Perform the operation four times as follows to yield the grid shown in the sample output:

• Perform the operation with (i,j,x)=(1,2,7).
• Perform the operation with (i,j,x)=(2,2,-5).
• Perform the operation with (i,j,x)=(3,1,-2).
• Perform the operation with (i,j,x)=(3,2,7).

The total cost is 7+5+2+7=21, which is not greater than \frac{1}{2}dN^2=\frac{45}{2}.

Sample Input 2

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

Sample Output 2

0 4 6 1 3
3 1 3 6 1
5 3 0 3 5
2 6 3 1 3
4 0 5 3 6

Problem Statement

For a positive integer x, let f(x) denote the sum of its digits. For example, f(331)=3+3+1=7, f(2024)=2+0+2+4=8, and f(1)=1.

You are given a positive integer N. Print a positive integer x that satisfies all of the following conditions:

• 1\leq x< 10^{10000}
• f(2^{i-1}x)>f(2^ix) for all integers 1\leq i\leq N.

Constraints

• 1\leq N\leq 50

Sample Input 1

3

Sample Output 1

89

For x=89, it follows from f(x)=17, f(2x)=16, f(4x)=14, and f(8x)=10 that f(x)>f(2x)>f(4x)>f(8x), satisfying the conditions.

Some other integers that satisfy the conditions are x=539 and x=890.

Problem Statement

You are given a string S consisting of characters A and B.

On this string, you can repeatedly perform the following operation:

• Choose three consecutive characters in S that are equal to AAB or BAA, and delete those three characters from S (after deletion, the remaining characters are concatenated).

Find the maximum number of times you can perform this operation.

T test cases are given; solve each of them.

Constraints

• 1\leq T\leq 10^5
• S is a string consisting of A and B.
• 1\leq |S|\leq 10^6
• The sum of |S| over all test cases in a single input is at most 10^6.

Sample Input 1

10
AABAAAB
BAAAAABBA
A
B
ABA
BAA
AAAAAA
AAAABB
AABABBAABBABAAAABBAA
BBAAAAABAAAAABABAABA

Sample Output 1

2
3
0
0
0
1
0
2
5
6

For each of the first and second test cases, here is a possible way to perform the maximum number of operations:

• AABAAAB → AAAB → A
• BAAAAABBA → BAAABA → BAA → (empty string)

Problem Statement

You are given a string S of length N consisting of A and B. It is guaranteed that the number of As in S is at most \frac{N+1}{2}. Additionally, you are given a sequence of positive integers (x_1, \ldots, x_{N-1}).

On this string, you can repeatedly perform the following operation:

• Choose an integer i such that 1\leq i\leq N-1, and swap the i-th and (i+1)-th characters of S. The cost of this operation is x_i.

Your goal is to rearrange S so that no two As are adjacent. Find the minimum total cost required to achieve this goal.

T test cases are given; solve each of them.

Constraints

• 1\leq T\leq 10^5
• 2\leq N\leq 10^6
• S is a string of length N consisting of A and B.
• The number of As in S is at most \frac{N+1}{2}.
• 1\leq x_i \leq 10^6
• The sum of N over all test cases in a single input is at most 10^6.

Sample Input 1

5
4
BAAB
3 4 5
5
BBBBB
1 2 3 4
7
BAAABBB
8 7 6 5 4 3
7
BAAABBB
100 7 6 5 4 3
20
BAABAABBBABAAABBBABB
12 85 37 44 25 14 36 29 71 53 15 47 13 80 14 74 53 76 19

Sample Output 1

3
0
13
15
133

• For the first test case, performing the operation with i=1 changes S as BAAB → ABAB, achieving the goal. The total cost in this case is x_1=3.
• For the second test case, performing nothing achieves the goal. The total cost in this case is 0.
• For the third test case, performing the operation with i=1 and i=4 changes S as BAAABBB → ABAABBB → ABABABB, achieving the goal. The total cost in this case is x_1+x_4=13.
• For the fourth test case, performing the operation with i=4, i=3, and i=5 changes S as BAAABBB → BAABABB → BABAABB → BABABAB, achieving the goal. The total cost in this case is x_4+x_3+x_5=15.

Problem Statement

You are given a tree with N vertices numbered 1 to N. The i-th edge of the tree connects vertices u_i and v_i.

For each K=1, 2, \ldots, N, solve the following problem:

There are K stones numbered 1, 2, \ldots, K, with the stone numbered i placed on vertex i. You can repeatedly perform the following operation:

• Choose two vertices u and v connected by an edge such that u has a stone on it and v does not. Move the stone from u to v.

Find the number, modulo 998244353, of possible configurations of the stones after performing the operations. Two configurations are distinguished if and only if there is a stone whose position differs between those configurations.

T test cases are given; solve each of them.

Constraints

• 1\leq T\leq 10^5
• 1\leq N\leq 2\times 10^5
• 1\leq u_i, v_i\leq N
• The given graph is a tree.
• The sum of N over all test cases in a single input is at most 2\times 10^5.

Sample Input 1

1
4
1 2
1 3
1 4

Sample Output 1

4 12 4 1

Let us represent the configuration of stones by the sequence of vertices where the stones numbered 1, 2, \ldots, K are placed.

• For K=1, there are 4 possible configurations: (1), (2), (3), (4).
• For K=2, there are 12 possible configurations: (1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3).
• For K=3, there are 4 possible configurations: (1,2,3), (4,1,3), (4,2,1), (4,2,3).
• For K=4, there is 1 possible configuration: (1,2,3,4).

For K=3, refer to the following figure.

Sample Input 2

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

Sample Output 2

1
5 10 10 5 1
7 42 210 840 84 7 1
10 90 720 5040 30240 151200 604800 720 10 1

The tree given in each test case is as follows:

Problem Statement

A string is called a beautiful string if and only if it satisfies the following conditions:

• Every character is A, B, or C.
• No two adjacent characters are the same.

For example, AB and BCAC are beautiful strings, while BB and CBAAC are not.

You are given a beautiful string S. On this string, you can repeatedly perform the following operation.

• Operation: Swap two adjacent characters in S. Here, S must still be a beautiful string after the swap.

Find the lexicographically smallest string that S can become.

T test cases are given; solve each of them.

Constraints

• 1\leq T\leq 10^5
• S is a beautiful string.
• 1\leq |S|\leq 10^6
• The sum of |S| over all test cases in a single input is at most 10^6.

Sample Input 1

8
CAB
ACBCB
B
AC
BACBA
BABABA
ABCBCAC
CBABACABCBABABC

Sample Output 1

ABC
ABCBC
B
AC
ABABC
BABABA
ABCACBC
ABABACBCACBCBAB

For each of the first and second test cases, here is a possible way to lexicographically minimize S:

• CAB → ACB → ABC
• ACBCB → CABCB → CBACB → BCACB → BCABC → BACBC → ABCBC