Problem Statement

Determine if there is a segment that directly connects the points numbered a and b in the figure below.

Constraints

• 1 \leq a \lt b \leq 15
• a and b are integers.

Sample Input 1

1 2

Sample Output 1

Yes

In the figure in the Problem Statement, there is a segment that directly connects the points numbered 1 and 2, so Yes should be printed.

Sample Input 2

2 8

Sample Output 2

No

In the figure in the Problem Statement, there is no segment that directly connects the points numbered 2 and 8, so No should be printed.

Sample Input 3

14 15

Sample Output 3

No

Problem Statement

You are given a string S of length 3.
Print a character that occurs only once in S.
If there is no such character, print -1 instead.

Constraints

• S is a string of length 3 consisting of lowercase English letters.

Sample Input 1

pop

Sample Output 1

o

o occurs only once in pop.

Sample Input 2

abc

Sample Output 2

a

a, b, and c occur once each in abc, so you may print any of them.

Sample Input 3

xxx

Sample Output 3

-1

No character occurs only once in xxx.

Problem Statement

There are N stations, station 1, station 2, \ldots, station N, arranged in this order on a straight line.
Here, for 1\leq i\leq N-1, the distance between stations i and (i+1) is D_i.

For each pair of integers (i,j) satisfying 1\leq i<j\leq N, find the distance between stations i and j.
For the output format, refer to the Output section.

Constraints

• 2 \leq N \leq 50
• 1 \leq D_i \leq 100
• All input values are integers.

Sample Input 1

5
5 10 2 3

Sample Output 1

5 15 17 20
10 12 15
2 5
3

The distances between stations are as follows:

• The distance between stations 1 and 2 is 5.
• The distance between stations 1 and 3 is 5+10=15.
• The distance between stations 1 and 4 is 5+10+2=17.
• The distance between stations 1 and 5 is 5+10+2+3=20.
• The distance between stations 2 and 3 is 10.
• The distance between stations 2 and 4 is 10+2=12.
• The distance between stations 2 and 5 is 10+2+3=15.
• The distance between stations 3 and 4 is 2.
• The distance between stations 3 and 5 is 2+3=5.
• The distance between stations 4 and 5 is 3.

Thus, output as shown above.

Sample Input 2

2
100

Sample Output 2

100

Problem Statement

Takahashi has a calculator that initially displays 1.
He will perform N operations on the calculator.
In the i-th operation (1 \leq i \leq N), he multiplies the currently displayed number by a positive integer A_i.
However, the calculator can display at most K digits. If the result of the multiplication has (K+1) or more digits, the display shows 1 instead; otherwise, the result is shown correctly.

Find the number showing on the calculator after the N operations.

Constraints

• 1 \leq N \leq 100
• 1 \leq K \leq 18
• 1 \leq A_i < 10^K
• All input values are integers.

Sample Input 1

5 2
7 13 3 2 5

Sample Output 1

10

This calculator can display at most two digits and initially shows 1. Takahashi operates as follows:

• The 1st operation multiplies by 7. Since 1 \times 7 = 7, the calculator shows 7.
• The 2nd operation multiplies by 13. Since 7 \times 13 = 91, the calculator shows 91.
• The 3rd operation multiplies by 3. Since 91\times 3=273, which has three digits, the calculator shows 1.
• The 4th operation multiplies by 2. Since 1\times 2=2, the calculator shows 2.
• The 5th operation multiplies by 5. Since 2\times 5=10, the calculator shows 10.

Sample Input 2

2 1
2 5

Sample Output 2

1

Problem Statement

You have N keys numbered 1, 2, \dots, N.
Some of these are real keys, while the others are dummies.

There is a door, Door X, into which you can insert any number of keys. Door X will open if and only if at least K real keys are inserted.

You have conducted M tests on these keys. The i-th test went as follows:

• You inserted C_i keys A_{i,1}, A_{i,2}, \dots, A_{i,C_i} into Door X.
• The test result is represented by a single English letter R_i.
  • R_i = o means that Door X opened in the i-th test.
  • R_i = x means that Door X did not open in the i-th test.

There are 2^N possible combinations of which keys are real and which are dummies. Among these, find the number of combinations that do not contradict any of the test results.
It is possible that the given test results are incorrect and no combination satisfies the conditions. In such a case, report 0.

Constraints

• N, M, K, C_i, and A_{i,j} are integers.
• 1 \le K \le N \le 15
• 1 \le M \le 100
• 1 \le C_i \le N
• 1 \le A_{i,j} \le N
• A_{i,j} \neq A_{i,k} if j \neq k.
• R_i is o or x.

Sample Input 1

3 2 2
3 1 2 3 o
2 2 3 x

Sample Output 1

2

In this input, there are three keys and two tests were conducted.
Two correct keys are required to open Door X.

• In the first test, keys 1, 2, 3 were used, and Door X opened.
• In the second test, keys 2, 3 were used, and Door X did not open.

There are two combinations of which keys are real and which are dummies that do not contradict any of the test results:

• Key 1 is real, key 2 is a dummy, and key 3 is real.
• Key 1 is real, key 2 is real, and key 3 is a dummy.

Sample Input 2

4 5 3
3 1 2 3 o
3 2 3 4 o
3 3 4 1 o
3 4 1 2 o
4 1 2 3 4 x

Sample Output 2

0

As mentioned in the problem statement, the answer may be 0.

Sample Input 3

11 4 9
10 1 2 3 4 5 6 7 8 9 10 o
11 1 2 3 4 5 6 7 8 9 10 11 o
10 11 10 9 8 7 6 5 4 3 2 x
10 11 9 1 4 3 7 5 6 2 10 x

Sample Output 3

8

Problem Statement

N balls are lined up in a row from left to right. Initially, the i-th (1 \leq i \leq N) ball from the left has an integer i written on it.

Takahashi has performed Q operations. The i-th (1 \leq i \leq Q) operation was as follows.

• Swap the ball with the integer x_i written on it with the next ball to the right. If the ball with the integer x_i written on it was originally the rightmost ball, swap it with the next ball to the left instead.

Let a_i be the integer written on the i-th (1 \leq i \leq N) ball after the operations. Find a_1,\ldots,a_N.

Constraints

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

Sample Input 1

5 5
1
2
3
4
5

Sample Output 1

1 2 3 5 4

The operations are performed as follows.

• Swap the ball with 1 written on it with the next ball to the right. Now, the balls have integers 2,1,3,4,5 written on them, from left to right.
• Swap the ball with 2 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 3 written on it with the next ball to the right. Now, the balls have integers 1,2,4,3,5 written on them, from left to right.
• Swap the ball with 4 written on it with the next ball to the right. Now, the balls have integers 1,2,3,4,5 written on them, from left to right.
• Swap the ball with 5 written on it with the next ball to the left, since it is the rightmost ball. Now, the balls have integers 1,2,3,5,4 written on them, from left to right.

Sample Input 2

7 7
7
7
7
7
7
7
7

Sample Output 2

1 2 3 4 5 7 6

Sample Input 3

10 6
1
5
2
9
6
6

Sample Output 3

1 2 3 4 5 7 6 8 10 9

Problem Statement

Given a sequence of N positive integers A=(A_1,A_2,\dots,A_N), find every integer k between 1 and M (inclusive) that satisfies the following condition:

• \gcd(A_i,k)=1 for every integer i such that 1 \le i \le N.

Constraints

• All values in input are integers.
• 1 \le N,M \le 10^5
• 1 \le A_i \le 10^5

Sample Input 1

3 12
6 1 5

Sample Output 1

3
1
7
11

For example, 7 has the properties \gcd(6,7)=1,\gcd(1,7)=1,\gcd(5,7)=1, so it is included in the set of integers satisfying the requirement.
On the other hand, 9 has the property \gcd(6,9)=3, so it is not included in that set.
We have three integers between 1 and 12 that satisfy the condition: 1, 7, and 11. Be sure to print them in ascending order.

Problem Statement

You are given a length-N integer sequence A = (A_1, A_2, \ldots, A_N).

Your goal is to perform the following operation repeatedly so that for every length-L contiguous subarray of A, the sum is a multiple of M.

• Choose an integer i such that 1 \leq i \leq N, and increase the value of A_i by 1.

Find the minimum possible number of operations before achieving the goal.

Constraints

• 1 \leq N, M \leq 500
• 1 \leq L \leq N
• 0 \leq A_i < M
• All input values are integers.

Sample Input 1

4 5 3
4 2 1 3

Sample Output 1

4

By performing the operation once choosing i = 2, twice choosing i = 3, and once choosing i = 4, you get A = (4, 3, 3, 4) with a total of four operations, where every length-3 contiguous subarray sums to a multiple of 5.

Sample Input 2

7 10 4
7 0 9 1 6 4 2

Sample Output 2

10

Problem Statement

For a sequence X=(X_1,X_2\ldots,X_N) of length N consisting of positive integers, we define f(X) as follows:

• A tree with N vertices is said to be good if and only if the degree of the i-th (1 \leq i \leq N) vertex is X_i. If a good tree exists, f(X) is the maximum diameter of a good tree; if it doesn't, f(X)=0.

Here, the distance between two vertices is the minimum number of edges that must be traversed to travel from one vertex to the other, and the diameter of a tree is the maximum distance between two vertices.

Find the sum, modulo 998244353, of f(X) over all possible sequences X of length N consisting of positive integers. We can prove that the sum of f(X) is a finite value.

Given T test cases, find the answer for each of them.

Constraints

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

Sample Input 1

10
2
3
5
8
13
21
34
55
89
144

Sample Output 1

1
6
110
8052
9758476
421903645
377386885
881422708
120024839
351256142

If N=3,

for example,

• when X=(1,1,1), there is no tree with three vertices whose degrees are 1,1, and 1, so f(X)=0.
• When X=(2,1,1), the only possible tree is illustrated below. The diameter of this tree is 2, so f(X)=2.

For X=(2,1,1),(1,2,1),(1,1,2), we have f(X)=2; for other X, we have f(X)=0. Thus, the answer is 6.