TheForces Round #45 (DIV3-Forces2)
A. OR what?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For any sequence $$$(b_1, b_2, \ldots, b_m)$$$ of integers, let's define the beauty of the sequence as $$$b_1$$$ $$$|$$$ $$$b_2$$$ $$$|$$$ $$$b_3$$$ $$$\cdots$$$ $$$|$$$ $$$b_m$$$.

Here, $$$|$$$ denotes the bitwise OR operator.

You are given an array of $$$n$$$ positive integers $$$[a_1, a_2, \ldots, a_n]$$$.

Your task is to determine the minimum beauty value over all the non-decreasing subsequences$$$^{\text{∗}}$$$ of the array $$$a$$$.

$$$^{\text{∗}}$$$A subsequence of an array is a sequence that can be obtained by removing several (possibly zero) elements from the original array.

A sequence $$$(b_1, b_2, \ldots, b_m)$$$ is non-decreasing if $$$b_1 \le b_2 \le b_3 \cdots \le b_m$$$.

Input

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

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the length of the array $$$a$$$.

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of the array.

Output

For each testcase, output a single integer — the minimum beauty value over all the non-decreasing subsequences of the given array.

Example
Input
3
4
1 1 1 1
5
9 6 7 6 8
4
4 8 4 4
Output
1
6
4
Note

For the first testcase, consider the subsequence $$$(1, 1, 1)$$$. The beauty of this subsequence is $$$1$$$ $$$|$$$ $$$1$$$ $$$|$$$ $$$1$$$ $$$=$$$ $$$1$$$. This is the minimum possible value over all subsequences.

B. Weird Function
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Define $$$f(x, y) = \begin{cases} 1 & \text{if } x \bmod y = 1 \\ 0 & \text{otherwise} \end{cases}$$$

You are given an integer $$$n$$$. Find any positive integer $$$m$$$, which makes $$$f(m,1) + f(m,2) + \ldots + f(m,n)$$$ reach the maximum.

In other words, for all $$$i \in [1, +\infty)$$$, $$$$$$f(m,1) + f(m,2) + \dots + f(m,n) \ge f(i,1) + f(i,2) + \dots + f(i,n)$$$$$$

You need to find two values: $$$m$$$ and $$$f(m,1) + f(m,2) + \ldots + f(m,n)$$$. Since there can be multiple possible such $$$m$$$, you can output any.

Input

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

A single line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^{9}$$$).

Output

For each test case, output two values — $$$m$$$($$$1 \le m \le 10^{18}$$$) and $$$f(m,1) + f(m,2) + \ldots + f(m,n)$$$. It can be proven that such $$$m$$$ always exists for $$$1 \le m \le 10^{18}$$$. Since there can be multiple possible such $$$m$$$, you can output any.

Example
Input
2
3
5
Output
7 2
61 4
Note

In the first test case, $$$f(m,1)+f(m,2)+f(m,3)=f(7,1)+f(7,2)+f(7,3)=0+1+1=2$$$, which reaches the maximum.

C. Rare Function
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Define $$$f(x, y) = \begin{cases} 1 & \text{if } x \bmod y = 1 \\ 0 & \text{otherwise} \end{cases}$$$

You are given two integers $$$n$$$ and $$$m$$$. Check whether $$$f(m,1) + f(m,2) + \ldots + f(m,n)$$$ reaches the maximum.

In other words, for all $$$i \in [1, +\infty)$$$, $$$$$$f(m,1) + f(m,2) + \dots + f(m,n) \ge f(i,1) + f(i,2) + \dots + f(i,n)$$$$$$

Input

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

A single line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^9$$$).

Output

For each test case, print "YES" if the inequality holds for every $$$i$$$; otherwise, print "NO".

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

Example
Input
3
3 7
1 2
2 4
Output
YES
YES
NO
Note

In the first test case, $$$f(m,1)+f(m,2)+f(m,3)=f(7,1)+f(7,2)+f(7,3)=0+1+1=2$$$, which reaches the maximum.

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

An array $$$b$$$ of length $$$m$$$ is called good if it satisfies the following conditions:

  • $$$m$$$ is even.
  • $$$\operatorname{mex} $$$$$$(\operatorname{mex}$$$$$$(b_1, b_3, \cdots, b_{m-1})$$$$$$,$$$$$$\operatorname{mex}$$$ $$$(b_2, b_4, \cdots ,b_m)) = $$$$$$\operatorname{mex}$$$$$$(b_1, b_2, \cdots ,b_m)$$$.

You are given an array $$$a$$$ of length $$$n$$$ ,where $$$n$$$ is even. Determine whether it can be rearranged into a good array.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$). It is guaranteed that $$$n$$$ is even.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$0 \le a_i \le n$$$).

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

Output

For each testcase, print YES if the given array is beautiful and NO otherwise.

You can output YES and NO in any case (for example, strings yES, yes and Yes will be recognized as a positive response).

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

In the first test case, $$$a=[1,3,0,3]$$$ can be rearranged into $$$a'=[0,1,3,3]$$$.

We can see $$$a'=[0,1,3,3]$$$ is good because $$$\operatorname{mex} $$$$$$(\operatorname{mex}$$$$$$(a'_1, a'_3)$$$$$$,$$$$$$\operatorname{mex}$$$ $$$(a'_2, a'_4)) = $$$$$$\operatorname{mex} $$$$$$(\operatorname{mex}$$$$$$(0, 3)$$$$$$,$$$$$$\operatorname{mex}$$$ $$$(1, 3)) = $$$$$$\operatorname{mex}$$$ $$$(1, 0) = 2 = $$$$$$\operatorname{mex}$$$$$$(a'_1, a'_2, a'_3 ,a'_4)$$$.

E. Max Subarray Sum
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 length $$$n$$$.

The cost of an array is the maximum sum of any of it's subarrays$$$^{\text{∗}}$$$. Note the cost of an empty array is $$$0$$$.

You must choose exactly one non-empty subarray and remove it, then concatenate the remaining part without changing the order. For example, if the array is $$$[1, 5, 2, 4]$$$ and you remove the subarray from index $$$2$$$ to $$$3$$$, the resulting array becomes $$$[1, 4]$$$.

Find the maximum possible cost of the array over all possible subarray removals.

$$$^{\text{∗}}$$$An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Input

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

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

The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the elements of the array.

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

Output

For each testcase, output a single integer — the maximum cost of the given array.

Example
Input
3
4
1 2 3 4
3
1 -1 1
1
-1
Output
9
2
0
Note

In the first test case, the maximum cost is achieved by removing the first element.

In the second test case, the maximum cost is achieved by removing the second element.

F. Bamboozle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

For any integer $$$x$$$, define $$$f(x)$$$ as follows: $$$$$$ f(x) = (x - 1) \oplus x \oplus (x + 1) $$$$$$ where $$$\oplus$$$ denotes the bitwise XOR operator.

We call an array $$$[b_1, b_2, \dots, b_m]$$$ good if it satisfies the following condition: $$$$$$ f(b_1 + b_2 + \dots + b_m) = f(b_1) + f(b_2) + \dots + f(b_m) $$$$$$

You are given an array $$$a$$$ of length $$$n$$$. Determine the number of good subarrays.

Input

The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ $$$(1 \le n \le 2\cdot10^5)$$$.

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

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2\cdot10^5$$$.

Output

For each testcase, print the number of good subarrays.

Example
Input
4
3
1 2 3
5
5 3 6 2 1
5
8 8 3 7 2
4
69 10 54 27
Output
3
6
6
4
Note

In the first test case, there are $$$3$$$ good subarrays $$$[a_1]$$$, $$$[a_2]$$$, and $$$[a_3]$$$.

G. Binary Tree Traversal
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 size $$$n$$$, and an integer $$$r$$$.

Your task is to find a binary tree of size $$$n$$$ satisfying:

  • The binary tree is rooted at $$$r$$$.
  • For every node $$$i$$$ from $$$1$$$ to $$$n$$$, $$$a_i$$$ is the last traversed node in the subtree of node $$$i$$$ using In-order Traversal.

You need to output the In-order Traversal sequence of this binary tree. If there can be multiple possible answers, output any. If there is no such binary tree, output $$$-1$$$ instead.

Input

The first line of input contains $$$t$$$, the number of test cases $$$(1\le t\le 10^4)$$$.

For each testcase:

  • The first line of input contains $$$n$$$ and $$$r(1\le r\le n\le 2 \cdot 10^5)$$$, the number of nodes in the binary tree and the root of the binary tree.
  • The next line contains $$$n$$$ integers $$$a_1,a_2,...a_n$$$, where $$$a_i$$$ is the last node traversed in the subtree of node $$$i$$$ using In-order Traversal.

The sum of $$$n$$$ over all test cases doesn't exceed $$$2\cdot10^5$$$.

Output

For each test case, you have to output a sequence of $$$n$$$ integers — the In-order Traversal sequence of this binary tree. Since there can be multiple possible answers, output any. If there is no such tree, output $$$-1$$$ instead.

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

In the first test case, the binary tree is as follows:

We can see that node $$$1$$$ is the root and for each testcase:

  • for node $$$1$$$ , the last traversed node is $$$2$$$.
  • for node $$$2$$$ , the last traversed node is $$$2$$$.
  • for node $$$3$$$ , the last traversed node is $$$3$$$.
  • for node $$$4$$$ , the last traversed node is $$$3$$$.
  • for node $$$5$$$ , the last traversed node is $$$5$$$.

In the fourth test case, it can be shown that there exists no valid binary tree.

H. Kaosar and Path
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of size $$$n$$$ and an integer $$$x$$$.

You need to perform $$$n$$$ operations. In the $$$i$$$-th operation, you must perform exactly one of the following operations:

  • G-operation: set $$$x := \gcd(x, a_i)$$$.
  • L-operation: set $$$x := \mathrm{lcm}(x, a_i)$$$.

Define the operation sequence $$$s$$$ as a string of length $$$n$$$, where $$$s_i \in \{$$$ 'G', 'L' $$$\}$$$ denotes the type of operation chosen in the $$$i$$$-th operation.

There is an additional constraint: You cannot use the G-operation twice in a row. Formally, if there exists an $$$i$$$ ($$$1 \le i \le n-1$$$) such that $$$s_i=s_{i+1}=\{$$$'G'$$$\}$$$, then it is illegal.

Find the minimum possible final value of $$$x$$$, assuming you perform the operations optimally. And count the number of different operation sequences that can achieve this minimum value, modulo $$$998,244,353$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\le t\le 2 \cdot 10^4$$$). The description of the test cases follows. For each test case:

  • The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1\le n\le 10^5$$$, $$$1\le x\le 10^6$$$).
  • The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$${1\le a_i\le 10^6}$$$).

The sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.

Output

For each test case, print a single line containing two integers — the minimum possible final value of $$$x$$$, assuming you perform the operations optimally, and the number of different operation sequences that can achieve this minimum value, modulo $$$998,244,353$$$.

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

In the first test case:

  • For operation sequence "LG", the final value of $$$x$$$ is $$$2$$$.
  • For operation sequence "GL", the final value of $$$x$$$ is $$$2$$$.
  • For operation sequence "LL", the final value of $$$x$$$ is $$$12$$$.

We can see the minimum possible final value of $$$x$$$ is $$$2$$$, and the number of different operation sequences that can achieve this minimum value is $$$2$$$.