Problem Statement

There are N types of chemicals 1,2,\dots,N. Your goal is to create a state where all of them are mixed.
You are given a string S of length 2^N-1 consisting of 0 and 1, which represents the following information:

• First, define state i (1 \le i \le 2^N-1) where one or more types of chemicals are mixed as follows:
  • When the k-th digit (1 \le k \le N) from the bottom in the binary representation of i is 1, and only then, chemical k is included.
  • For example, 13 in binary is 1101_{(2)}, so state 13 represents a state where chemicals 1,3,4 are mixed.
• When the i-th character of S is 0, state i is safe.
• When the i-th character of S is 1, state i is dangerous.

You mix chemicals using the following operation:

• First, prepare an empty bottle.
• Next, repeat the following:
  • Choose one type of chemical that has not yet been poured into the bottle and pour it into the bottle.
  • At this time, the chemicals mixed in the bottle must not be in a dangerous state.

Determine whether this operation can create a state where all chemicals are mixed.

You are given T test cases; solve each of them.

Constraints

• T is an integer between 1 and 40000, inclusive.
• N is an integer between 1 and 18, inclusive.
• S is a string of length 2^N-1 consisting of 0 and 1.
• The sum of |S| = 2^N-1 in each input does not exceed 5 \times 10^5.

Sample Input 1

5
3
0010000
3
0010110
1
1
2
100
4
001110010101110

Sample Output 1

Yes
No
No
Yes
Yes

This input contains five test cases.

The 1st case is as follows:

• There are three types of chemicals.
• Only state 3 where chemicals 1,2 are mixed is dangerous, and the other states are safe.
• For example, you can create a state where all chemicals are mixed with the following procedure:
  • First, pour chemical 2 into the bottle. Only chemical 2 is mixed in the bottle, which is state 2, so it is safe.
  • Next, pour chemical 3 into the bottle. Chemicals 2,3 are mixed in the bottle, which is state 6, so it is safe.
  • Finally, pour chemical 1 into the bottle. Chemicals 1,2,3 are mixed in the bottle, which is state 7, so it is safe.

The 2nd case is as follows:

• There are three types of chemicals.
• State 3 where chemicals 1,2 are mixed, state 5 where chemicals 1,3 are mixed, and state 6 where chemicals 2,3 are mixed are dangerous, and the other states are safe.
• For this case, it is impossible to create a state where all chemicals are mixed.

The 3rd case is as follows:

• There is one type of chemical.
• Since state 1 where only chemical 1 is mixed is dangerous, it is impossible to create a state where all chemicals are mixed.

Problem Statement

You are given strictly increasing sequences of length N and M: A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ M). Here, A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).

Let C=(C _ 1,C _ 2,\ldots,C _ {N+M}) be a strictly increasing sequence of length N+M that results from the following procedure.

• Let C be the concatenation of A and B. Formally, let C _ i=A _ i for i=1,2,\ldots,N, and C _ i=B _ {i-N} for i=N+1,N+2,\ldots,N+M.
• Sort C in ascending order.

For each of A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M, find its position in C. More formally, for each i=1,2,\ldots,N, find k such that C _ k=A _ i, and for each j=1,2,\ldots,M, find k such that C _ k=B _ j.

Constraints

• 1\leq N,M\leq 10^5
• 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
• 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
• A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
• All values in the input are integers.

Sample Input 1

4 3
3 14 15 92
6 53 58

Sample Output 1

1 3 4 7
2 5 6

C will be (3,6,14,15,53,58,92). Here, the 1-st, 3-rd, 4-th, 7-th elements are from A=(3,14,15,92), and the 2-nd, 5-th, 6-th elements are from B=(6,53,58).

Sample Input 2

4 4
1 2 3 4
100 200 300 400

Sample Output 2

1 2 3 4
5 6 7 8

Sample Input 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

Sample Output 3

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19

Problem Statement

You are given a directed graph with N vertices and M edges. The j-th directed edge goes from vertex u_j to vertex v_j and has a weight of w_j.

Find one way to write an integer between -10^{18} and 10^{18}, inclusive, to each vertex such that the following condition is satisfied.

• Let x_i be the value written on vertex i. For all edges j=1,2,\dots,M, it holds that x_{v_j} - x_{u_j} = w_j.

It is guaranteed that at least one such assignment exists for the given input.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq \min\{2 \times 10^5,N(N-1)/2\}
• 1 \leq u_j, v_j \leq N
• u_j \neq v_j
• If i \neq j, then (u_i, v_i) \neq (u_j, v_j) and (u_i, v_i) \neq (v_j, u_j)
• |w_j| \leq 10^9
• All input values are integers.
• There exists at least one assignment satisfying the conditions.

Sample Input 1

3 3
1 2 2
3 2 3
1 3 -1

Sample Output 1

3 5 2

By setting x = (3, 5, 2), we have x_2 - x_1 = w_1 = 2, x_2 - x_3 = w_2 = 3, x_3 - x_1 = w_3 = -1, satisfying the conditions.

For example, x = (-1, 1, -2) is also a valid answer.

Sample Input 2

4 2
2 1 5
3 4 -3

Sample Output 2

5 0 6 3

For example, x = (0, -5, 4, 1) and x = (5, 0, 4, 1) are also valid answers.

Sample Input 3

5 7
2 1 18169343
3 1 307110901
4 1 130955934
2 3 -288941558
2 5 96267410
5 3 -385208968
4 3 -176154967

Sample Output 3

200401298 182231955 -106709603 69445364 278499365

Problem Statement

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

Perform the following operation M times:

• For each i\ (1\leq i \leq N), add i to A_i. Then, find the minimum non-negative integer not contained in A.

Constraints

• 1\leq N,M \leq 2\times 10^5
• -10^9\leq A_i\leq 10^9
• All values in the input are integers.

Sample Input 1

3 3
-1 -1 -6

Sample Output 1

2
2
0

The 1-st operation makes the sequence A

(-1 + 1, -1 +2 ,-6+3) = (0,1,-3).

The minimum non-negative integer not contained in A is 2.

The 2-nd operation makes the sequence A

(0 + 1, 1 +2 ,-3+3) = (1,3,0).

The minimum non-negative integer not contained in A is 2.

The 3-rd operation makes the sequence A

(1 + 1, 3 +2 ,0+3) = (2,5,3).

The minimum non-negative integer not contained in A is 0.

Sample Input 2

5 6
-2 -2 -5 -7 -15

Sample Output 2

1
3
2
0
0
0

Problem Statement

You are given a string S of length N consisting of o and x, and integers M and K.
S is guaranteed to contain at least one x.

Let T be the string of length NM obtained by concatenating M copies of S. Consider replacing exactly K x's in T with o.
Your objective is to have as long a contiguous substring consisting of o as possible in the resulting T.
Find the maximum length of a contiguous substring consisting of o that you can obtain.

Constraints

• N, M, and K are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le M \le 10^9
• 1 \le K \le x, where x is the number of x's in the string T.
• S is a string of length N consisting of o and x.
• S has at least one x.

Sample Input 1

10 1 2
ooxxooooox

Sample Output 1

9

S= ooxxooooox and T= ooxxooooox.
Replacing x at the third and fourth characters with o makes T= ooooooooox.
Now we have a length-9 contiguous substring consisting of o, which is the longest possible.

Sample Input 2

5 3 4
oxxox

Sample Output 2

8

S= oxxox and T= oxxoxoxxoxoxxox.
Replacing x at the 5,7,8 and 10-th characters with o makes T= oxxooooooooxxox.
Now we have a length-8 contiguous substring consisting of o, which is the longest possible.

Sample Input 3

30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox

Sample Output 3

19964887064