Problem Statement

A string of length 2N that contains N occurrences of each of 0 and 1 is called a good string.

For good strings S and T, let \operatorname{dist}(S, T) denote the minimum number of swaps required to make S equal to T by swapping two adjacent characters of S zero or more times.

You are given good strings A, B, and C. Among all good strings X, find one that minimizes the value of

\[ \operatorname{dist}(A, X)+\operatorname{dist}(B, X)+\operatorname{dist}(C, X), \]

and output it together with the minimum value.

Constraints

• 1 \le N \le 2 \times 10^5
• Each of A, B, and C is a good string of length 2N.
• N is an integer.

Sample Input 1

2
1100
1010
0011

Sample Output 1

4
1010

If we choose 1010 as the good string X, then \operatorname{dist}(A, X), \operatorname{dist}(B, X), and \operatorname{dist}(C, X) are 1, 0, 3, respectively, and their sum is 4. The sum of the distances cannot be made smaller than 4.

Sample Input 2

3
101010
101010
101010

Sample Output 2

0
101010

Since the three input strings are all equal, choosing the same string as X makes the sum of the distances 0.

Problem Statement

You are given a length-N sequence of non-negative integers A=(A_1,A_2,\ldots,A_N).

Determine whether there exists a sequence B=(B_1,B_2,\ldots,B_N) that is a permutation of A that satisfies the following condition for every i=1,2,\ldots,N, and construct one such sequence if it exists.

• B_i is equal to the number of integers j satisfying 1 \le j < i and B_j < B_i.

Constraints

• 1 \le N \le 5 \times 10^5
• 0 \le A_i < N
• All input values are integers.

Sample Input 1

4
3 0 1 0

Sample Output 1

Yes
0 1 0 3

The output sequence is a permutation of A. For i=1,2,3,4, the number of elements to the left of B_i that are smaller than B_i is 0,1,0,3, respectively, which equals B_i.

Sample Input 2

3
0 2 2

Sample Output 2

No

Since there is only one element smaller than the value 2, no permutation satisfies the condition.

Sample Input 3

7
4 1 6 0 4 3 1

Sample Output 3

Yes
0 1 1 3 4 4 6

The output sequence is a permutation of A. For i=1,2,\ldots,7, the number of elements to the left of B_i that are smaller than B_i is 0,1,1,3,4,4,6, respectively, which equals B_i.

Problem Statement

You are given a string S of length N consisting of lowercase English letters. Let S_i denote the i-th character of S.

There are N islands arranged in a circle, numbered island 1, island 2, \ldots, island N in clockwise order. In particular, the island clockwise-adjacent to island N is island 1. The character S_i is written on island i. Initially, there is one person on each island.

You can perform the following operation zero or more times.

• Choose one character c that appears in S. Every person departs from the island they are currently on and moves one island at a time in the clockwise direction. Each person stops as soon as they first arrive, after departing, at an island on which the character c is written. Even if the island a person is currently on has the character c written on it, that person still departs.

Let K be the minimum possible number of islands that have one or more people on them after all operations are finished.

Find K, and a sequence of operations that makes the number of islands with one or more people equal to K after the operations.

Under the constraints of this problem, it can be proved that there always exists a sequence of operations of length at most 10^6 that makes the number of islands with one or more people equal to K.

Constraints

• 1 \le N \le 1000
• S is a string of length N consisting of lowercase English letters.
• N is an integer.

Sample Input 1

4
abca

Sample Output 1

1
1
b

If we perform the operation choosing the character b, everyone gathers on the island on which the character b is written. The number of islands with people becomes 1, and this is the minimum.

Sample Input 2

4
aabb

Sample Output 2

1
2
ab

By choosing a first and then b, everyone gathers on the same island. The number of islands with people becomes 1, and this is the minimum.

Sample Input 3

4
aaaa

Sample Output 3

4
0

No matter which operation is performed, each person moves to the next island in the clockwise direction. Therefore, the number of islands with people is always 4, so K=4. In this sample output, no operation is performed.

Problem Statement

You are given length-M strings S_1,S_2,\ldots,S_N consisting of 0 and 1.

Initially, S_1,S_2,\ldots,S_N are written on the blackboard.

You can perform the following operation zero or more times.

• Choose three strings from those written on the blackboard, allowing the same string to be chosen multiple times, and call them A,B,C. Newly write on the blackboard a string D of length M satisfying the following condition:
  • For each i=1,2,\ldots,M, letting A_i,B_i,C_i,D_i denote the i-th characters of A,B,C,D, respectively, D_i is equal to at least two of A_i,B_i,C_i.

You are given Q strings T_1,T_2,\ldots,T_Q. For each i=1,2,\ldots,Q, determine whether it is possible to make T_i be written on the blackboard by performing operations starting from the initial state.

Constraints

• 1 \leq N \leq 500
• 1 \leq M \leq 500
• 1 \leq Q \leq 500
• S_i is a string of length M consisting of 0 and 1. (1 \leq i \leq N)
• T_i is a string of length M consisting of 0 and 1. (1 \leq i \leq Q)
• All input values are integers.

Sample Input 1

3 3 2
000
011
101
000
001

Sample Output 1

Yes
Yes

T_1 is written on the blackboard from the beginning.

T_2 is 001. If we perform the operation choosing the three strings 000, 011, 101, we can newly write 001 on the blackboard.

Sample Input 2

2 1 2
0
0
0
1

Sample Output 2

Yes
No

The strings initially written on the blackboard are both 0, and the string newly written by the operation is also 0. Therefore, it is impossible to make 1 be written on the blackboard.

Problem Statement

There is a length-N sequence B=(B_1,B_2,\ldots,B_N) consisting of 0 and 1. Initially, B_1=1, and all other elements are 0.

There are M switches, and the integer A_i is written on switch i (1 \le i \le M). When switch i is pressed, using the state immediately before the operation, B_j is simultaneously changed as follows for every integer j satisfying 1 \le j \le N:

\[ B_j \leftarrow \begin{cases} B_j \oplus B_{j-A_i} & (A_i \lt j),\\ B_j & (j \le A_i) \end{cases} \]

Each switch can be pressed zero times or once, and the switches may be pressed in any order.

Find the number, modulo 998244353, of possible final sequences B.

Constraints

• 2 \le N \le 2 \times 10^5
• 1 \le M \le 2 \times 10^5
• 1 \le A_i \lt N (1 \le i \le M)
• All input values are integers.

Sample Input 1

4 2
2 3

Sample Output 1

4

There are four possible final sequences:

• (1,0,0,0)
• (1,0,1,0)
• (1,0,0,1)
• (1,0,1,1)

Sample Input 2

2 1
1

Sample Output 2

2

There are two possible final sequences: (1,0) and (1,1).

Sample Input 3

96 30
56 6 46 18 9 38 20 25 18 44 46 71 44 65 42 20 38 25 9 95 18 65 71 9 95 65 9 42 65 6

Sample Output 3

384912

Problem Statement

There is an integer sequence A=(0,0,\ldots,0) of length N. The following operation is repeated as long as it can be performed.

• Choose a pair of integers (i,j) satisfying 1\le i\lt j\le |A| and A_i=A_j.
• Remove A_i and A_j from the sequence.
• Add 1 to every element that was between A_i and A_j immediately before the removal.

Here, |A| denotes the length of the sequence A at that point.

Find the number, modulo 998244353, of possible sequences when no more operations can be performed. If the final sequences are the same, they are not distinguished even if the process of operations differs. A sequence of length 0 is also counted as one sequence.

Constraints

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

Sample Input 1

1

Sample Output 1

1

No operation can be performed, so there is one possible final sequence: (0).

Sample Input 2

5

Sample Output 2

3

There are three possible final sequences: (0), (1), (2).

Sample Input 3

7

Sample Output 3

8

Depending on the choices made during the operations, eight different sequences can be obtained.

Sample Input 4

200000

Sample Output 4

159211719

Be sure to find the count modulo 998244353.