Problem Statement

For a string T=T_1T_2\dots T_n of length n\ (2\leq n) consisting of A and B, we define a string f(T) of length n-1 as follows.

• Let a_1 < a_2 < \dots < a_{m} be the indices i\ (1\leq i \leq n-1) such that T_i={}A, and b_1 < b_2 < \dots < b_k be the indices i\ (1\leq i \leq n-1) such that T_i={}B. Then, let f(T)=T_{a_1+1}T_{a_2+1}\dots T_{a_m+1}T_{b_1+1}T_{b_2+1}\dots T_{b_k+1}.

For example, for the string T={}ABBABA, the indices i\ (1\leq i \leq 5) with T_i={}A are i=1,4, and the indices i\ (1\leq i \leq 5) with T_i={}B are i=2,3,5, so f(T) is T_{1+1}T_{4+1}T_{2+1}T_{3+1}T_{5+1}={}BBBAA.

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

Find S after replacing S with f(S) (N-1) times.

You have T test cases to solve.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 3 \times 10^5
• S is a string of length N consisting of A and B.
• All numbers in the input are integers.
• The sum of N over the test cases in a single input file is at most 3 \times 10^5.

Sample Input 1

3
2
AB
3
AAA
4
ABAB

Sample Output 1

B
A
A

In the first test case, S changes as AB{}\rightarrow {}B.

In the second test case, S changes as AAA{} \rightarrow {}AA{} \rightarrow {}A.

In the third test case, S changes as ABAB{}\rightarrow {}BBA{} \rightarrow {}BA{} \rightarrow {}A.

Problem Statement

There is a permutation A=(A_1,A_2,\dots,A_N) of the integers from 1 to N. Initially, we have A_i=i\ (1\leq i \leq N).

Takahashi will perform the following operation on this sequence K times.

• Choose an integer k such that 0 \leq k < N. Take the last k terms of A and insert them among the first N-k. More precisely, replace A with any permutation A' of the N integers that satisfies the following conditions.
  • (A_1,A_2,\dots,A_{N-k}) is a (not necessarily contiguous) subsequence of A'.
  • (A_{N-k+1},A_{N-k+2},\dots,A_{N}) is a (not necessarily contiguous) subsequence of A'.

The cost of the series of operations is \sum_{i=1}^{K}k_iC_i, where k_i is the k chosen in the i-th operation.

Takahashi wants to perform K operations so that A=(P_1,P_2,\dots,P_N) afterward.

Determine whether it is possible to perform such a series of operations. If it is possible, find its minimum cost.

Constraints

• 2 \leq N \leq 100
• 1 \leq K \leq 100
• 1 \leq C_i \leq 10^9
• (P_1,P_2,\dots,P_N) is a permutation of the integers from 1 to N.
• All input values are integers.

Sample Input 1

4 1
3
3 1 2 4

Sample Output 1

6

By choosing k=2, and inserting A_3=3 before A_1,A_2 and A_4=4 after A_1,A_2, we can make A=(3,1,2,4), which satisfies A=(P_1,P_2,P_3,P_4). The cost of this operation is 2 \times C_1 = 6.

It can be proved that the minimum cost of performing operations so that A=(P_1,P_2,P_3,P_4) afterward is 6.

Sample Input 2

4 1
3
4 3 2 1

Sample Output 2

-1

It is impossible to perform operations so that A=(P_1,P_2,P_3,P_4) afterward.

Sample Input 3

20 10
874735445 684260477 689935252 116941558 915603029 923404262 843759669 656978932 286318130 255195090
11 15 20 10 6 8 18 2 12 4 9 13 19 3 16 7 14 17 5 1

Sample Output 3

7372920743

Problem Statement

You are given an integer sequence of length N: A=(A_1,A_2,\dots,A_N).

Find the K smallest positive integers X that satisfy the following condition.

• There is no non-empty (not necessarily contiguous) subsequence of A whose elements sum to X.

Constraints

• 1 \leq N \leq 60
• 1 \leq K \leq 1000
• 1 \leq A_i \leq 10^{15}
• All input values are integers.

Sample Input 1

3 3
1 2 5

Sample Output 1

4 9 10

The subsequences of A are (1),(2),(1,2),(5),(1,5),(2,5),(1,2,5), and their respective sums are 1,2,3,5,6,7,8. Therefore, for X=1,2,3,5,6,7,8, there are subsequences of A whose elements sum to X.

On the other hand, for X=4,9,10, there is no subsequence of A whose elements sum to X.

Sample Input 2

20 10
324 60 1 15 60 15 1 60 319 1 327 1 2 60 2 345 1 2 2 15

Sample Output 2

14 29 44 59 74 89 104 119 134 149

Problem Statement

Takahashi, with a notepad, is standing at the origin (0,0) of a two-dimensional plane. His notepad has N even numbers D_i\ (1\leq i \leq N) written.

Takahashi will perform the following actions N times on the plane.

• He chooses and erases one even number written on the notepad. Let d be the chosen even number. He then moves to a point exactly d distance away in terms of Manhattan distance. More precisely, if Takahashi is currently at the coordinates (x,y), he moves to a point (x',y') such that |x-x'|+|y-y'|=d.

After performing N actions, Takahashi must return to the origin (0,0).

Determine if it is possible to perform N actions in such a way. If it is possible, find the minimum value of \displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|), where (x_i,y_i) are the coordinates where Takahashi is located after the i-th action (we can prove that this value is an integer).

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq D_i \leq 2 \times 10^5
• D_i\ (1\leq i \leq N) is even.
• All input values are integers.

Sample Input 1

3
2 4 6

Sample Output 1

4

If Takahashi erases 2,6,4 from his notepad for the first to third actions, respectively, and moves as (0,0)\rightarrow (0,2) \rightarrow (-4,0) \rightarrow (0,0), then \displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|) is 4, which is the minimum.

Sample Input 2

5
2 2 2 2 6

Sample Output 2

3

If Takahashi erases 2,2,6,2,2 from his notepad for the first to fifth actions, respectively, and moves as (0,0)\rightarrow (\frac{1}{2},\frac{3}{2})\rightarrow (0,3) \rightarrow (0,-3) \rightarrow (-\frac{1}{2},-\frac{3}{2}) \rightarrow (0,0), then \displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|) is 3, which is the minimum.

Takahashi can also move to non-grid points.

Sample Input 3

2
2 200000

Sample Output 3

-1

Takahashi cannot return to the origin after performing N actions as described above.

Problem Statement

You are given an odd number N and a non-negative integer K.

Find the number, modulo 998244353, of sequences of integer pairs ((L_1,R_1),(L_2,R_2),\dots,(L_N,R_N)) satisfying all of the following conditions.

• (L_1,R_1,L_2,R_2,\dots,L_N,R_N) is a permutation of the integers from 1 to 2N.
• L_1 \leq L_2 \leq \dots \leq L_N.
• L_i \leq R_i \ (1 \leq i \leq N).
• There are exactly K indices i\ (1\leq i \leq N) such that L_i+1=R_i.
• There is a rooted binary tree T with N vertices numbered from 1 to N such that the following holds:
  • vertices i and j have an ancestor-descendant relationship in T \iff intervals [L_i,R_i] and [L_j,R_j] intersect.

Here, a rooted binary tree is a rooted tree where each vertex has 0 or 2 children. Vertices i and j are said to have an ancestor-descendant relationship in a tree T if either vertex j exists on the simple path connecting the root to vertex i, or vice versa.

Constraints

• 1 \leq N < 2 \times 10^5
• 0 \leq K \leq N
• N is odd.
• All input values are integers.

Sample Input 1

3 1

Sample Output 1

2

For example, if (L_1,R_1)=(1,5),(L_2,R_2)=(2,3),(L_3,R_3)=(4,6), then i=2 is the only pair with L_i+1=R_i. Also, the fifth condition is satisfied by a tree where vertex 1 is the root, and its children are vertices 2 and 3.

Sample Input 2

1 0

Sample Output 2

0

Sample Input 3

521 400

Sample Output 3

0

Sample Input 4

199999 2023

Sample Output 4

283903125

Problem Statement

There are N decks of cards, each card in which has an integer between 1 and M, inclusive, written on it. The i-th deck (1\leq i \leq N) contains K_i cards, and the number written on the j-th card from the top is A_{i,j}\ (1\leq j \leq K_i).

Initially, the integers written on the cards satisfy the following conditions:

• For each integer x\ (1\leq x \leq M), there are exactly two cards with x written on them, each in a different deck.
• The integers written on the top cards of all the decks are pairwise different.

We can perform the following operation on the N decks:

• Choose a deck that still has cards and discard the top card. After discarding, the integers written on the top cards of the decks that still have cards must remain pairwise different.

Determine the maximum number of times this operation can be performed.

Constraints

• 2 \leq N \leq M
• 2 \leq M \leq 2 \times 10^5
• 1 \leq K_i \leq M
• 1 \leq A_{i,j} \leq M
• For each integer x\ (1\leq x \leq M), there are exactly two pairs (i,j) such that x=A_{i,j}, and the two values of i are different.
• A_{i,1}\ (1\leq i \leq N) are pairwise different.
• All input values are integers.

Sample Input 1

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

Sample Output 1

1

If you initially perform the operation on the first deck, the numbers on the cards of this deck become 2, 3, 4 in order from the top. After this, you may not perform the operation again on the first deck because both the first and second decks would have 3 on their top cards. Similarly, you cannot perform the operation on the second deck either. Therefore, if you start by performing the operation on the first deck, you can only do it once.

Even if you start by performing the operation on the second deck, you can only do it once. Therefore, the answer is 1.

Sample Input 2

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

Sample Output 2

12

By operating properly, it is possible to discard all the cards.

Sample Input 3

3 3
2 1 2
2 2 3
2 3 1

Sample Output 3

0

There are cases when no operation can be performed.

Sample Input 4

12 40
4 35 39 11 21
7 31 29 16 15 30 32 34
4 21 27 38 40
11 17 28 26 23 33 22 3 36 8 1 20
1 30
4 40 38 24 6
8 8 36 9 10 5 7 20 4
10 5 10 9 3 22 33 23 26 28 17
4 15 16 29 31
11 19 13 12 18 25 2 39 35 7 14 37
3 4 1 14
13 24 27 11 2 25 18 12 13 19 32 37 6 34

Sample Output 4

53