KONGJUNE / / ACM / 阅读量

B - Intersting Subarray

For an array $a$ of integers let's denote its maximal element as $\max(a)$, and minimal as $\min(a)$. We will call an array $a$ of $k$ integers interesting if $\max(a)−\min(a)\geq k$. For example, array $[1,3,4,3]$ isn't interesting as $\max(a)−\min(a)=4−1=3<4$ while array $[7,3,0,4,3]$ is as $\max(a)−\min(a)=7−0=7\geq 5$.

You are given an array $a$ of $n$ integers. Find some interesting nonempty subarray of $a$

, or tell that it doesn't exist.

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 integer number $t$ $(1\leq t\leq 10000)$. Then $t$ test cases follow.

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

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n (0≤a_i≤10^9)$ — the elements of the array.

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

Output

For each test case, output "NO" in a separate line if there is no interesting nonempty subarray in $a$.

Otherwise, output "YES" in a separate line. In the next line, output two integers $l$ and $r$ $(1≤l≤r≤n)$ — bounds of the chosen subarray. If there are multiple answers, print any.

You can print each letter in any case (upper or lower).

Example

Input

3
5
1 2 3 4 5
4
2 0 1 9
2
2019 2020


Output

NO
YES
1 4
NO


Note

In the second test case of the example, one of the interesting subarrays is $a=[2,0,1,9]$: $\max(a)−\min(a)=9−0=9≥4$.

AC代码：

#include <iostream>
using namespace std;
int a[200005];
int main(){
ios::sync_with_stdio(false);
int T;
cin >> T;
while(T--) {
int n;
cin >> n;
int l, r;
bool yes = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (i && abs(a[i] - a[i - 1]) > 1) {
l = i;
r = i + 1;
yes = 1;
}
}
if (yes) {
cout << "YES" << endl << l << " " << r << endl;
} else cout << "NO" << endl;

}
}


C - Make Good

Let's call an array $a_1,a_2,…,a_m$ of nonnegative integer numbers good if $a_1+a_2+⋯+a_m=2⋅(a_1⊕a_2⊕⋯⊕a_m)$, where $⊕$ denotes the bitwise XOR operation.

For example, array $[1,2,3,6]$ is good, as $1+2+3+6=12=2⋅6=2⋅(1⊕2⊕3⊕6)$. At the same time, array $[1,2,1,3]$ isn't good, as $1+2+1+3=7≠2⋅1=2⋅(1⊕2⊕1⊕3)$.

You are given an array of length $n$ : $a_1,a_2,…,a_n$. Append at most 3 elements to it to make it good. Appended elements don't have to be different. It can be shown that the solution always exists under the given constraints. If there are different solutions, you are allowed to output any of them. Note that you don't have to minimize the number of added elements! So, if an array is good already you are allowed to not append elements.

Input

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

The first line of each test case contains a single integer $n(1≤n≤105)$ — the size of the array.

The second line of each test case contains $n$ integers $a_1,a_2,…,a_n (0≤a_i≤109)$ — the elements of the array.

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

Output

For each test case, output two lines.

In the first line, output a single integer $s$ $(0≤s≤3)$ — the number of elements you want to append.

In the second line, output $s$ integers $b_1,…,b_s (0≤b_i≤1018)$ — the elements you want to append to the array.

If there are different solutions, you are allowed to output any of them.

Example

Input

3
4
1 2 3 6
1
8
2
1 1


Output

0

2
4 4
3
2 6 2


Note

In the first test case of the example, the sum of all numbers is $12$, and their $⊕$ is $6$ , so the condition is already satisfied.

In the second test case of the example, after adding $4$, $4$, the array becomes $[8,4,4]$. The sum of numbers in it is $16$, $⊕$ of numbers in it is $8$.

$$x + y + \mathrm{sum} = 2 \cdot (x⊕y⊕\mathrm{xorSum})$$

AC代码：

#include <iostream>
using namespace std;
int a[200005];
int main(){
ios::sync_with_stdio(false);
int T;
cin >> T;
while(T--) {
long long sum = 0;
long long xorV = 0;
int n;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
sum += a[i];
xorV ^= a[i];
}
long long x, y;
if(sum == 2 * xorV){
cout << 0 << endl << endl;
} else  {
x = xorV;
y = xorV + sum;
if (x){
cout << 2 << endl << x << " " << y << endl;
} else cout << 1 << endl << y << endl;
}
}
}


D - Strange Device

AC代码：

#include <iostream>
using namespace std;
int main(){
int n, k;
cin >> n >> k;
int m = k;
for (int i = 1; i <= k; i++) {
a[i] = i + 1;
}
int maxV = 0;
int cnt = 0;
fflush(stdout);
for (int i = 1; i <= k + 1; i++) {
cout << "?";
for (int i = 1; i <= k; i++) {
cout << " " << a[i];
}
cout << endl;
int n, v;
cin >> n >> v;
if (v > maxV) {
maxV = v;
cnt = 1;
} else if (v == maxV) {
cnt++;
}
a[i] = i;
}
cout << "! " << cnt << endl;
}