Problem Statement

You are given a length-9 sequence of non-negative integers A=(A_1,A_2,\dots,A_9). It is guaranteed that 2\leq \sum_{i=1}^{9}A_i.

You can perform the following operation any number of times (possibly zero): choose one element of A and add 1 to it.

What is the minimum number of operations required so that there exists a sequence of positive integers S satisfying all of the following conditions?

• All elements of S are between 1 and 9, inclusive.
• S contains exactly A_i occurrences of i for each integer i such that 1\leq i\leq 9. (Thus, the length of S is \sum_{i=1}^{9}A_i.)
• No two adjacent elements sum to 10.

It can be proved that the goal can be achieved in a finite number of operations.

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

Constraints

• 1\leq T\leq 10^3
• 0\leq A_i\leq 10^9 (1\leq i\leq 9)
• 2\leq \sum_{i=1}^{9}A_i
• All input values are integers.

Sample Input 1

2
0 0 0 1 0 1 0 0 0
2 1 1 0 0 0 0 0 0

Sample Output 1

1
0

For the first test case, initially, the possible values of S satisfying all conditions except the last one are (4,6) and (6,4), neither of which satisfies the last condition. By choosing A_8 and adding 1 to it, S=(6,8,4) satisfies all conditions.

For the second test case, S=(1,2,3,1) satisfies the conditions without any operations.

Problem Statement

You are given a triple of positive integers (X,Y,Z) such that X\leq Y\leq Z.

Output one triple of sequences of non-negative integers (S_1,S_2,S_3) that satisfies all of the following conditions:

• The lengths of S_1,S_2,S_3 are each between 1 and 1000, inclusive.
• The length of a longest sequence that is both a contiguous subsequence of S_1 and a contiguous subsequence of S_2 is X.
• The length of a longest sequence that is both a contiguous subsequence of S_1 and a contiguous subsequence of S_3 is Y.
• The length of a longest sequence that is both a contiguous subsequence of S_2 and a contiguous subsequence of S_3 is Z.
• \max(\max(S_1),\max(S_2),\max(S_3)) is minimized among all triples satisfying the above four conditions.

It can be proved that under the constraints of this problem, a triple (S_1,S_2,S_3) satisfying the conditions always exists. If there are multiple such triples, you may output any of them.

Constraints

• 1\leq X\leq Y\leq Z\leq 100
• All input values are integers.

Sample Input 1

4 5 5

Sample Output 1

10 1 1 0 0 1 0 1 0 1 1
8 1 1 0 1 0 0 1 1
11 1 0 0 0 1 1 0 1 0 1 0

It can be verified that S_1=(1,1,0,0,1,0,1,0,1,1),S_2=(1,1,0,1,0,0,1,1),S_3=(1,0,0,0,1,1,0,1,0,1,0) satisfies the conditions as follows:

• The lengths of S_1,S_2,S_3 are 10,8,11, respectively, all of which are between 1 and 1000, inclusive.
• The longest sequences that are both a contiguous subsequence of S_1 and a contiguous subsequence of S_2 are (1,0,0,1) and (1,0,1,0), with length X=4.
• The longest sequences that are both a contiguous subsequence of S_1 and a contiguous subsequence of S_3 are (1,0,1,0,1) and (0,1,0,1,0), with length Y=5.
• The longest sequence that is both a contiguous subsequence of S_2 and a contiguous subsequence of S_3 is (1,1,0,1,0), with length Z=5.
• \max(\max(S_1),\max(S_2),\max(S_3))=1, and it can be shown that it is impossible to satisfy the above four conditions with \max(\max(S_1),\max(S_2),\max(S_3))=0, so this is minimal.

Problem Statement

You are given a positive integer N, a string S of length N consisting of # and ., and a length-N sequence of positive integers R=(R_1,R_2,\dots,R_N).

There is a forest with N sections arranged in a single horizontal line. The sections are numbered 1,2,\dots,N from left to right.

Some sections have trees. Specifically, section i has a tree if and only if the i-th character of S is #. It is guaranteed that the following operation can be performed at least once.

You can repeat the following operation as many times as you like:

• Choose two sections without trees. Let sections i and j (where i < j) be the chosen sections from left to right. Then, all trees between sections i and j are removed, and you gain a reward of R_i+R_j.

Here, you cannot perform an operation that removes no trees.

Find the number of ways to perform the first operation to achieve the maximum possible total reward. Two ways are considered distinct if and only if there exists a section chosen in one way but not in the other.

Constraints

• 3\leq N\leq 2\times 10^5
• The length of S is N, and each character is # or ..
• 1\leq R_i\leq 10^9 (1\leq i\leq N)
• The operation can be performed at least once.
• N and R_i are integers.

Sample Input 1

8
...###..
20 25 1 1 30 2 1 1

Sample Output 1

2

There are six ways to perform the first operation, as follows:

• Choose sections 1 and 7. The trees at sections 4,5,6 are removed, and you gain a reward of 21.
• Choose sections 1 and 8. The trees at sections 4,5,6 are removed, and you gain a reward of 21.
• Choose sections 2 and 7. The trees at sections 4,5,6 are removed, and you gain a reward of 26.
• Choose sections 2 and 8. The trees at sections 4,5,6 are removed, and you gain a reward of 26.
• Choose sections 3 and 7. The trees at sections 4,5,6 are removed, and you gain a reward of 2.
• Choose sections 3 and 8. The trees at sections 4,5,6 are removed, and you gain a reward of 2.

No matter which operation is performed, all trees are removed, so a second operation cannot be performed. The maximum possible total reward is 26.

Sample Input 2

5
.#.#.
211 182 192 182 211

Sample Output 2

2

The maximum possible total reward is 825.

Note that the goal is not to maximize the reward obtained in the first operation. If you choose sections 1 and 5 first, you can gain a reward of 422, but no operation can be performed afterwards, and the total reward cannot reach 825.

Sample Input 3

11
#..#.##.#..
192 192 192 211 182 192 182 192 182 211 182

Sample Output 3

3

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges. The i-th edge (1\leq i\leq M) is an undirected edge connecting vertices U_i and V_i.

Place signposts at all vertices as follows:

• At every vertex except vertex 1, place a blue signpost pointing to one of its adjacent vertices.
• At every vertex except vertex 2, place a yellow signpost pointing to one of its adjacent vertices.

Here, the two signposts at the same vertex must not point to the same vertex.

Determine whether it is possible to place signposts satisfying the following conditions, and if possible, output one way to place them:

• From any vertex other than vertex 1, you can reach vertex 1 by repeatedly moving to the vertex pointed to by the blue signpost a finite number of times.
• From any vertex other than vertex 2, you can reach vertex 2 by repeatedly moving to the vertex pointed to by the yellow signpost a finite number of times.

If there are multiple ways to place signposts satisfying the conditions, you may output any of them.

Constraints

• 2\leq N\leq 2\times 10^5
• 1\leq M\leq 3\times 10^5
• 1\leq U_i\lt V_i\leq N (1\leq i\leq M)
• The given graph is simple and connected.
• All input values are integers.

Sample Input 1

7 8
1 3
3 4
4 5
1 5
4 6
2 6
2 7
4 7

Sample Output 1

Yes
5
6
4 1
5 6
1 4
4 2
4 2

Here, signposts are placed as shown in the figure below. For example, from vertex 3:

• Following the blue signpost, you move as vertex 3\rightarrow 4\rightarrow 5\rightarrow 1, eventually reaching vertex 1.
• Following the yellow signpost, you move as vertex 3\rightarrow 1\rightarrow 5\rightarrow 4 \rightarrow 6\rightarrow 2, eventually reaching vertex 2.

You can also verify that following the blue signpost from vertex 2 leads to vertex 1, and following the yellow signpost from vertex 1 leads to vertex 2. The other vertices also satisfy the conditions.

There are multiple other solutions, but you must not have both the blue signpost and the yellow signpost at vertex 3 point to vertex 4, because the signposts at the same vertex would point to the same vertex.

Sample Input 2

10 12
1 3
3 4
4 5
1 5
4 6
2 6
2 7
4 7
4 8
8 9
9 10
8 10

Sample Output 2

No

There is no way to place signposts satisfying the conditions.

Problem Statement

You are given a positive integer N and a permutation P of (1,2,\dots,N).

When there is a tree with N vertices numbered 1,2,\dots,N, Snuke and Takahashi move according to the following rules:

• Snuke specifies a permutation Q of (1,2,\dots,N) such that the sequence returned by Takahashi, when following the rules below, is lexicographically maximum.
• Takahashi, who is at vertex 1 of the tree, first receives Q from Snuke and initializes an integer sequence R with the length-1 sequence (Q_1). Then, he moves N-1 times as follows, and returns the final R:
  • Visit the vertex i with the smallest Q_i among vertices that are adjacent to a previously visited vertex but have not yet been visited (it can be proved that there is always exactly one such vertex). Then, append Q_i to the end of R.

Here, vertex 1 is considered to have been visited initially.

Determine whether there exists a tree such that Takahashi returns P.

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

Constraints

• 1 \le T \le 10^5
• 1 \le N \le 2 \times 10^5
• P is a permutation of (1,2,\dots,N).
• The sum of N over all test cases is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes
No
Yes

For the first test case, a tree with four vertices having edges between vertices 1-2, 1-3, and 2-4 satisfies the conditions.

If Snuke specifies Q=(4,3,2,1), Takahashi visits vertices 1,3,2,4 in this order and returns R=(4,2,3,1). No matter what Q Snuke specifies, it is impossible to make Takahashi return a sequence lexicographically larger than (4,2,3,1), so the sequence that ends up being returned is (4,2,3,1).

For the second test case, it can be proved that there is no tree satisfying the conditions.