Problem Statement

You are given a positive integer N. Print an integer sequence of length L \coloneqq N(N+1)/2, A = (A_1, A_2, \ldots, A_L), that satisfies all of the following conditions.

• A contains exactly i occurrences of i for every i = 1, 2, \ldots, N.
• 1 \leq |A_i - A_{i+1}| \leq 2 for every i = 1, 2, \ldots, L. Here, A_{L+1} means A_1.

It can be proved that, under the Constraints of this problem, there is always an integer sequence A of length L that satisfies all of the above conditions.

Constraints

• 3 \leq N \leq 1000
• N is an integer.

Sample Input 1

4

Sample Output 1

1 3 4 2 4 3 4 2 4 3

The integer sequence A = (1, 3, 4, 2, 4, 3, 4, 2, 4, 3) contains exactly one 1, two 2s, three 3s, and four 4s, satisfying the first condition. The second condition is also satisfied, as follows:

• |A_1 - A_2| = |1 - 3| = 2
• |A_2 - A_3| = |3 - 4| = 1
• |A_3 - A_4| = |4 - 2| = 2
• |A_4 - A_5| = |2 - 4| = 2
• |A_5 - A_6| = |4 - 3| = 1
• |A_6 - A_7| = |3 - 4| = 1
• |A_7 - A_8| = |4 - 2| = 2
• |A_8 - A_9| = |2 - 4| = 2
• |A_9 - A_{10}| = |4 - 3| = 1
• |A_{10} - A_1| = |3 - 1| = 2

Problem Statement

You are given a connected undirected graph G with N vertices and M edges. For each i=1,2,\ldots,M, the i-th edge connects vertices a_i and b_i, and is colored red if c_i= R and blue if c_i= B.

Determine if there is a spanning tree of G that satisfies the following condition, and if so, display such a tree.

• For every i=1,2,\ldots,N,
  • if s_i = R, at least one red edge has vertex i as its endpoint;
  • if s_i = B, at least one blue edge has vertex i as its endpoint.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N-1 \leq M \leq 2 \times 10^5
• 1 \leq a_i \lt b_i \leq N
• c_i is R or B.
• (a_i,b_i,c_i) \neq (a_j,b_j,c_j) if i \neq j.
• The given graph is connected.
• s_i is R or B.
• N,M,a_i,b_i are integers.

Sample Input 1

3 3
1 2 R
1 3 B
2 3 B
RRB

Sample Output 1

Yes
2 1

Here we show that the spanning tree formed by the first and second edges of G satisfies the condition.

• s_1 = R, so for i=1, at least one red edge must have vertex 1 as its endpoint. The first edge of G is such an edge.
• s_2 = R, so for i=2, at least one red edge must have vertex 2 as its endpoint. The first edge of G is such an edge.
• s_3 = B, so for i=3, at least one blue edge must have vertex 3 as its endpoint. The second edge of G is such an edge.

Sample Input 2

3 4
1 2 R
1 2 B
1 3 B
2 3 B
RRR

Sample Output 2

No

Sample Input 3

8 16
5 7 B
2 7 R
1 6 R
1 4 R
6 7 R
4 6 B
4 8 R
2 3 R
3 5 R
6 7 B
2 6 B
5 6 R
1 3 B
4 5 B
2 7 B
1 8 B
BRBRRBRB

Sample Output 3

Yes
1 2 4 9 11 13 16

Sample Input 4

8 10
1 7 R
1 3 B
2 5 B
2 8 R
1 5 R
3 6 R
2 6 B
3 4 B
2 8 B
4 6 B
RRRBBBRB

Sample Output 4

No

Problem Statement

Takahashi and Aoki will play the following game.

1. For each i=1,2,\ldots,N in this order, do the following.
   • Write each integer from l_i through r_i once on the blackboard. (Here, l_i and r_i are non-negative integers from the input.)
2. While one or more integers are written on the blackboard, the players take turns doing the following, with Takahashi going first.
   • Choose and perform exactly one of the following two operations.
     • Delete all even numbers written on the blackboard, and replace each remaining integer with half its value rounded down to an integer.
     • Delete all odd numbers written on the blackboard, and replace each remaining integer with half its value.
3. When no integer is written on the blackboard, the game ends and the last player to perform an operation wins.

It can be proved that the game ends in a finite number of operations if Takahashi and Aoki act optimally. Find the winner in this case.

Solve the above problem for T cases.

Constraints

• 1 \leq T \leq 10^4
• 1 \leq N \leq 10^4
• 0 \leq l_i \leq r_i \leq 10^{18}
• r_i \lt l_{i+1}
• The sum of N over the test cases in a single input is at most 10^4.
• All input values are integers.

Sample Input 1

3
2
1 2
5 7
1
0 100
10
1312150450968413 28316250877914571
74859962623690078 84324828731963974
148049062628894320 252509054433933439
269587449430302150 335408917861648766
349993004923078531 354979173822804781
522842184971407769 578223540024979436
585335723211047194 615812229161735895
645762258982631926 760713016476190622
779547116602436424 819875141880895723
822981260158260519 919845426262703496

Sample Output 1

Aoki
Aoki
Takahashi

Here is an example of how the game goes for the first test case.

• Each of 1,2,5,6,7 is written once on the blackboard.
• Takahashi chooses to delete the odd numbers. 1,5,7 are deleted from the blackboard, and the remaining integers 2,6 are replaced by half their values, that is, 1,3, respectively.
• Aoki chooses to delete the odd numbers. 1,3 are deleted from the blackboard, and no more integer is written on the blackboard, so the game ends and Aoki, who performed the last operation, wins.

Problem Statement

There are N squares: square 1, square 2, \ldots, square N. Each square is colored red or blue. The colors of the squares are represented by a string S of length N. Specifically, for each i = 1, 2, \ldots, N, square i is colored red if the i-th character of S is R, and blue if it is B. Square N is always colored blue.

Initially, each square has a chip of the same color as the square.

For each i = 1, 2, \ldots, N-1 in this order, let us perform the following operation.

• Choose an integer j such that i \lt j \leq N and square j is colored blue, and place the pile of chips on square i on top of the pile of chips on square j, keeping the order of the chips.

Print the number of possible sequences of colors of chips of the N-chip pile on square N from top to bottom after the above process, modulo 998244353.

Constraints

• 2 \leq N \leq 300
• N is an integer.
• S is a string of length N consisting of R and B.
• The N-th character of S is B.

Sample Input 1

4
RBRB

Sample Output 1

2

We use a string consisting of R and B, corresponding to red and blue, to represent the sequence of colors of the chips of a pile from top to bottom. Particularly, the sequence of colors of the chips of a 0-chip pile is an empty string \varepsilon.

Also, the state where the sequences of colors of chips of the piles on square 1, 2, 3, 4 are S_1, S_2, S_3, S_4, respectively, is called as state (S_1, S_2, S_3, S_4).

The following process yields RRBB as the sequence of colors of chips of the pile on square 4.

• First, on each square, place a chip of the same color as the square, resulting in state ( R , B , R , B ).
• Place the pile of chips on square 1 on top of the pile of chips on square 2, resulting in state (\varepsilon, RB , R , B ).
• Place the pile of chips on square 2 on top of the pile of chips on square 4, resulting in state (\varepsilon, \varepsilon, R , RBB ).
• Place the pile of chips on square 3 on top of the pile of chips on square 4, resulting in state (\varepsilon, \varepsilon, \varepsilon, RRBB ).

The following process yields RBRB as the sequence of colors of chips of the pile on square 4.

• First, on each square, place a chip of the same color as the square, resulting in state ( R , B , R , B ).
• Place the pile of chips on square 1 on top of the pile of chips on square 4, resulting in state (\varepsilon, B , R , RB ).
• Place the pile of chips on square 2 on top of the pile of chips on square 4, resulting in state (\varepsilon, \varepsilon, R , BRB ).
• Place the pile of chips on square 3 on top of the pile of chips on square 4, resulting in state (\varepsilon, \varepsilon, \varepsilon, RBRB ).

The above two, RRBB and RBRB, are the only possible sequences of colors of chips of the pile on square 4 from top to bottom after the process in the problem.

Sample Input 2

20
RRBRRRBBRBBBBRBRBRBB

Sample Output 2

92378

Problem Statement

You are given a positive integer N and integer sequences of length N: A=(a_1,\ldots,a_N) and B=(b_1,\ldots,b_N).
Let X be the multiset of N^2 instances (a_i+b_j)(1 \leq i,j \leq N).

For an N \times N matrix M whose elements are integers between -10^{18} and 10^{18}, inclusive, we define the score as follows.

• Let S be the multiset of N^2 instances, each of which is the sum of the 2N-1 elements in the i-th row or j-th column of M (1 \leq i,j \leq N). Then, the score is the sum of \min(the multiplicity of z in X, the multiplicity of z in S) over all integers z.

Find a matrix M with the maximum score.

Solve the above problem for T cases.

Constraints

• 1 \leq T \leq 2.5 \times 10^5
• 1 \leq N \leq 500
• -10^9 \leq a_i,b_i \leq 10^9
• The sum of N^2 over the test cases in a single input is at most 2.5 \times 10^5.
• All input values are integers.

Sample Input 1

3
1
5
-10
2
0 -1
8 -11
3
20 23 26
1 2 3

Sample Output 1

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

For the input and output in the first case, X=\{-5\}, S=\{-5\}, for a score of 1.
For the input and output in the second case, X=\{8,-11,7,-12\}, S=\{7,8,-11,-10\}, for a score of 3.
For the input and output in the third case, X=\{21,22,23,24,25,26,27,28,29\}, S=\{28,21,26,23,25,27,24,29,22\}, for a score of 9.

Problem Statement

You are given a positive integer N. Print the number, modulo 998244353, of sequences A of length 3N that contain each integer from 1 through N three times and satisfy the following condition.

• A has no contiguous subsequence of length N that is a permutation of the sequence (1, 2, \ldots, N).

Constraints

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

Sample Input 1

3

Sample Output 1

132

For instance, A = (1, 3, 3, 2, 2, 2, 1, 1, 3) satisfies the condition in the problem statement. On the other hand, A = (1, 3, 3, 2, 2, 3, 1, 1, 2) does not, because the 5-th, 6-th, 7-th elements of A form a contiguous subsequence that is a permutation of the sequence (1, 2, 3).

Sample Input 2

123456

Sample Output 2

31984851