TheForces Round #25(5^2-Forces)
A. Make All Elements 0
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ non-negative integers and an integer $$$k$$$.

In one operation you can do:

  • choose two integers $$$l,r(1 \le l \le r \le n)$$$ and a positive integer $$$x(1 \le x \le k)$$$, after that make $$$a_i:=a_i\&x$$$ for all $$$l \le i \le r$$$.

Here $$$\&$$$ denotes the bitwise AND operation.

Find the minimum number of operations to make all elements to zero.

If it's impossible to make all elements to zero, output $$$-1$$$ instead.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10000$$$). The description of the test cases follows.

The first line of each testcase contains two integers $$$n,k$$$ ($$$1 \le n,k \le 10000$$$).

The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$0 \le s_i \le 10000$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10000$$$.

Output

For each test case, print a single integer — the minimum number of operations to make all elements to zero. If it's impossible to make all elements to zero, output $$$-1$$$ instead.

Example
Input
4
1 1
0
4 4
1 3 2 8
4 3
1 3 2 8
8 1
1 5 17 29 1000 11 45 22
Output
0
1
2
-1

B. Array Construction
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given three non-negative integers $$$n,x$$$ and $$$y$$$.

Determine if you can construct an array $$$a$$$ of size $$$n$$$ satisfying:

  • All elements in $$$a$$$ are distinct;
  • $$$a_1 | ... | a_n = x$$$;
  • $$$a_1 \& ... \& a_n = y$$$.

Here $$$|$$$ denotes the bitwise OR operation and $$$\&$$$ denotes the bitwise AND operation.

If you can construct such array $$$a$$$ output YES.Otherwise,output NO.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The only line of each testcase contains three integers $$$n,x,y$$$ ($$$1 \le n \le 2^{30}-1,0 \le x,y \le 2^{30}-1$$$).

Output

For each testcase output in a new line  — If you can construct such array $$$a$$$ output YES.Otherwise,output NO.

Example
Input
4
1 0 0
3 14 2
1000000000 14 2
3 6 5
Output
YES
YES
NO
NO

C. Prefix MEX Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence of $$$n$$$ non-negative integers $$$a = [a_1, a_2, \dots, a_n]$$$.

You can perform the following operation any number of times:

  • choose an index $$$i$$$ ($$$1 \le i \le n$$$) and replace $$$a_i$$$ by the MEX of the prefix $$$[a_1, a_2, \dots, a_{i-1}]$$$. (Note, that in case of choosing $$$i = 1$$$, the MEX of an empty prefix is equal to $$$0$$$).

Find the lexicographically smallest sequence that can be obtained by performing such operations.

Recall that MEX of a sequence is a minimum non-negative integer that does not belong to the sequence.

A sequence $$$a$$$ is lexicographically smaller than a sequence $$$b$$$ if and only if one of the following holds:

  • $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
  • in the first position where $$$a$$$ and $$$b$$$ differ, the sequence $$$a$$$ has a smaller element than the corresponding element in $$$b$$$.
Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, output $$$n$$$ integers — the lexicographically smallest sequence that can be obtained by performing such operations.

Example
Input
4
7
0 3 0 1 2 4 0
4
0 1 2 3
5
1 0 1 0 1
3
1 3 5
Output
0 1 0 1 2 3 0 
0 1 2 3 
0 0 1 0 1 
0 0 0
Note

In the first test case, you can perform such $$$2$$$ operations:

  1. choose $$$i = 2$$$, then replace $$$a_2 = 3$$$ by the MEX of the prefix $$$[0]$$$ — $$$1$$$.
  2. choose $$$i = 6$$$, then replace $$$a_6 = 4$$$ by the MEX of the prefix $$$[0, 1, 0, 1, 2]$$$ — $$$3$$$.

In the second test case, you can perform no operations.

In the third test case, you can perform a single operation:

  1. choose $$$i = 1$$$, then replace $$$a_1 = 1$$$ by the MEX of an empty prefix — $$$0$$$.

D1. Prefix XOR Problem(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 this problem.The only difference is that you can perform at most $$$3n$$$ operations.

You are given two binary strings $$$a$$$ and $$$b$$$ of the same length $$$n$$$.

You can perform the following operation:

  • choose an index $$$i$$$ ($$$1 \le i \le n$$$) and make $$$a_i := a_1 \oplus a_2 \oplus \ldots \oplus a_i$$$, where $$$\oplus$$$ denotes bitwise XOR.

Output any scheme to transform $$$a$$$ into $$$b$$$ by performing at most $$$3n$$$ operations.If there's no such scheme,output $$$-1$$$ instead.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains the binary string $$$a$$$ of length $$$n$$$.

The third line contains the binary string $$$b$$$ of length $$$n$$$.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, if it is impossible to transform $$$a$$$ into $$$b$$$ by performing such operations, output $$$-1$$$.

Otherwise, output $$$2$$$ lines.

The first line should contain a single integer $$$m$$$ ($$$0 \le m \le 3 \cdot n$$$) — the number of operations.

The second line should contain $$$m$$$ integers ($$$1 \le i_1, i_2, \ldots, i_m \le n$$$) — indices defining the operations.

It is guaranteed that if there is a way to transform $$$a$$$ into $$$b$$$, then it can be done in at most $$$3 \cdot n$$$ operations.

Example
Input
4
2
01
00
2
00
00
4
1010
1101
6
110000
111111
Output
-1
0

3
3 4 2
6
2 6 5 4 3 2

D2. Prefix XOR Problem(Hard 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 this problem.The only difference is that you can perform at most $$$n$$$ operations.

You are given two binary strings $$$a$$$ and $$$b$$$ of the same length $$$n$$$.

You can perform the following operation:

  • choose an index $$$i$$$ ($$$1 \le i \le n$$$) and make $$$a_i := a_1 \oplus a_2 \oplus \ldots \oplus a_i$$$, where $$$\oplus$$$ denotes bitwise XOR.

Output any scheme to transform $$$a$$$ into $$$b$$$ by performing at most $$$n$$$ operations.If there's no such scheme,output $$$-1$$$ instead.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains the binary string $$$a$$$ of length $$$n$$$.

The third line contains the binary string $$$b$$$ of length $$$n$$$.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, if it is impossible to transform $$$a$$$ into $$$b$$$ by performing such operations, output $$$-1$$$.

Otherwise, output $$$2$$$ lines.

The first line should contain a single integer $$$m$$$ ($$$0 \le m \le n$$$) — the number of operations.

The second line should contain $$$m$$$ integers ($$$1 \le i_1, i_2, \ldots, i_m \le n$$$) — indices defining the operations.

It is guaranteed that if there is a way to transform $$$a$$$ into $$$b$$$, then it can be done in at most $$$n$$$ operations.

Example
Input
4
2
01
00
2
00
00
4
1010
1101
6
110000
111111
Output
-1
0

3
3 4 2
6
2 6 5 4 3 2

E. Range Modulo Queries
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Raman is a curious kid who likes to play with arrays. One day, his friend Pradeep, a math nerd came to meet him. He gave Raman two arrays $$$a$$$ $$$(a_1,a_2,a_3,...,a_n)$$$ and $$$b$$$ $$$(b_1,b_2,b_3,...,b_n)$$$, both of size $$$n$$$, and asked this problem:

"Given $$$q$$$ queries of the form: $$$l$$$ $$$r$$$ , where $$$1\le l \le r \le n$$$ .

Find minimum possible positive integer $$$m$$$ such that $$$a_i \bmod m = b_i$$$ for all $$$l \le i \le r$$$. And, if no such $$$m$$$ exists, then print $$$-1$$$."

Raman finds the problem difficult to solve,and hence asks you for help. Please solve this problem for him.

Input

The first line contains an integer $$$t (1 \le t \le 10^5)$$$ - the number of test cases.

The descriptions of the test cases follow.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ $$$(1 \le n,q \le 10^6)$$$ - the size of the array and the number of queries.

The second line contains $$$n$$$ space-separated non-negative integers $$$a_1, a_2, a_3, ..., a_n$$$ $$$(0 \le a_i \le 10^6)$$$ — the elements of array $$$a$$$.

The third line contains $$$n$$$ space-separated non-negative integers $$$b_1, b_2, b_3, ..., b_n$$$ $$$(0 \le b_i \le 10^6)$$$ — the elements of array $$$b$$$.

The next $$$q$$$ lines contain the queries: $$$l$$$ $$$r$$$ $$$(1 \le l \le r \le n)$$$.

It is guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases do not exceed $$$10^6$$$.

Output

For each query, output a single positive integer $$$m$$$, as required.

If no such $$$m$$$ exists, then print $$$-1$$$ for that query.

Example
Input
1
4 5
0 18 31 17
1 2 7 5
1 1
2 2
2 3
3 4
2 4
Output
-1
4
8
12
-1

F. Yet Another Tree Problem
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree of $$$n$$$ nodes (the nodes are indexed from $$$1$$$ to $$$n$$$) that is rooted at node $$$1$$$.

Each node has a distinct value $$$a_i$$$ written on it. Let us define $$$Sub(u)$$$ to be the set of all nodes that are in the subtree of node $$$u$$$ (node $$$u$$$ is also included in its subtree).

You have to process $$$Q$$$ queries of $$$4$$$ different types. They are as follows:

  • 1 p u val: Create a new node with index $$$u$$$,parent $$$p$$$ and assign $$$A_u :=$$$ val.It is guaranteed that $$$u$$$ has not appeared before;
  • 2 u: Remove all $$$v$$$ such that $$$v \in Sub(u)$$$ from tree (remove all the nodes in the subtree of $$$u$$$);
  • 3 u val: Assign the value $$$A_u := $$$val;
  • 4 u: Print $$$mex_{v \in Sub(u)} A_v$$$. (Print the $$$mex$$$ of all values of nodes in the subtree of $$$u$$$).

    It is guaranteed that, at any time, there are no two distinct nodes in the tree that have the same value.

    Note: The $$$mex$$$ of a collection of integers $$$c_1, c_2, \ldots, c_k$$$ is defined as the smallest non-negative integer $$$x$$$ which does not occur in the collection $$$c$$$.

Input

The first line contains two space separated integers denoting $$$n,q (2 \le n,q \le 2 \cdot 10^5)$$$.

The next line contains $$$n-1$$$ space separated integers $$$p_2, p_3, \dots, p_n(1 \le p_i \le n)$$$ where $$$p_i$$$ denotes an edge between node $$$p_i$$$ and $$$i$$$ where $$$p_i$$$ is the parent of $$$i$$$.

The next line contains $$$n$$$ space separated integers $$$a_1, a_2, \dots, a_n(0 \le a_i \le 10^9)$$$.

The next $$$q$$$ lines contain the queries as described above.

It's guaranteed:

  • The edges of the initial graph form a valid tree.
  • $$$0 \le$$$ val $$$\le 10^9$$$
  • In queries, $$$1 \le p, u \le n+q$$$
  • At all times there are no two distinct nodes in the tree that have the same value.
  • For all $$$p, u$$$ that appear in the queries of type $$$1$$$, there is a node with index $$$p$$$ in the tree,there is no node with the index $$$u$$$ and $$$u$$$ has not appeared before.
  • For all $$$u$$$ that appear in the queries of type $$$2, 3$$$ and $$$4$$$, there is a node with index $$$u$$$ in the tree.
Output

For each query of type $$$4$$$, print the answer in a new line.

Example
Input
5 5
1 2 3 3
5 4 3 2 1
1 5 7 0
4 5
2 3
3 2 0
4 2
Output
2
1
Note
  • Initially, the tree looks like this:

  • After the first query, the tree looks like this:

  • After the fourth query, the tree looks like this:

  • After the fifth query, the tree looks like this: