PSUT Individual
A. Alice and Bob
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice gives you an array $$$a$$$ of size $$$n$$$. You can perform the following operation any number of times (including zero):

  • Choose two distinct indexes $$$i$$$ and $$$j$$$, such that $$$a_j \le a_i$$$ and replace $$$a_i$$$ with $$$a_i-a_j$$$.

Bob being the troublemaker he is, orders you to change $$$\textbf{exactly one}$$$ element in the array before performing the above operation. Your goal is to maximize the gcd of the whole array, $$$gcd(a_1,a_2,...,a_n)$$$.

Input

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

The first line of each testcase contains a single integer $$$n$$$ ($$$2\le n\le 10^5$$$) — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1$$$,$$$a_2$$$,…,$$$a_n$$$ ($$$1\le a_i\le 10^9$$$) — the elements of array $$$a$$$.

The sum of $$$n$$$ over all testcases does not exceed $$$10^6$$$.

Output

Output a single integer for each testcase — the maximum possible value of $$$gcd(a_1,a_2,...,a_n)$$$.

Example
Input
3
2
5 5
5
4 4 4 2 4
7
3 6 12 990 9 12 15
Output
5
4
3

B. Yet Another Count the Pairs Satisfying a Condition Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an permutation $$$a$$$ of length $$$n$$$ which will consist of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$.

How many pairs $$$(i, j)$$$ are there such that $$$a_i + a_j = a_{i + a_j}$$$?

Input

The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).

The second line contains $$$n$$$ space separated integers $$$a_1, a_2 \dots a_n$$$ ($$$1 \leq a_i \leq n$$$). It is guaranteed these numbers are all distinct and thus form a permutation of length $$$n$$$.

Output

Output a single integer, which is the number of pairs that satisfy the conditions stated. Note that the answer might not fit into $$$32$$$ bits.

Example
Input
5
3 4 1 2 5
Output
2
Note

For the first testcase, the first pair that works is $$$(i, j) = (1, 3)$$$ since $$$a_1 + a_3 = a_{1 + 1} = 4$$$. The second pair is $$$(i, j) = (3, 3)$$$ since $$$a_3 + a_3 = a_{3 + 1} = 2$$$.

C. Maximum Subarray
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Kilani will give you two arrays, array $$$a$$$ with size $$$n$$$ which all its elements are positive integers, and an array $$$b$$$ with size $$$m$$$ which all its elements are negative integers.

You will have to make a new array $$$c$$$ with size $$$n+m$$$, such that:

  • the array $$$a$$$ is a subsequence of the array $$$c$$$
  • the array $$$b$$$ is a subsequence of the array $$$c$$$
  • the maximum subarray sum of the array $$$c$$$ is minimized.

Can you tell Kilani what is the maximum subarray sum of the array $$$c$$$?

Input

In the first line you will be given $$$n$$$ and $$$m$$$, where $$$(1\le n,m \le 2 \cdot 10^5)$$$.

In the second line you will be given $$$n$$$ integers as the array $$$a$$$, where $$$(1\le a_i \le 10^9)$$$.

In the third line you will be given $$$m$$$ integers as the array $$$b$$$, where $$$(-1\le b_i \le -10^9)$$$.

Output

Print one integer, the maximum subarray sum of the array $$$c$$$.

Examples
Input
4 4
1 1 1 1
-1 -1 -1 -1
Output
1
Input
7 5
4 8 20 7 1 4 9
-13 -3 -17 -2 -5
Output
20

D. Guess the permutation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

In the mystical kingdom of Numeria, a powerful oracle has concealed a secret sequence — a hidden permutation $$$p$$$. The kingdom's future depends on deciphering this sequence, for it holds the key to unlocking the legendary Vault of Order, a chamber said to contain untold wisdom and treasures.

As the kingdom's greatest mathematician, you have been chosen for this task. However, the oracle does not reveal secrets so easily. Instead, she offers a challenge:

"For any query, you may choose three distinct indices $$$i,j,k$$$ where $$$ 1 \le i,j,k \le n$$$, and I shall reveal the sum $$$p_i + p_j + p_k$$$."

Your task is to determine the hidden permutation $$$p$$$ in no more than $$$n$$$ queries.

Input

The first line of each testcase contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of testcases. Description of each testcase follows.

Interaction

The interaction begins with reading $$$n$$$ $$$(4 \le n \le 10^4)$$$ — the length of hidden permutation $$$p$$$.

It is guaranteed that the sum of $$$n$$$ over all testcases do not exceed $$$10^4$$$.

The permutation $$$p$$$ is fixed for each testcase. In other words, the interactor is not adaptive.

It is guaranteed that $$$p$$$ is a permutation.

To make a query, output "? i j k" (without quotes, $$$1 \le i,j,k \le n,i \neq j \neq k \neq i$$$). Then you must read the response to the query, which is equal to $$$p_i + p_j + p_k$$$.

To give an answer, output "! $$$p_1$$$ $$$p_2$$$ $$$p_3$$$ ... $$$p_n$$$" where $$$p_1,p_2,p_3 \cdots p_n$$$ represent the hidden permutation $$$p$$$.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict. If, at any interaction step, you make an invalid query or make more queries than the given limit, then the program will terminate immediately and you will receive Wrong Answer verdict.

$$$^{\text{∗}}$$$To flush, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
2
5

8

10

6

11

11

6
Output

? 5 1 2

? 1 4 3

! 3 1 2 5 4

? 4 5 6

? 3 1 4

? 5 2 3

! 6 3 1 4 2 5
Note

In the first testcase, $$$p = [3,1,2,5,4]$$$.

In the second testcase, $$$p = [6,3,1,4,2,5]$$$.

E. Maximize Minimum Mex
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected tree with $$$n$$$ vertices, labeled from $$$0$$$ to $$$n-1$$$. The tree has $$$n-1$$$ edges and is connected and acyclic.

Your task is to select exactly $$$k$$$ vertices ($$$2 \leq k \leq n$$$) such that the minimum $$$\operatorname{MEX}$$$ value over all paths between two chosen vertices is maximized.

For any two vertices $$$u$$$ and $$$v$$$, define $$$P_{uv}$$$ as the set of vertex labels that appear on the unique simple path between them. The function $$$\operatorname{MEX}(P_{uv})$$$ is defined as the smallest non-negative integer that does not appear in $$$P_{uv}$$$.

Formally, for a chosen set of vertices $$$S$$$ with $$$|S| = k$$$, we define: $$$$$$ f(S) = \min_{u, v \in S, u \neq v} \operatorname{MEX}(P_{uv}). $$$$$$

Your goal is to maximize $$$f(S)$$$ over all valid choices of $$$S$$$.

For each integer $$$k$$$ from $$$2$$$ to $$$n$$$, compute the maximum possible value of $$$f(S)$$$.

Input

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

The first line of each test case contains an integer $$$n$$$ $$$(3 \leq n \leq 10^5)$$$ — the number of nodes in the tree.

The next $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ $$$(0 \leq u, v \lt n)$$$, representing an undirected edge between nodes $$$u$$$ and $$$v$$$.

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

Output

For each test case, print $$$n-1$$$ integers. The $$$i$$$-th integer should represent the maximum possible value of the minimum $$$\operatorname{MEX}$$$ when choosing $$$k = i+1$$$ nodes.

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

The given tree has $$$n = 5$$$ nodes with the following structure:

  • Node $$$0$$$ is connected to nodes $$$1$$$ and $$$2$$$.
  • Node $$$1$$$ is connected to nodes $$$3$$$ and $$$4$$$.

For different values of $$$k$$$:

  • For $$$k = 2$$$, selecting nodes $$$\{2, 3\}$$$ maximizes $$$f(S)$$$, yielding $$$\operatorname{MEX}(\mathcal{P}_{2,3}) = 4$$$.
  • For $$$k = 3$$$, selecting nodes $$$\{0, 1, 2\}$$$ yields a maximum $$$f(S) = 1$$$.
  • For $$$k = 4$$$ and $$$k = 5$$$, the maximum value of $$$f(S)$$$ is $$$0$$$.

F. XO-OR
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two integers $$$x$$$ and $$$y$$$, choose an integer $$$v \in [0, x]$$$ such that the size of a set $$$S$$$ of distinct non-negative integers is maximized.

Formally, determine the largest possible size of a set $$$$$$ S = \{ s_1, s_2, \dots, s_m \} $$$$$$ satisfying the following conditions:

  • The bitwise XOR of all elements equals $$$y$$$: $$$$$$ s_1 \oplus s_2 \oplus \cdots \oplus s_m = y. $$$$$$
  • The bitwise OR of all elements equals $$$v$$$: $$$$$$ s_1 \mid s_2 \mid \cdots \mid s_m = v. $$$$$$

Output the maximum possible value of $$$m$$$. If no valid set exists, output $$$-1$$$.

Input

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

Each test case contains two integers $$$x$$$ and $$$y$$$ $$$(0 \leq x, y \leq 10^{18})$$$.

Output

For each test case, print a single integer  — the maximum possible size of the set $$$S$$$. If no such set can be formed, report $$$-1$$$.

Example
Input
2
2 2
3 0
Output
2
4
Note
  • For the first test case, let $$$(x, y) = (2, 2)$$$ and choose $$$v = 2$$$. The resulting set is defined as: $$$$$$ S = \{0, 2\} $$$$$$
    • XOR of all elements: $$$ 0 \oplus 2 = 2 $$$
    • OR of all elements: $$$ 0 \mid 2 = 2 $$$

  • For the second test case, let $$$(x, y) = (3, 0)$$$ and choose $$$v = 3$$$. The resulting set is defined as: $$$$$$ S = \{0, 1, 2, 3\} $$$$$$
    • XOR of all elements: $$$ 0 \oplus 1 \oplus 2 \oplus 3 = 0 $$$
    • OR of all elements: $$$ 0 \mid 1 \mid 2 \mid 3 = 3 $$$

G. Awkward Middle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

You can perform the following operation any number of times, possibly zero:

Choose an index $$$i$$$ such that $$$1 \lt i \lt |a|$$$ and $$$a_{i-1} = a_{i+1}$$$, then remove the $$$i$$$-th element from the array.

Here, $$$|a|$$$ denotes the current length of the array.

Your task is to find the minimum possible length of the array after performing the operation any number of times.

Input

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

Output

For each test case, print a single integer — the minimum possible length of the array after performing the operation any number of times.

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

In the first test case, one possible sequence of operations is:

$$$$$$ [1, 2, 1, 3, 1] \rightarrow [1, 1, 3, 1] \rightarrow [1, 1, 1] \rightarrow [1, 1] $$$$$$

So the minimum possible length is $$$2$$$.

In the second test case, no operation can be performed, so the answer is $$$4$$$.

In the third test case, the array can be reduced to length $$$3$$$.