TheForces Round #37 (Brute-Forces1)
A. Niimmm
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob decided to play the following game on a pile containing $$$n$$$ stones with Alice starting first :

  • On his/her turn, he/she will choose $$$2$$$ or $$$3$$$ stones from the pile and remove it.

The player who cannot make a move loses. Note that both Alice and Bob are intelligent so they always play optimally.

You are the best friend of Alice. So add the minimum number of additional stones to the pile so that Alice will win.

Input

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

The first line of each testcase contain single integer $$$n$$$ ($$$1 \le n \le 10^3$$$) — the number of stones in a pile.

Output

For each test case, print a single integer — minimum number of additional stones added to the pile so that Alice will win.

Example
Input
4
2
4
6
10
Output
0
0
1
2

B. K Palindrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A grid containing $$$n$$$ rows and $$$n$$$ columns is called Beautiful grid if it satisfies the following conditions :

  • Each cell conatins a lowercase English character.
  • For every $$$i(1 \le i \le n)$$$, $$$i$$$-th row is palindrome.
  • For every $$$i(1 \le i \le n)$$$, $$$i$$$-th column is palindrome.
  • The number of distinct characters in the grid is exactly $$$k$$$.

Your task is to construct any Beautiful grid for given $$$n$$$ and $$$k$$$.

Input

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

The first line of each testcase contains two integers $$$n,k$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le k \le 26$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^3$$$.

Output

For each test case, print $$$-1$$$ if there is no Beautiful grid. Otherwise print $$$n$$$ strings each of length $$$n$$$.

If there are multiple answers, output any.

Example
Input
5
1 1
2 1
2 2
3 2
3 26
Output
z
kk
kk
-1
www
wyw
www
-1

C. Pair of GCD
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer array $$$a$$$ containing $$$n$$$ elements.

Find the maximum value of $$$^\dagger$$$ $$$gcd(a_1, a_2, a_3, \cdots , a_n)$$$, after applying the following operation exactly once :

  • Choose any $$$i,j(1 \le i \lt j \le n)$$$ and change $$$a_i$$$ and $$$a_j$$$ to any value.

$$$^\dagger$$$ $$$gcd(a_1, a_2, a_3, \cdots , a_n)$$$ denotes the greatest common divisor of $$$a_1, a_2, a_3, \cdots , a_n$$$.

Input

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

The first line of each test case contains single integer $$$n$$$ ($$$3 \le n \le 10^5$$$) — the length of the array.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n$$$ ($$$1 \le a_{i} \le 10^9$$$).

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

Output

For each test case, print single integer — the maximum value of $$$gcd(a_1, a_2, a_3, \cdots , a_n)$$$.

Example
Input
4
3
2 3 2
4
4 3 2 1
6
4 4 3 3 2 2
9
3 6 9 2 3 6 9 3 6
Output
3
2
2
3
Note

In the $$$1$$$-th test case, Choose $$$i = 1$$$ and $$$j = 3$$$ and change $$$a_i$$$ to $$$9$$$ and $$$a_j$$$ to $$$9$$$.

So the final array is $$$9, 3, 9$$$.

Hence, $$$gcd(9, 3, 9) = 3$$$.

D. Perfect Prefix
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

An integer array $$$b$$$ containing $$$m$$$ elements is called perfect-prefix array, if it satisfies the following condition :

  • For every $$$i(1 \le i \le m)$$$, $$$\sum_{j = 1}^i b_j \gt 0$$$.

You can do the following operation on $$$b$$$ any number of times (possibly zero) :

  • Choose $$$i,j(1 \le i \le j \le m)$$$ and swap $$$a_i$$$ and $$$a_j$$$.

Let $$$f(b)$$$ be the minimum number of operations required to turn $$$b$$$ into perfect-prefix array. If it is not possible to turn $$$b$$$ into perfect-prefix array then $$$f(b) = -1$$$.

You are given an integer array $$$a$$$ containing $$$n$$$ elements where each element is either $$$1$$$ or $$$-1$$$.

Now your task is to answer $$$q$$$ queries of following type :

  • 1 l r : Find the value of $$$f(a[l \cdots r])$$$.
  • 2 x : Multiply $$$a_x$$$ with $$$-1$$$.
Input

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

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

The second line of each test case contains $$$n$$$ space separated integers $$$a_{i}$$$ ($$$-1 \le a_{i} \le 1$$$ , $$$a_i ≠ 0$$$).

The next $$$q$$$ lines contain one of the two forms:

  • 1 l r $$$(1 \le l \le r \le n)$$$ ;
  • 2 x $$$(1 \le x \le n)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$.

It is guaranteed that the sum of $$$q$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$.

Output

For each test case, print the required answer for the $$$1$$$-st type query.

Example
Input
2
5 5
1 1 -1 1 -1
1 1 4
1 2 4
2 3
1 1 4
1 4 5
11 6
1 1 1 1 -1 -1 -1 1 1 -1 -1
1 7 9
1 1 11
2 5
2 6
1 1 7
1 7 10
Output
0
1
0
-1
1
0
0
-1

E. Any Tree ?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer grid $$$a$$$ containing $$$n$$$ rows and $$$n$$$ columns. Let $$$a_{i,j}$$$ denote the value at the $$$i$$$-th row from the top and $$$j$$$-th column from the left.

Now your task is to construct a tree (undirected acyclic graph) containing $$$n$$$ nodes, such that :

  • For every $$$i,j(1 \le i,j \le n)$$$, the smallest value of the node on the path between $$$i$$$ and $$$j$$$ (both inclusive) is $$$a_{i,j}$$$.
Input

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

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

The next $$$n$$$ lines of each test case contains $$$n$$$ integers $$$a_{i,1},a_{i,2},\cdots,a_{i,n}$$$ ($$$1 \le a_{i,j} \le n$$$).

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

Output

For each test case, print $$$-1$$$ if there is no possible tree.

Otherwise, print $$$n-1$$$ lines — the edges of the tree.

If there are multiple answers output any.

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

F. Permutation via Tree
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a rooted tree containing $$$n$$$ nodes and rooted at node $$$1$$$.

Now your task is to count the number of different permutations $$$p$$$ of length $$$n$$$ which satisfies the following condition :

  • For every $$$i(1 \le i \lt n)$$$, either $$$p_i$$$ is an $$$^\dagger$$$ ancestor of $$$p_{i+1}$$$ or $$$p_{i+1}$$$ is an ancestor of $$$p_i$$$.

$$$^\dagger$$$ Node $$$a$$$ is an ancestor of node $$$b$$$ if the shortest path from $$$b$$$ to the root passes through $$$a$$$.

Input

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

The first line of each test case contains a single integer $$$n$$$ $$$(3 \le n \le 5000)$$$ — the size of the tree.

The next $$$n-1$$$ lines contain two integers $$$x,y$$$ $$$(1 \le x,y \le n, x≠y)$$$ — there is an edge between $$$x$$$ and $$$y$$$.

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

Output

For each test case, print a single integer — the required count modulo $$$10^9 + 7$$$.

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

For the first test case, the permutations which satisfies the condition are :

  1. $$$2, 1, 3$$$
  2. $$$3, 1, 2$$$

For the second test case, the permutations which satisfies the condition are :

  1. $$$2, 4, 5, 1, 3$$$
  2. $$$5, 4, 2, 1, 3$$$
  3. $$$3, 1, 5, 4, 2$$$
  4. $$$3, 1, 2, 4, 5$$$

G. If Sort is Life
time limit per test
13 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a permutation $$$p$$$ of length $$$n$$$.

You are allowed to do the following operation :

  • Choose any $$$i,j(1 \le i, j \le n)$$$ such that |$$$i - j$$$| is odd, then swap $$$p_i$$$ and $$$p_j$$$.

Let $$$f(p)$$$ denotes the minimum number of operations required to sort $$$p$$$ in ascending order.

Find the value of $$$f(p)$$$ and also answer the $$$q$$$ queries :

  • x y : swap $$$p_x$$$ and $$$p_y$$$ and find the value of $$$f(p)$$$. Note that these updates are persistent, that is changes made to the $$$p$$$ will apply when processing future updates.
Input

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

The first line of each test case contains two integers $$$n,q$$$ $$$(2 \le n,q \le 5 \cdot 10^4)$$$ — the length of the permutation and the number of queries.

The second line of each test case contains $$$n$$$ integers $$$p_1,p_2,\cdots,p_n$$$ ($$$1 \le p_{i} \le n$$$).

The next $$$q$$$ lines of each test case contains two integers $$$x,y$$$ $$$(1 \le x \lt y \le n)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^4$$$.

It is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$5 \cdot 10^4$$$.

Output

For each test case, print $$$q+1$$$ space separated integers — the value of $$$f(p)$$$.

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