Problem Statement

Consider a string t consisting only of characters A, B, and C. We can do the following operation with it:

• Choose any substring t[l:r] and any permutation (X, Y, Z) of characters (A,B,C). Here, t[l:r] denotes the substring formed by the l-th through the r-th characters of t, where l and r are of your choice. Then, replace each character A, B, and C in t[l:r] by X, Y, and Z, respectively.

For example, for a string t = ACBAAC, we can choose a substring t[3:6] and (X,Y,Z)=(C,B,A). After this operation, the string will become ACBCCA.

Alina likes strings in which all characters are the same. She defines the beauty of a string t as the minimum number of operations required to make all its characters equal.

You are given a string S of length N consisting only of characters A, B, and C. Answer Q queries. The i-th query is the following:

• Given integers L_i and R_i, find the beauty of the substring t=S[L_i:R_i].

Constraints

• 1 \le N \le 10^5
• S is a string of length N consisting only of characters A, B, and C.
• 1 \le Q \le 10^5
• 1 \le L_i \le R_i \le N
• All numbers in the input are integers.

Sample Input 1

6 4
ABCCCA
3 5
2 3
1 3
1 6

Sample Output 1

0
1
2
2

In the first query, the string is t = CCC, in which all letters are already equal. The answer is 0.

In the second query, the string is t = BC. We can change it to BB in one operation, by choosing a substring t[2:2] and (X,Y,Z)=(A,C,B).

In the third query, the string is t = ABC. We can change it to AAB in one operation, by choosing a substring t[2:3] and (X,Y,Z)=(C,A,B), and then to BBB in the next operation, by choosing a substring t[1:2] and (X,Y,Z)=(B,A,C).

Problem Statement

You have N balls of colors C_1, C_2, \ldots, C_N. Here, all colors are represented by an integer between 1 and N inclusive. You want to arrange the balls on a circle. After you do that, you will count the number of pairs of colors (X, Y) such that X < Y and there exist two adjacent balls of colors X and Y.

Find an arrangement that minimizes the number of such pairs. If there are many such arrangements, find any of them.

For example, for balls of colors 1, 1, 2, 3, if we arrange them as 1, 1, 2, 3, we get 3 pairs: (1, 2), (2, 3), (1, 3). If we arrange them as 1, 2, 1, 3, we get only 2 pairs: (1, 2), (1, 3).

Solve T test cases for each input file.

Constraints

• 1 \le T \le 5 \cdot 10^4
• 3 \le N \le 2 \cdot 10^5
• 1 \le C_i \le N
• The sum of N in one input file doesn't exceed 2\cdot 10^5.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

1 2 3 
2 1 3 1 
3 3 2 5 2 

Problem Statement

A teacher has a hidden permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\cdots,N). You are going to determine it.

To do this, you prepared a sequence of pairs of integers (A_1,B_1),(A_2,B_2),\ldots,(A_{N(N-1)/2},B_{N(N-1)/2}); this is a permutation of all pairs of the form (a,b) (1 \le a < b \le N). Now, you will go over the pairs from the beginning. For a pair (A_i, B_i), you will ask if P_{A_i}<P_{B_i}, and the teacher will tell you the answer. However, you will skip this question if you can already determine the answer to it from previous answers.

Find the number of permutations P, for which with your algorithm you will have to ask all \frac{N(N-1)}{2} questions, modulo 10^9+7.

Constraints

• 2 \le N \leq 400
• 1 \le A_i < B_i \le N
• (A_i,B_i) \neq (A_j,B_j) (i \neq j)
• All values in the input are integers.

Sample Input 1

2
1 2

Sample Output 1

2

Clearly, for any permutation P, you need to ask 1 question.

Sample Input 2

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

Sample Output 2

4

Consider P=(2,3,1,4) as an example. In this case, you will skip the third question since you know P_1 < P_2 and P_1 > P_3 from previous questions and you can determine P_2 > P_3. Therefore, P=(2,3,1,4) should not be counted.

Sample Input 3

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

Sample Output 3

0

Problem Statement

For an integer array A=(A_1, A_2, \ldots, A_{N + K-1}) (1 \leq A_i \leq N+K-1), let's construct an array B=(B_1, B_2, \ldots, B_N), where B_i is the number of distinct elements in A_i,A_{i+1},\ldots,A_{i+K-1}.

You are given B_1, B_2, \ldots, B_N. Determine if there exists an array A which could have produced such an array B, and if yes, construct one.

Solve T test cases for each input file.

Constraints

• 1 \le T \le 5 \cdot 10^4
• 2 \le N \le 2 \cdot 10^5
• 2 \le K \le 2 \cdot 10^5
• 1 \le B_i \le K
• The sum of N in one input file doesn't exceed 2\cdot 10^5.
• The sum of K in one input file doesn't exceed 2\cdot 10^5.
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

NO
YES
1 1 1 2 2 2 
YES
1 2 3 1 2 3 1 2 3 

Problem Statement

You have an N \times N grid board. You want to color all cells in 3 colors so that no two adjacent (edge-sharing) cells have the same color.

You have already painted the border of the board. Determine if you can color the rest of the board properly.

More precisely, you are given a string S of length 4N-4 consisting of characters 1, 2, and 3. The string denotes the colors of the cells on the border, starting from the cell (1, 1), in clockwise order. Strictly speaking, the i-th character of S denotes the color of the cell:

• (1, i) for 1 \le i \le N-1
• (i - (N-1), N) for N \le i \le 2N-2
• (N, 3N - 1 - i) for 2N-1 \le i \le 3N-3
• (4N-2 - i, 1) for 3N-2 \le i \le 4N-4.

Here, (r,c) denotes the cell in the r-th row and the c-th column.

It is guaranteed that no two adjacent cells on the border have the same color.

Solve T test cases for each input file.

Constraints

• 1 \le T \le 5 \cdot 10^4
• 3 \le N \le 2 \cdot 10^5
• S is a string of length 4N-4 consisting of characters 1, 2, and 3.
• S_i \neq S_{i+1} for 1 \le i \le 4N-5, and S_{4N-4} \neq S_1.
• The sum of N in one input file doesn't exceed 2\cdot 10^5.
• All numbers in the input are integers.

Sample Input 1

4
3
12312312
4
121212121212
7
321312312312121212121321
7
321312312312121312121321

Sample Output 1

NO
YES
NO
YES

It can be shown that there is no way to properly color the rest of the board in the first and the third test cases. The proper colorings for the second and fourth test cases are shown below.

Problem Statement

Given N, pos, val, find the number of permutations P=(P_1, P_2, \ldots, P_N) of (1,2,\ldots,N) that satisfy all of the following conditions, modulo 10^9+7:

• LIS(P) + LDS(P) = N+1
• P_{pos} = val

Here, LIS(P) denotes the length of the longest increasing subsequence of P, and LDS(P) denotes the length of the longest decreasing subsequence of P.

Constraints

• 1 \le N \le 5\cdot 10^6
• 1 \le pos, val \le N
• All values in the input are integers.

Sample Input 1

3 2 2

Sample Output 1

2

The following permutations satisfy the conditions: (1, 2, 3), (3, 2, 1).

Sample Input 2

4 1 1

Sample Output 2

6

The following permutations satisfy the conditions: (1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2).

Sample Input 3

5 2 5

Sample Output 3

11

Sample Input 4

2022 69 420

Sample Output 4

128873576