Problem Statement

You are given a string S of length N consisting of lowercase English letters. Determine whether it is possible to divide S into two or more consecutive substrings so that they are strictly increasing in lexicographical order.

To be precise, determine whether there is a sequence of strings t=(t_1,t_2,\dots,t_k) that satisfies all of the following conditions.

• The length of the sequence k is at least 2.

• t_i is not empty. (1 \le i \le k)

• Concatenating t_1,t_2,\dots,t_k in this order results in S.

• t_i is lexicographically smaller than t_{i+1} for every integer i such that 1 \le i < k.

You are given T test cases. Find the answer for each of them.

Constraints

• 1 \le T \le 2000
• 2 \le N \le 2000
• S is a string of length N consisting of lowercase English letters.
• The sum of N over all test cases in a single input does not exceed 2000.

Sample Input 1

5
4
abac
3
cac
2
ab
12
abababababab
5
edcba

Sample Output 1

Yes
No
Yes
Yes
No

For the first test case, you can divide S into a, ba, c.

For the second test case, there is no way to divide S into substrings so that they are strictly increasing in lexicographical order.

Problem Statement

You are given an integer sequence of length N: A=(A_1,A_2,\dots,A_N). You can perform the following operation any number of times (possibly zero).

• Choose an integer i such that 1 \le i \le N, and increase or decrease A_i by 1.

Your goal is to make at least M integers i(3 \le i \le N) satisfy A_1 \le A_i \le A_2. Find the minimum number of operations required to achieve this goal.

Constraints

• 3 \le N \le 2 \times 10^5
• 1 \le M \le N-2
• 1 \le A_i \le 10^9

Sample Input 1

3 1
2 3 5

Sample Output 1

2

You can make not less than one integer i(3 \le i \le N) satisfy A_1 \le A_i \le A_2 by performing the operation as follows.

• Choose i=3, and decrease A_i by 1.
• Choose i=2, and increase A_i by 1.

Since it is impossible to achieve the goal with less than 2 operation, the answer is 2.

Sample Input 2

5 2
1 4 2 3 5

Sample Output 2

0

You may already have achieved the goal from the start.

Sample Input 3

8 5
15 59 64 96 31 17 88 9

Sample Output 3

35

Problem Statement

Determine whether there is a length-N sequence of positive integers A=(A_1,A_2,\dots,A_N) that satisfies all of the following conditions, and if it exists, construct one.

• \sum_{i=1}^{N} \frac{1}{A_i} = 1
• All elements of A are distinct.
• 1 \le A_i \le 10^9(1 \le i \le N)

You are given T test cases. Find the answer for each of them.

Constraints

• 1 \le T \le 500
• 1 \le N \le 500

Sample Input 1

2
3
5

Sample Output 1

Yes
2 3 6 
Yes
3 4 5 6 20 

In the first test case, N=3.

A=(2,3,6) is valid because \frac{1}{2} + \frac{1}{3} + \frac{1}{6} = 1 and it satisfies all other conditions.

In the second test case, N=5.

A=(3,4,5,6,20) is valid because \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{20} = 1 and it satisfies all other conditions.

Note that, for example, A=(5,5,5,5,5) satisfies the first and third conditions, but it is invalid because it contains duplicated elements.

Problem Statement

Consider a directed graph G with N vertices numbered 1 to N that satisfies all of the following conditions.

• G is a tournament. In other words, G has no multi-edges or self-loops, and for any two vertices u,v of G, exactly one of the edges u \rightarrow v and v \rightarrow u exists.

• Among the edges of G, exactly M are directed from a vertex with a smaller number to a vertex with a larger number.

Find the total number of strongly connected components over all such directed graphs G, modulo 998244353.

Constraints

• 1 \le N \le 30
• 0 \le M \le \frac{N(N-1)}{2}

Sample Input 1

3 1

Sample Output 1

7

Below are the three directed graphs G that satisfy the conditions. The numbers of their strongly connected components are 3,1,3 from left to right, so the answer is 7.

Sample Input 2

6 2

Sample Output 2

300

Sample Input 3

25 156

Sample Output 3

902739687

Problem Statement

Alice and Bob are playing a game using a length-N sequence of non-negative integers A=(A_1,A_2,\dots,A_N).

Starting with Alice, they take turns performing the following operation. The player who cannot make a move first loses.

• Choose a non-negative integer X such that there is an integer i satisfying A_i > A_i \oplus X.
• For each 1 \le i \le N, replace A_i with \min(A_i,A_i \oplus X).

Determine who wins when both players play optimally.

Here, \oplus represents the bitwise XOR.

You are given T test cases. Find the answer for each of them.

Constraints

• 1 \le T \le 100
• 1 \le N \le 100
• 0 \le A_i \le 10^9

Sample Input 1

5
2
3 1
5
1 1 1 1 1
4
0 0 0 0
4
8 1 6 4
5
3 8 7 12 15

Sample Output 1

Bob
Alice
Bob
Bob
Alice

In the first test case, one possible game progression could be as follows.

• Alice chooses X=3. This choice is valid because 3 > 3 \oplus 3(=0) for i=1.
• A=(3,1) becomes A=(0,1).
• Bob chooses X=1. This choice is valid because 1 > 1 \oplus 1(=0) for i=2.
• A=(0,1) becomes A=(0,0).
• Since Alice cannot choose any X, the game ends.

In this case, Bob wins.

In the second test case, one possible game progression could be as follows.

• Alice chooses X=1. This choice is valid because 1 > 1 \oplus 1(=0) for i=1.
• A=(1,1,1,1,1) becomes A=(0,0,0,0,0).
• Since Bob cannot choose any X, the game ends.

In this case, Alice wins.

Problem Statement

PCT-kun created the following problem.

Increasing Problem

You are given a length-N sequence of non-negative integers A_1,A_2,\dots,A_N. You can perform the following operation any number of times (possibly zero).

• Choose an integer i such that 1 \le i \le N, and increase or decrease A_i by 1.

Your goal is to make A non-decreasing. Find the minimum number of operations required to achieve this goal.

Thinking that this problem is too easy to be placed at the end of the contest, PCT-kun has revised it as follows.

Many Increasing Problems

There are M^N integer sequences A of length N where all elements are between 1 and M, inclusive. Find the sum of the answers to Increasing Problem for all those sequences, modulo 998244353.

Solve Many Increasing Problems.

Constraints

• 1 \le N,M \le 10^5

Sample Input 1

2 2

Sample Output 1

1

Let us solve Increasing Problem for all sequences of length 2 where all elements are between 1 and 2, inclusive.

• For A=(1,1), the answer is 0.
• For A=(1,2), the answer is 0.
• For A=(2,1), the answer is 1.
• For A=(2,2), the answer is 0.

Therefore, the final answer is 0+0+1+0=1.

Sample Input 2

6 4

Sample Output 2

14668

Sample Input 3

163 702

Sample Output 3

20728656

Sample Input 4

98765 99887

Sample Output 4

103564942