Bangladesh CP Server - BCS Round 1 (Div. 3)
A. String Removal
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ consisting of characters 'a' and/or 'b'.

In one move you can remove any two adjacent characters from the string if those two characters are different.

Can you make the whole string empty by applying the move as many times as you want(possibly zero)?

Input

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

Each test case consists of one line containing the string $$$s$$$ ($$$1\le |s|\le 2 \cdot 10^5$$$), consisting of characters 'a' and/or 'b'.

The total length of strings $$$s$$$ in all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case print "YES" (without quotes) if you can make the string empty, or "NO" (without quotes) otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as correct answer).

Example
Input
4
ba
abaabb
a
bbbbb
Output
YES
YES
NO
NO
Note

In the first test case, you can erase the whole string in a single move as the two characters are different.

In the second test case, you can apply the following moves (the underlined characters are being removed in each operation):

"abaabb" $$$\rightarrow$$$ "abaabb" $$$\rightarrow$$$ "abab" $$$\rightarrow$$$ "abab" $$$\rightarrow$$$ "ab" $$$\rightarrow$$$ "ab"$$$\rightarrow$$$ ""

In the third test case, you can't make a move because there is only a single character.

In the fourth test case, there is only character $$$b$$$ in the whole string. As no two adjacent characters are different you can't make any move, and thus the answer is "NO"

B. OR-bitax
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

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

The score of a subarray is defined as the bitwise XOR of the elements in this subarray.

You need to split the sequence $$$a$$$ into one or more consecutive subarrays so that each element of $$$a$$$ belongs to exactly one subarray and the bitwise OR of the scores of these subarrays is as large as possible.

For example, if $$$a=[3,4,2,5,1]$$$, then you can split the array into subarrays $$$[3,4]$$$ with score $$$3 \oplus 4 = 7$$$, and $$$[2,5,1]$$$ with score $$$2 \oplus 5 \oplus 1 = 6$$$. The bitwise OR of the scores $$$6$$$ and $$$7$$$ is $$$7$$$. This is the maximum possible score for the given array. Note that, here $$$\oplus$$$ is the bitwise XOR operator.

An array $$$c$$$ is a subarray of an array $$$b$$$ if $$$c$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

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

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

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

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

Output

For each test case, output an integer  — the maximum possible bitwise OR of the scores.

Example
Input
2
3
6 4 8
5
3 4 2 5 1
Output
14
7
Note

In the first test case, the possible ways to split the array are given below:

  • $$$[6], [4], [8]$$$. Scores are $$$6, 4, $$$ and $$$8$$$. The bitwise OR of the scores $$$=14$$$.
  • $$$[6, 4], [8]$$$. Scores are $$$6 \oplus 4 = 2$$$ and $$$8$$$. The bitwise OR of the scores $$$=10$$$.
  • $$$[6], [4, 8]$$$. Scores are $$$6$$$ and $$$4 \oplus 8 = 12$$$. The bitwise OR of the scores $$$=14$$$.
  • $$$[6, 4, 8]$$$. Scores are $$$6 \oplus 4 \oplus 8 = 10$$$. The bitwise OR of the scores $$$=10$$$.

So the maximum possible bitwise OR of the scores is $$$14$$$.

The second test case is explained in the problem statement.

C. Equal Digits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. Find the smallest integer $$$k$$$ such that $$$k \ge n$$$ and all digits in $$$k$$$ are the same.

Input

The first and only line of the input contains a single integer $$$n$$$ $$$(1 \le n \le 10^{18})$$$.

Output

Output the value of $$$k$$$ as described in the statement.

Examples
Input
6528
Output
6666
Input
9952
Output
9999

D. GCD in Median Land
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 $$$n$$$ integers.

For each integer $$$k$$$ from $$$1$$$ to $$$n$$$, solve the following problem:

  • Select a $$$k$$$ length subsequence of $$$a$$$ and take its median.
  • Do it for all possible $$$k$$$ length subsequences of $$$a$$$ and compute the medians of each of the subsequences.
  • Now compute the Greatest Common Divisor (GCD) of all those medians.

Check the sample explanation for more clarity.

A subsequence is a sequence that can be derived from the given array by deleting zero or more elements without changing the order of the remaining elements.

The median of a sequence is the value of the element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of the two middle elements is used.

For example, for the sequence $$$[4,2,7,5]$$$, its median is $$$4$$$ since after sorting the sequence, it will look like $$$[2,4,5,7]$$$ and the left of two middle elements is equal to $$$4$$$. The median of $$$[7,1,2,9,6]$$$ equals $$$6$$$ since after sorting, the value $$$6$$$ will be in the middle of the sequence.

Input

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

The first line of each test case contains an integer $$$n(1\leq n\leq 10^5)$$$  — the number of integers in the array. The next line contains $$$n$$$ space-separated integers $$$a_i (1\leq a_i\leq 10^9)$$$  — the elements of the array.

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

Don't forget to use Fast I/O as the input is huge.

Output

For each test case, print $$$n$$$ space-separated integers in a line. The $$$k^{th}$$$ integer will represent the $$$\operatorname{GCD}$$$ of the medians of all possible $$$k$$$ length subsequences of $$$a$$$.

Example
Input
2
3
12 8 30
2
5 7
Output
2 4 12 
1 5
Note

In the first test case,

The $$$1$$$ length subsequences and their medians are:

  1. $$$[12]$$$. Median = $$$12$$$.
  2. $$$[8]$$$. Median = $$$8$$$.
  3. $$$[30]$$$. Median = $$$30$$$.

The $$$\operatorname{GCD}$$$ of the medians $$$=\operatorname{GCD}([12,8,30]) = 2$$$.

The $$$2$$$ length subsequences and their medians are:

  1. $$$[12, 8]$$$. After sorting: $$$[8, 12]$$$. Median = $$$8$$$.
  2. $$$[8, 30]$$$. After sorting: $$$[8, 30]$$$. Median = $$$8$$$.
  3. $$$[12, 30]$$$. After sorting: $$$[12, 30]$$$. Median = $$$12$$$.

The $$$\operatorname{GCD}$$$ of the medians $$$=\operatorname{GCD}([8, 8, 12])=4$$$.

The $$$3$$$ length subsequences and their medians are:

  1. $$$[12, 8, 30]$$$. After sorting: $$$[8, 12, 30]$$$. Median = $$$12$$$.
The $$$\operatorname{GCD}$$$ of the medians $$$=\operatorname{GCD}([12])=12$$$.

E. Non-decreasing Sequence
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \ldots a_n$$$.

In one operation you can do the following:

  • Select an index $$$i$$$ such that $$$1 \le i \lt n$$$.
  • Merge the two adjacent elements $$$a_i$$$ and $$$a_{i + 1}$$$ by their sum.

For example, if $$$a = [2, 3, 7, 4, 5]$$$ and you select $$$i = 3$$$, then after performing the operation, the array will be $$$[2, 3, \underline{7}, \underline{4}, 5] \rightarrow [2, 3, 7 + 4, 5] \rightarrow [2, 3, 11, 5]$$$.

Find the minimum number of operations to make the array non-decreasing.

Input

The first line contains an integer $$$n$$$ $$$(1\le n \le 3000)$$$  — the length of the array.

The second line contains $$$n$$$ space-separated integers $$$a_1,a_2,...,a_n$$$ $$$(1\le a_i \le 10^{15})$$$

Output

Output an integer  — the minimum number of operations needed to make the array non-decreasing.

Examples
Input
6
4 3 2 7 6 9
Output
2
Input
7
55 50 87 17 36 90 6
Output
4
Input
17
55 50 87 17 36 90 6 74 67 92 40 18 97 78 86 41 88
Output
10
Note

In the first testcase, one possible optimal sequence of operations would be: $$$[4,\underline{3},\underline{2},7,6,9] \rightarrow [4,5,7,\underline{6},\underline{9}] \rightarrow [4,5,7,15] $$$. It can shown that you can't make the array non-decreasing in less than $$$2$$$ operations.

In the second testcase, an optimal sequence of operations would be: $$$[55,\underline{50},\underline{87},17,36,90,6] \rightarrow [55,137,\underline{17},\underline{36},90,6]$$$ $$$\rightarrow [55,137,53,\underline{90},\underline{6}] \rightarrow [55,137,\underline{53},\underline{96}] \rightarrow [55,137,149] $$$.

F. Pull Smaller
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

Let's define an operation on $$$a$$$ as follows:

  • Pick two indices $$$i$$$ and $$$j$$$ such that $$$1 \le i \lt j \le n$$$ and $$$a_i \gt a_j$$$.
  • Place the element $$$a_j$$$ right before $$$a_i$$$  — that is in-between $$$a_{i-1}$$$ and $$$a_i$$$ if $$$i \gt 1$$$ and before the first element if $$$i = 1$$$.

For example, if the array is $$$a = [7, 1, \textbf{6}, 2, 4, 3, \textbf{5}]$$$, one of the possible operations is to set $$$i = 3$$$ and $$$j = 7$$$ to get the new array $$$[7, 1, \textbf{5}, \textbf{6}, 2, 4, 3]$$$.

Given a permutation $$$b$$$ of the array $$$a$$$, find out if $$$b$$$ is achievable from $$$a$$$ by repeatedly applying the operation on $$$a$$$ any number of times (possibly zero).

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 4 \cdot 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 3 \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 n$$$) — elements of the array.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le n$$$) — a permutation of the array $$$a$$$.

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

Output

For each test case, output on a single line the word "YES" (without quotes, case insensitive) if it is possible to turn the array $$$a$$$ into $$$b$$$ using the aforementioned operation, or "NO" (without quotes, case insensitive) if it is impossible to do so.

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

The possible solutions for all test cases are given below (the bolded elements are the pair chosen for that operation):

Test Case 1: $$$ [\text{2}, \textbf{4}, \text{3}, \textbf{1}] \rightarrow [\text{2}, \text{1}, \text{4}, \text{3}] $$$

Test Case 2: $$$ [\textbf{3}, \text{2}, \text{1}, \textbf{2}] \rightarrow [\text{2}, \text{3}, \text{2}, \text{1}] $$$

Test Case 3: $$$ [\textbf{3}, \textbf{1}, \text{2}, \text{1}] \rightarrow [\text{1}, \text{3}, \text{2}, \text{1}] $$$

Test Case 4: It can be shown that it is impossible to convert $$$a$$$ to $$$b$$$ by performing the operations.

Test Case 5: $$$ [\text{4}, \textbf{3}, \text{1}, \textbf{2}] \rightarrow [\text{4}, \text{2}, \textbf{3}, \textbf{1}] \rightarrow [\textbf{4}, \text{2}, \text{1}, \textbf{3}] \rightarrow [\text{3}, \text{4}, \text{2}, \text{1}] $$$