TheForces Round #12 (Double-Forces)
A. A Matchsticks Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have $$$n$$$ matchsticks.Your task is to combine them to make a number.

Here're some restrictions:

  1. Each and every digit must be put together exactly as shown in the image above.
  2. The $$$n$$$ marchsticks must all be used up.
  3. There may be leading zeros in the number.

Find the least possible number.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 1000)$$$, denoting the number of test cases.

Each test case consists of a line of input.The only line of each test case contains an integer $$$n(2 \leq n \leq 1000)$$$.

Output

For each test case, output on a new line — the the smallest number you can get.

Example
Input
3
4
8
60
Output
4
01
0000000000

B. Yet Another Matchsticks Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have $$$n$$$ matchsticks.Your task is to combine them to make a number..

Here're some restrictions:

  1. Each and every digit must be put together exactly as shown in the image above.
  2. You don't need to use up all $$$n$$$ marchsticks.
  3. Leading zeros are not permitted in the number.
  4. The number's digits cannot go beyond k.

Find the largest possible number.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 1000)$$$, denoting the number of test cases.

Each test case consists of a line of input.The only line of each test case contains two integers $$$n(2 \leq n \leq 1000),k(1 \leq k \leq 1000)$$$.

Output

For each test case, output on a new line — the the biggest number you can get.

Example
Input
3
1000 1
2 1000
9 2
Output
9
1
97

C1. Permutaion Construction(easy version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of the problem.The only difference is that there is no the third restriction.

You're given an integer $$$n$$$.Construct a permutation $$$p$$$ of length $$$2n$$$ which satisfies:

  1. $$$p_1+p_2=p_3+p_4=...=p_{2n-1}+p_{2n}$$$
  2. $$$p_2+p_3=p_4+p_5=...=p_{2n-2}+p_{2n-1}$$$

If no solution,output $$$-1$$$ instead.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists a single line of input.

The only line of each test case contains an integer $$$n(2 \leq n \leq 10^5)$$$. The sum of $$$n$$$ over all test cases won't exceed $$$10^5$$$.

Output

For each test case, output on a new line — a permutaion of length $$$2n$$$ which satisfies the restrictions above.If no solution,output $$$-1$$$ instead.

Example
Input
2
2
3
Output
1 4 3 2
4 3 5 2 6 1

C2. Permutaion Construction(hard version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of the problem.The only difference is that there is the third restriction.

You're given two integers $$$n$$$ and $$$x$$$.Construct a permutation $$$p$$$ of length $$$2n$$$ which satisfies:

  1. $$$p_1+p_2=p_3+p_4=...=p_{2n-1}+p_{2n}$$$
  2. $$$p_2+p_3=p_4+p_5=...=p_{2n-2}+p_{2n-1}$$$
  3. $$$p_1=x$$$

If no solution,output $$$-1$$$ instead.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

Each test case consists a single line of input.

The only line of each test case contains two integers $$$n(2 \leq n \leq 10^5),x(1 \leq x \leq 2n)$$$. The sum of $$$n$$$ over all test cases won't exceed $$$10^5$$$.

Output

For each test case, output on a new line — a permutaion of length $$$2n$$$ which satisfies the restrictions above.If no solution,output $$$-1$$$ instead.

Example
Input
3
2 3
3 5
4 6
Output
3 2 4 1
5 2 3 4 1 6
-1

D. Y Flip
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two $$$n*m$$$ binary matrixs $$$a,b$$$ and an integer $$$l$$$.

Define a Y as an element set which contains $$$4$$$ elements.There are $$$4$$$ types of Y:

Type $$$1$$$:$$${a_{x,y},a_{x-1,y-1},a_{x-1,y+1},a_{x+1,y-1}}$$$

Type $$$2$$$:$$${a_{x,y},a_{x-1,y-1},a_{x-1,y+1},a_{x+1,y+1}}$$$

Type $$$3$$$:$$${a_{x,y},a_{x-1,y-1},a_{x+1,y-1},a_{x+1,y+1}}$$$

Type $$$4$$$:$$${a_{x,y},a_{x-1,y+1},a_{x+1,y-1},a_{x+1,y+1}}$$$

Note none of the elements can exceed the boundary.

You can do the following operation for $$$a$$$ any number of times:choose a Y in $$$a$$$,flip each number in it.

Flip means:if the number is $$$0$$$ change it to $$$1$$$,otherwise change it to $$$0$$$.

Find if $$$a$$$ can change to $$$b$$$ after any number of operations.

Input

The first line of input will contain a single integer $$$t(t \leq 300)$$$, denoting the number of test cases.

Each test case consists of multiple lines of input.

The first line of each test case contains two space-separated integers $$$n$$$,$$$m$$$$$$(3 \leq n,m \leq 1000)$$$.

The next $$$n$$$ lines describe $$$a$$$.There are $$$m$$$ numbers in each line. The $$$j^{th}$$$ number in line $$$i$$$ represents $$$a_{i,j}(0 \leq a_{i,j} \leq 1)$$$.

The next $$$n$$$ lines describe $$$b$$$.There are $$$m$$$ numbers in each line. The $$$j^{th}$$$ number in line $$$i$$$ represents $$$b_{i,j}(0 \leq b_{i,j} \leq 1)$$$.

The sum of $$$n,m$$$ over all test cases won't exceed $$$1000$$$.

Output

For each test case, output on a new line:if $$$a$$$ can change to $$$b$$$ after any number of operations,output $$$YES$$$,otherwise output $$$NO$$$.

Example
Input
5
3 3
1 0 1
0 1 0
0 0 0
1 0 1
0 1 0
1 0 1
3 3
0 0 0
0 0 0
0 0 0
0 1 0
1 0 1
0 1 0
4 4
0 0 0 0
0 0 0 0
1 1 1 1
1 1 1 1
0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1
4 4
0 0 0 0
0 0 0 0
1 1 1 1
1 1 1 1
0 0 0 0
0 0 0 0
1 1 1 0
1 1 1 0
3 4
0 1 0 0
0 1 1 1
1 0 0 1
0 1 0 1
0 1 0 1
0 0 1 1
Output
YES
NO
YES
NO
YES
Note

Test case $$$1$$$:

  1. flip $$${a_{2,2},a_{1,1},a_{1,3},a_{3,1}}$$$

  2. flip $$${a_{2,2},a_{1,1},a_{1,3},a_{3,3}}$$$

Test case $$$2$$$:It can be proved there's no way to change $$$a$$$ to $$$b$$$.

E. Yet Another Y Flip
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes.Node $$$1$$$ is the root node.The value of each node is either $$$0$$$ or $$$1$$$.

Define a Y as an node set which contains $$$4$$$ nodes.The descriptions of the $$$4$$$ nodes are as follows:

  1. A node(note it as $$$x$$$) with at least two child nodes;
  2. The parent node of $$$x$$$;
  3. Any two child nodes of $$$x$$$.

You can do the following operation any number of times:choose a Y in the tree,flip each value of nodes in it.

Flip means:if the value is $$$0$$$ change it to $$$1$$$,otherwise change it to $$$0$$$.

Find if you can change the values of all nodes to $$$0$$$.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

For each test case:

The first line of each test case contains an integer $$$n(4 \leq n \leq 10^5)$$$.

The next line contains $$$n$$$ integers $$$a_1,a_2,...,a_n(0 \leq a_i \leq 1)$$$— the value of node from $$$1$$$ to $$$n$$$.

The next $$$n-1$$$ line of each test case contains two integers:$$$u,v(1 \leq u,v \leq n)$$$.It means there's an edge between node $$$u$$$ and $$$v$$$.

The sum of $$$n$$$ over all test cases won't exceed $$$10^5$$$.

Output

For each test case, output on a new line — if you can change the values of all nodes to $$$0$$$,output $$$YES$$$.Otherwise,output $$$NO$$$.

Example
Input
8
4
0 0 0 0
1 2
1 3
2 4
4
1 1 1 0
1 2
1 3
2 4
7
1 0 0 1 0 0 0
1 2
2 3
2 4
3 5
3 6
3 7
7
0 1 1 0 0 0 0
1 2
1 3
1 4
2 5
3 6
4 7
10
0 0 0 0 0 0 0 1 0 1
1 4
2 4
3 2
4 10
5 2
6 3
7 3
8 2
9 3
10
1 0 0 1 0 0 1 0 0 1
1 2
2 4
3 2
4 10
5 3
6 4
7 4
8 3
9 3
10
1 1 0 0 1 0 0 0 1 0
1 4
2 10
3 4
4 2
5 2
6 5
7 3
8 4
9 2
12
1 0 1 0 0 0 0 0 0 0 0 0
1 2
2 3
2 4
4 5
4 6
5 7
5 8
5 9
6 10
6 11
6 12
Output
YES
NO
YES
NO
NO
YES
YES
YES
Note

Test case $$$1$$$:

Since the values of all nodes are already $$$0$$$,you don't need to do any operations.

Test case $$$2$$$:

Since you can not do any operations at all and $$$a_1=a_2=a_3=1$$$,you can not change the values of all nodes to $$$0$$$.

Test case $$$3$$$:

  1. Flip node $$$2,1,3,4$$$
  2. Flip node $$$3,2,5,6$$$
  3. Flip node $$$3,2,5,7$$$
  4. Flip node $$$3,2,6,7$$$

F1. Partition and Alternating Sum(easy version)
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is the easy version of the problem.The only difference is the time limit and memory limit.

You are given an array $$$a$$$ of size $$$n$$$.

You do the following operation:

  1. First you choose an integer $$$k(1 \leq k \leq n)$$$
  2. Then choose $$$k$$$ intervals $$$[l_i,r_i](1 \leq i \leq k,l_1=1,r_k=n)$$$ and $$$(l_{j+1}=r_j+1$$$ for $$$1 \leq j \leq k-1)$$$.

Note $$$s_i=a_{l_i}|a_{l_{i+1}}$$$ $$$|...|a_{r_i}$$$.Here $$$|$$$ means bitwise-or.

Find the maximum of $$$Σ_{i=1}^k(-1)^{i+1}*s_i$$$.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^6)$$$, denoting the number of test cases.

Each test case consists of multiple lines of input.

The first line of each test case contains an integer $$$n(1 \leq n \leq 10^6)$$$.

The next lines contains $$$n$$$ space-separated integers:$$$a_1$$$,$$$a_2$$$,...$$$a_n$$$ $$$(0 \leq a_i \lt 2^{30})$$$.

The sum of $$$n$$$ over all test cases won't exceed $$$10^6$$$.

Output

For each test case, output on a new line — the maximum of $$$Σ_{i=1}^k(-1)^{i+1}*s_i$$$.

Example
Input
4
3
2 1 2
6
6 6 6 6 6 6
7
7 0 5 4 4 2 6
6
9 4 6 8 1 7
Output
3
6
16
25
Note

Test case $$$1$$$:

Choose $$$k=3,[l_1,r_1]=[1,1],[l_2,r_2]=[2,2],[l_3,r_3]=[3,3]$$$.

We get $$$s_1=2,s_2=1,s_3=2$$$.The answer is $$$s_1-s_2+s_3=2-1+2=3$$$.

Test case $$$2$$$:

Choose $$$k=1,[l_1,r_1]=[1,6]$$$.

We get $$$s_1=6$$$.The answer is $$$s_1=6$$$.

F2. Partition and Alternating Sum(hard version)
time limit per test
1 second
memory limit per test
4 megabytes
input
standard input
output
standard output

This is the hard version of the problem.The only difference is the time limit and memory limit.

You are given an array $$$a$$$ of size $$$n$$$.

You do the following operation:

  1. First you choose an integer $$$k(1 \leq k \leq n)$$$
  2. Then choose $$$k$$$ intervals $$$[l_i,r_i](1 \leq i \leq k,l_1=1,r_k=n)$$$ and $$$(l_{j+1}=r_j+1$$$ for $$$1 \leq j \leq k-1)$$$.

Note $$$s_i=a_{l_i}|a_{l_{i+1}}$$$ $$$|...|a_{r_i}$$$.Here $$$|$$$ means bitwise-or.

Find the maximum of $$$Σ_{i=1}^k(-1)^{i+1}*s_i$$$.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^6)$$$, denoting the number of test cases.

Each test case consists of multiple lines of input.

The first line of each test case contains an integer $$$n(1 \leq n \leq 10^6)$$$.

The next lines contains $$$n$$$ space-separated integers:$$$a_1$$$,$$$a_2$$$,...$$$a_n$$$ $$$(0 \leq a_i \lt 2^{30})$$$.

The sum of $$$n$$$ over all test cases won't exceed $$$10^6$$$.

Output

For each test case, output on a new line — the maximum of $$$Σ_{i=1}^k(-1)^{i+1}*s_i$$$.

Example
Input
4
3
2 1 2
6
6 6 6 6 6 6
7
7 0 5 4 4 2 6
6
9 4 6 8 1 7
Output
3
6
16
25
Note

Test case $$$1$$$:

Choose $$$k=3,[l_1,r_1]=[1,1],[l_2,r_2]=[2,2],[l_3,r_3]=[3,3]$$$.

We get $$$s_1=2,s_2=1,s_3=2$$$.The answer is $$$s_1-s_2+s_3=2-1+2=3$$$.

Test case $$$2$$$:

Choose $$$k=1,[l_1,r_1]=[1,6]$$$.

We get $$$s_1=6$$$.The answer is $$$s_1=6$$$.