算法练习专栏——Codeforces——Codeforces Round 943 (Div. 3)

A. Maximize?

Problem - A - Codeforces

You are given an integer $x$. Your task is to find any integer $y (1≤y<x)$ such that $gcd(x,y)+y$ is maximum possible.

Note that if there is more than one y which satisfies the statement, you are allowed to find any.

$gcd(a,b)$is the Greatest Common Divisor of a and b. For example, $gcd(6,4)=2gcd(6,4)=2$.

Input

The first line contains a single integer $t (1≤t≤1000)$ — the number of test cases.

Each of the following $t$ lines contains a single integer $x (2≤x≤1000)$.

Output

For each test case, output any $y (1≤y<x)$, which satisfies the statement.

Example

input

7
10
7
21
100
2
1000
6

output

5
6
18
98
1
750
3

翻译

给你一个整数 $x$ 。你的任务是找出任意一个整数 $y (1≤y<x)$ ，使得 $\gcd(x,y)+y$ 为最大可能数。$y (1≤y<x) $ $\gcd(x,y)+y$ 最大。

注意，如果有一个以上的 $y$ 满足该语句，则允许你找出任何一个。

$\gcd(a,b)$ 是 $a$ 和 $b$ 的最大公约数。例如， $\gcd(6,4)=2$ 。

输入

第一行包含一个整数 $t$ ( $1 \le t \le 1000$ ) - 测试用例数。

下面每行 $t$ 都包含一个整数 $x$ ( $2 \le x \le 1000$ )。

输出

对于每个测试用例，输出任何满足声明的 $y$ ( $1 \le y \le x$ ) 。

Example

input

7
10
7
21
100
2
1000
6

output

5
6
18
98
1
750
3

思路

​ 直接暴力没啥好说的

代码

#include <bits/stdc++.h>

using namespace std;

void solve(){
    int n;
    cin >> n;
    int ans = 0, k;
    for (int i = 1; i < n; i++) {
        int kk = __gcd(n, i) + i;
        if (kk > ans) {
            k = i;
            ans = kk; 
        }
    } 

    cout << k << '\n';
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

B. Prefiquence

Problem - B - Codeforces

You are given two binary strings $a$ and $b$. A binary string is a string consisting of the characters ‘0’ and ‘1’.

Your task is to determine the maximum possible number $k$ such that a prefix of string $a$ of length $k$ is a subsequence of string $b$.

A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$​ by the deletion of several (possibly, zero or all) elements.

Input

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

The first line of each test case contains two integers $n$ and $m$ ($1\le n,m \le 2 \cdot 10^5$) — the length of string $a$ and the length of string $b$, respectively.

The second line of each test case contains a binary string $a$ of length $n$.

The third line of each test case contains a binary string $b$ of length $m$.

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

Output

For each test case, output a single number — the maximum $k$, such that the first $k$ characters of $a$ form a subsequence of $b$.

Note

In the first example, the string ‘$10$’ is a subsequence of ‘$1\color{red}11\color{red}0$’ but the string ‘$100$’ is not. So the answer is $2$.

In the fifth example, $a$=‘$100$’, $b$=‘$1\color{red}{10}1\color{red}0$’, whole string $a$ is a subsequence of string $b$. So the answer is $3$.

In the sixth example, string $b$ does not contain ‘$1$’ so the answer is $0$.

翻译

给你两个二进制字符串 $a$ 和 $b$ 。二进制字符串是由字符 “0 “和 “1 “组成的字符串。

您的任务是确定最大可能的数字 $k$ ，使得长度为 $k$ 的字符串 $a$ 的前缀是字符串 $$b$ 的子序列。

如果 $a$$ 可以从 $b$ 中删除几个(可能是零个或全部)元素，那么序列 $$a$$ 就是序列 $b 的子序列。

输入

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) - 测试用例数。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ( $1\le n,m \le 2 \cdot 10^5$ ) - 分别是字符串 $a$ 的长度和字符串 $b$ 的长度。

每个测试用例的第二行包含长度为 $n$ 的二进制字符串 $a$ 。

每个测试用例的第三行包含长度为 $m$ 的二进制字符串 $b$ 。

保证所有测试用例的值 $n$ 之和不超过 $2 \cdot 10^5$ 。同样，所有测试用例中 $m$ 的值之和不超过 $2 \cdot 10^5$ 。

注

在第一个例子中，字符串” $10$ “是” $1\color{red}11\color{red}0$ “的子序列，但字符串” $100$ “不是。因此答案是 $2$ 。

在第五个例子中， $a$ =’ $100$ ‘， $b$ =’ $1\color{red}{10}1\color{red}0$ ‘，整个字符串 $a$ 是字符串 $b$ 的子序列。所以答案是 $3$ 。

在第六个示例中，字符串 $b$ 不包含’ $1$ ‘，所以答案是 $0$ 。

Example

input

6
5 4
10011
1110
3 3
100
110
1 3
1
111
4 4
1011
1111
3 5
100
11010
3 1
100
0

output

2
2
1
1
3
0

思路

​ 一个简单的匹配问题，无他都是暴力。

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

void solve(){
    int n, m;
    int i, j;

    string a, b;
    cin >> n >> m;
    cin >> a >> b;
    for (i = 0, j = 0; i < n && j < m;) {
        if (a[i] == b[j]) {
            i++;
            j++;
        } else {
            j++;
        }
    }
    cout << i <<'\n';
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

C. Assembly via Remainders

Problem - C - Codeforces

You are given an array $x_2,x_3,\dots,x_n$. Your task is to find any array $a_1,\dots,a_n$, where:

• $1\le a_i\le 10^9$ for all $1\le i\le n$.
• $x_i=a_i \bmod a_{i-1}$ for all $2\le i\le n$.

Here $c\bmod d$ denotes the remainder of the division of the integer $c$ by the integer $d$. For example $5 \bmod 2 = 1$, $72 \bmod 3 = 0$, $143 \bmod 14 = 3$.

Note that if there is more than one $a$ which satisfies the statement, you are allowed to find any.

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$ $(2\le n\le 500)$ — the number of elements in $a$.

The second line of each test case contains $n-1$ integers $x_2,\dots,x_n$ $(1\le x_i\le 500)$ — the elements of $x$.

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

Output

For each test case output any $a_1,\dots,a_n$ ($1 \le a_i \le 10^9$) which satisfies the statement.

Example

input

5
4
2 4 1
3
1 1
6
4 2 5 1 2
2
500
3
1 5

output

3 5 4 9
2 5 11
5 14 16 5 11 24
501 500
2 7 5

Note

In the first test case $a=[3,5,4,9]$ satisfies the conditions, because:

• $a_2\bmod a_1=5\bmod 3=2=x_2$;
• $a_3\bmod a_2=4\bmod 5=4=x_3$;
• $a_4\bmod a_3=9\bmod 4=1=x_4$;

翻译

给你一个数组 $x_2,x_3,\dots,x_n$ 。你的任务是找出任意一个数组 $a_1,\dots,a_n$ ，其中：

• $1\le a_i\le 10^9$ 为所有的 $1\le i\le n$ 。
• $x_i=a_i \bmod a_{i-1}$ 代表所有的 $2\le i\le n$ 。

这里的 $c\bmod d$ 表示整数 $c$ 除以整数 $d$ 的余数。例如， $5 \bmod 2 = 1$ ， $72 \bmod 3 = 0$ ， $143 \bmod 14 = 3$ 。

注意，如果有一个以上的 $a$ 满足该语句的要求，你可以找到任何一个。

输入

第一行包含一个整数 $t$ $(1\le t\le 10^4)$ 。- 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ $(2\le n\le 500)$ - {7001414} 中的元素个数。 $(2\le n\le 500)$ - $a$ 中的元素个数。

每个测试用例的第二行包含 $n-1$ 个整数 $x_2,\dots,x_n$ - $a$ 中的元素个数。 $(1\le x_i\le 500)$ - $x$ 中的元素。

保证所有测试用例中 $n$ 的值之和不超过 $2 \cdot 10^5$ 。

输出

对于每个测试用例，输出任何满足语句的 $a_1,\dots,a_n$ ( $1 \le a_i \le 10^9$ )

注

第一个测试用例 $a=[3,5,4,9]$ 满足条件，因为

• $a_2\bmod a_1=5\bmod 3=2=x_2$ ;
• $a_3\bmod a_2=4\bmod 5=4=x_3$ ;
• $a_4\bmod a_3=9\bmod 4=1=x_4$ ;

思路

​ 完全就是一个数学问题，这个问题可以转为 a[i] ÷ a[i - 1] = k …… x[i - 1],最开始的a[1] 我们可以直接设置为x[1] + 1.然后从i = 2开始枚举，之后我们现在就是需要确定这个k就可以将这个a[i]推出来了，但是我们需要注意一个地方，就是你你得到的a[i]这个数必须 > x[i]，否则a[i + 1] % a[i]的时候就不可能得到x[i]了，具体的处理方式请看代码。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long LL;

const int N = 510;
const int INF = 1e9;

LL x[N], a[N];

void solve(){
    int n;
    cin >> n;
    for (int i = 1; i <= n - 1; i++) cin >> x[i];   

    a[1] = x[1] + 1;
    for (int i = 2; i <= n; i++) {
        int k = 0;
        int kk = x[i - 1] + a[i - 1];
        if (x[i] < kk) a[i] = kk;
        else a[i] = a[i - 1] * ceil(1.0 * x[i] / a[i - 1]) + x[i - 1];
    } 

    for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n];
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

D：Permutation Game

Bodya and Sasha found a permutation $p_1,\dots,p_n$ and an array $a_1,\dots,a_n$. They decided to play a well-known “Permutation game”.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Both of them chose a starting position in the permutation.

The game lasts $k$ turns. The players make moves simultaneously. On each turn, two things happen to each player:

• If the current position of the player is $x$, his score increases by $a_x$.
• Then the player either stays at his current position $x$ or moves from $x$ to $p_x$.

The winner of the game is the player with the higher score after exactly $k$ turns.

Knowing Bodya’s starting position $P_B$ and Sasha’s starting position $P_S$, determine who wins the game if both players are trying to win.

Input

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

The first line of each testcase contains integers $n$, $k$, $P_B$, $P_S$ ($1\le P_B,P_S\le n\le 2\cdot 10^5$, $1\le k\le 10^9$) — length of the permutation, duration of the game, starting positions respectively.

The next line contains $n$ integers $p_1,\dots,p_n$ ($1 \le p_i \le n$) — elements of the permutation $p$.

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

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

Output

For each testcase output:

• “Bodya” if Bodya wins the game.
• “Sasha” if Sasha wins the game.
• “Draw” if the players have the same score.

Example

input

10
4 2 3 2
4 1 2 3
7 2 5 6
10 8 2 10
3 1 4 5 2 7 8 10 6 9
5 10 5 1 3 7 10 15 4 3
2 1000000000 1 2
1 2
4 4
8 10 4 1
5 1 4 3 2 8 6 7
1 1 2 1 2 100 101 102
5 1 2 5
1 2 4 5 3
4 6 9 4 2
4 2 3 1
4 1 3 2
6 8 5 3
6 9 5 4
6 1 3 5 2 4
6 9 8 9 5 10
4 8 4 2
2 3 4 1
5 2 8 7
4 2 3 1
4 1 3 2
6 8 5 3
2 1000000000 1 2
1 2
1000000000 2

output

Bodya
Sasha
Draw
Draw
Bodya
Sasha
Sasha
Sasha
Sasha
Bodya

Note

Below you can find the explanation for the first testcase, where the game consists of $k=2$ turns.

Turn	Bodya’s position	Bodya’s score	Bodya’s move	Sasha’s position	Sasha’s score	Sasha’s move
first	$3$	$0 + a_3 = 0 + 5 = 5$	stays on the same position	$2$	$0 + a_2 = 0 + 2 = 2$	moves to $p_2=1$
second	$3$	$5 + a_3 = 5 + 5 = 10$	stays on the same position	$1$	$2 + a_1 = 2 + 7 = 9$	stays on the same position
final results	$3$	$10$		$1$	$9$

As we may see, Bodya’s score is greater, so he wins the game. It can be shown that Bodya always can win this game.

翻译

Bodya 和 Sasha 发现了一个排列 $p_1,\dots,p_n$ 和一个数组 $a_1,\dots,a_n$ 。他们决定玩一个著名的 “排列游戏”。

长度为 $n$ 的排列是由 $n$ 个不同的整数组成的数组，这些整数从 $1$ 到 $n$ 按任意顺序排列。例如， $[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列（ $2$ 在数组中出现了两次）， $[1,3,4]$ 也不是一个排列（ $n=3$ ，但数组中有 $4$ ）。

它们都在排列中选择了一个起始位置。

对局持续了 $k$ 个回合。棋手同时下棋。在每个回合中，每个棋手都会发生两件事：

• 如果棋手当前的位置是 $x$ ，那么他的得分就会增加 $a_x$ 。
• 然后棋手要么停留在当前位置 $x$ ，要么从 $x$ 移动到 $p_x$ 。

在整整 $k$ 个回合后，得分较高的棋手即为获胜者。

知道了博迪娅的起始位置 $P_B$ 和萨沙的起始位置 $P_S$​ 后，如果双方都想获胜，那么谁会赢得对局？

输出

每个测试用例的输出：

• 如果 Bodya 赢得游戏，则输出 “Bodya”。
• 如果 Sasha 赢得比赛，则输出 “Sasha”。
• 如果双方得分相同，则输出 “平局”。

Example

input

10
4 2 3 2
4 1 2 3
7 2 5 6
10 8 2 10
3 1 4 5 2 7 8 10 6 9
5 10 5 1 3 7 10 15 4 3
2 1000000000 1 2
1 2
4 4
8 10 4 1
5 1 4 3 2 8 6 7
1 1 2 1 2 100 101 102
5 1 2 5
1 2 4 5 3
4 6 9 4 2
4 2 3 1
4 1 3 2
6 8 5 3
6 9 5 4
6 1 3 5 2 4
6 9 8 9 5 10
4 8 4 2
2 3 4 1
5 2 8 7
4 2 3 1
4 1 3 2
6 8 5 3
2 1000000000 1 2
1 2
1000000000 2

output

Bodya
Sasha
Draw
Draw
Bodya
Sasha
Sasha
Sasha
Sasha
Bodya

注

下面是第一个测试案例的说明，其中游戏由 $k=2$ 个回合组成。

Turn	Bodya’s position	Bodya’s score	Bodya’s move	Sasha’s position	Sasha’s score	Sasha’s move
first	$3$	$0 + a_3 = 0 + 5 = 5$	stays on the same position	$2$	$0 + a_2 = 0 + 2 = 2$	moves to $p_2=1$
second	$3$	$5 + a_3 = 5 + 5 = 10$	stays on the same position	$1$	$2 + a_1 = 2 + 7 = 9$	stays on the same position
final results	$3$	$10$		$1$	$9$

我们可以看到，Bodya 的得分更高，因此他赢得了比赛。由此可见，博迪亚总是能赢得这盘棋。

思路

​ 稍微分析一下，我们其实就可以很快得出一个结论：就是我们如果选择停下来的话就会一直停留到结束，这个结论显然是不言而喻的。这样的话我们思路其实就蛮清晰了，每到一个位置我们就计算一下下面的轮次一直留在这个位置的总时间和ans取max即可，最后比较一下ansa和ansb两个大小即可。

代码

#include<bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;


signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int t; cin >> t;
	while (t--) {
		int n, k, pb, ps; cin >> n >> k >> pb >> ps;
		vector<int> p(n + 5), a(n + 5);
		for (int i = 1; i <= n; i++)cin >> p[i];
		for (int i = 1; i <= n; i++)cin >> a[i];
		
		
		int maxi = 0;
		for (int i = 1; i <= n; i++) maxi = max(maxi, a[i]);

		int turn = 0; 
		int cost = 0; 
		int ansb = 0;
		vector<bool> visb(n + 5);
		for (int pos = pb;;) {
			int now = cost + (k - turn) * a[pos]; 
			ansb = max(ansb, now);
			turn++;
			cost += a[pos];
			if (a[pos] == maxi)break;
			visb[pos] = 1;
			pos = p[pos];
			if (turn == k || visb[pos])break;
		}

		turn = 0;
		cost = 0;
		int anss = 0;
		vector<bool> viss(n + 5);
		for (int pos = ps;;) {
			int now = cost + (k - turn) * a[pos]; 
			anss = max(anss, now);
			turn++;
			cost += a[pos];
			if (a[pos] == maxi) break;
			viss[pos] = 1;
			pos = p[pos];
			if (turn == k || viss[pos]) break;
		}

		if (ansb > anss) cout<<"Bodya"<<endl;
		else if (anss > ansb) cout<<"Sasha"<<endl
		else cout<<"Draw"<<endl
	}


	return 0;
}

E：Cells Arrangement

You are given an integer $n$. You choose $n$ cells $(x_1,y_1), (x_2,y_2),\dots,(x_n,y_n)$ in the grid $n\times n$ where $1\le x_i\le n$ and $1\le y_i\le n$.

Let $\mathcal{H}$ be the set of distinct Manhattan distances between any pair of cells. Your task is to maximize the size of $\mathcal{H}$. Examples of sets and their construction are given in the notes.

If there exists more than one solution, you are allowed to output any.

Manhattan distance between cells $(x_1,y_1)$ and $(x_2,y_2)$ equals $|x_1-x_2|+|y_1-y_2|$.

Input

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

Each of the following $t$ lines contains a single integer $n$ ($2\le n\le 10^3$​).

Output

For each test case, output $n$ points which maximize the size of $\mathcal{H}$. It is not necessary to output an empty line at the end of the answer for each test case.

Example

input

5
2
3
4
5
6

output

1 1
1 2

2 1
2 3
3 1

1 1
1 3
4 3
4 4

1 1
1 3
1 4
2 1
5 5

1 4
1 5
1 6
5 2
5 5
6 1

Note

In the first testcase we have $n=2$. One of the possible arrangements is:

The arrangement with cells located in $(1,1)$ and $(1,2)$.

In this case $\mathcal{H}={|1-1|+|1-1|,|1-1|+|2-2|,|1-1|+|1-2|}={0,0,1}={0,1}$. Hence, the size of $\mathcal{H}$ is $2$. It can be shown that it is the greatest possible answer.

In the second testcase we have $n=3$. The optimal arrangement is:

The arrangement with cells located in $(2,1)$, $(2,3)$ and $(3,1)$.

$\mathcal{H}$=${|2-2|+|1-1|,|2-2|+|3-3|,|3-3|+|1-1|,|2-2|+|1-3|,|2-3|+|1-1|,|2-3|+|3-1|}$=${0,0,0,2,1,3}$=${0,1,2,3}$.

For $n=4$ a possible arrangement is:

For $n=5$ a possible arrangement is:

For $n=6$ a possible arrangement is:

翻译

给你一个整数 $n$。您在网格 $n\times n$ 中的 $n$ 单元格 $(x_1,y_1), (x_2,y_2),\dots,(x_n,y_n))$ 中选择 $1\le x_i \le n$ 和 $1\le y_i \le n$$ 。

假设 $$\mathcal{H}$$ 是任意一对单元格之间不同的曼哈顿距离集合。你的任务是最大化 $$\mathcal{H}$$ 的大小。注释中给出了集合及其构造的例子。

如果存在多个解，你可以输出任意一个。

单元格$$(x_1,y_1), (x_2,y_2)$$ 之间的曼哈顿距离等于 $$|x_1 - x_2|+|y_1 - y_2|$$ 。

输入

第一行包含一个整数 $t$ ( $1\le t\le 50$ )。( $1\le t\le 50$ ) - 测试用例的数量。

下面每行 $t$ 都包含一个整数 $n$ ( $2\le n\le 10^3$$ )。

输出

对于每个测试用例，输出 $n$ 个点，使 $\mathcal{H}$ 的大小达到最大。无需在每个测试用例的答案末尾输出空行。

Example

input

5
2
3
4
5
6

output

1 1
1 2

2 1
2 3
3 1

1 1
1 3
4 3
4 4

1 1
1 3
1 4
2 1
5 5

1 4
1 5
1 6
5 2
5 5
6 1

注

在第一个测试案例中，我们有 $n=2$ 。其中一种可能的排列方式是

单元格位于 $(1,1)$ 和 $(1,2)$ 的排列。

在这种情况下为 $\mathcal{H}={|1-1|+|1-1|,|1-1|+|2-2|,|1-1|+|1-2|}={0,0,1}={0,1}$ 。因此， $\mathcal{H}$ 的大小为 $2$ 。可以证明这是最可能的答案。

在第二个测试案例中，我们有 $n=3$ 。最佳排列是

单元格位于 $(2,1)$ 、 $(2,3)$ 和 $(3,1)$ 的排列。

$\mathcal{H}$ = ${|2-2|+|1-1|,|2-2|+|3-3|,|3-3|+|1-1|,|2-2|+|1-3|,|2-3|+|1-1|,|2-3|+|3-1|}$ = ${0,0,0,2,1,3}$ = ${0,1,2,3}$ .

对于 $n=4$ ，一种可能的排列方式是：

对于 $n=5$ ，可能的排列方式是：

对于 $n=6$ ，一种可能的排列方式是：

思路

​ 一般来说这种题目我一般第一个想法大多都是取寻找一下对角线这种情况，但是对于这种情况我们只可以得到$2,4,6,…,2(n - 1)$,这些情况，如果我们可以找到一种情况找到$1~2(n - 1)$的话，这种方式就一定是最优解，怎么搞呢？我们需要知道我们之所以对角线只能弄出这种偶数的倍数的情况是因为每个点之间的距离都是2的倍数，那么我们将其中$2$个点之间的位置的长度设置为1就可以了，这个操作可以选择将第2个结点的位置设置为$(1, 2)$即可。

代码

#include <cstring>
#include <iostream>
using namespace std;
void solve() {
    int n;
    cin >> n;
    cout << "1 1\n";
    cout << "1 2\n";
    for (int i = 3; i <= n; i++) {
        cout << i << " " << i << '\n';
    }
    puts("");
}
int main()
{
    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

F. Equal XOR Segments)(continous study……)

Let us call an array $x_1,\dots,x_m$ interesting if it is possible to divide the array into $k\gt1$ parts so that bitwise XOR of values from each part are equal.

More formally, you must split array $x$ into $k$ consecutive segments, each element of $x$ must belong to exactly $1$ segment. Let $y_1,\dots,y_k$ be the XOR of elements from each part respectively. Then $y_1=y_2=\dots=y_k$ must be fulfilled.

For example, if $x = [1, 1, 2, 3, 0]$, you can split it as follows: $[\color{blue}1], [\color{green}1], [\color{red}2, \color{red}3, \color{red}0]$. Indeed $\color{blue}1=\color{green}1=\color{red}2 \oplus \color{red}3\oplus \color{red}0$.

You are given an array $a_1,\dots,a_n$. Your task is to answer $q$ queries:

• For fixed $l$, $r$, determine whether the subarray $a_l,a_{l+1},\dots,a_r$ is interesting.

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 two integers $n$ and $q$ ($2 \le n \le 2 \cdot 10^5$, $1 \le q \le 2 \cdot 10^5$) — the number of elements in the array and the number of queries respectively.

The next line contains $n$ integers $a_1,\dots,a_n$ ($0 \le a_i \lt 2^{30}$) — elements of the array.

Each of the next $q$ lines contains two integers $l$ and $r$ ($1 \le l \lt r \le n$) describing the query.

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

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

Output

For each query, output “YES” if the subarray is interesting and “NO” otherwise.

You can output “Yes” and “No” in any case (for example, the strings “yES”, “yes”, and “Yes” will be recognized as correct answers).

Example

input

4
5 5
1 1 2 3 0
1 5
2 4
3 5
1 3
3 4
5 5
1 2 3 4 5
1 5
2 4
3 5
1 3
2 3
7 4
12 9 10 9 10 11 9
1 5
1 7
2 6
2 7
11 4
0 0 1 0 0 1 0 1 1 0 1
1 2
2 5
6 9
7 11

output

YES
YES
NO
NO
NO

YES
NO
NO
YES
NO

NO
NO
NO
NO

YES
NO
YES
YES

Note

Explanation for the first test case:

The first query is described in the statement.

In the second query, we should divide $[1,2,3]$. A possible division is $[1,2],[3]$, since $1\oplus 2=3$.

It can be shown that for queries $3,4,5$, the subarrays are not interesting.

翻译

如果可以将数组分成 $k\gt 1$ 部分，使得每一部分的值的 bitwise XOR 都相等，那么我们就称这个数组为 $x_1,\dots,x_m$ 有意思。

更正式地说，你必须将数组 $x$ 分割成 $k$ 个连续的部分，而 $x$ 中的每个元素都必须准确地**属于 $1$ 个部分。设 $y_1,\dots,y_k$ 分别是各部分元素的 XOR。那么 $y_1=y_2=\dots=y_k$ 必须满足。

例如，如果是 $x = [1, 1, 2, 3, 0]$ ，可以将其拆分如下： $[\color{blue}1], [\color{green}1], [\color{red}2, \color{red}3, \color{red}0]$ .确实是 $\color{blue}1=\color{green}1=\color{red}2 \oplus \color{red}3\oplus \color{red}0$ 。

给你一个数组 $a_1,\dots,a_n$ 。你的任务是回答 $q$ 个查询：

• 对于固定的 $l$ , $r$ , 判断子数组 $a_l,a_{l+1},\dots,a_r$​ 是否有趣。

输入

第一行包含一个整数 $t$ ( $1\le t\le 10^4$ ) - 测试用例数。

每个测试用例的第一行包含两个整数 $n$ 和 $q$ ( $2 \le n \le 2 \cdot 10^5$ , $1 \le q \le 2 \cdot 10^5$ )–分别是数组中的元素个数和查询次数。

下一行包含 $n$ 个整数 $a_1,\dots,a_n$ ( $0 \le a_i \lt 2^{30}$ ) - 数组元素。

接下来的 {326120} 行分别包含两个整数 $l$ 和 $r$ ( $1 \le l \lt r \le n$ )，用于描述查询。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$ 。

保证所有测试用例中 $q$ 的总和不超过 $2 \cdot 10^5$​ 。

输出

对于每个查询，如果子数组有趣，则输出 “YES”，否则输出 “NO”。

您可以在任何情况下输出 “YES “和 “NO”（例如，字符串 “yES”、”yes “和 “Yes “将被识别为正确答案）。

Example

input

4
5 5
1 1 2 3 0
1 5
2 4
3 5
1 3
3 4
5 5
1 2 3 4 5
1 5
2 4
3 5
1 3
2 3
7 4
12 9 10 9 10 11 9
1 5
1 7
2 6
2 7
11 4
0 0 1 0 0 1 0 1 1 0 1
1 2
2 5
6 9
7 11

output

YES
YES
NO
NO
NO

YES
NO
NO
YES
NO

NO
NO
NO
NO

YES
NO
YES
YES

注

第一个测试案例的解释：

语句中描述了第一个查询。

在第二个查询中，我们应该除以 $[1,2,3]$ 。可能的除法是 $[1,2],[3]$ ，因为 $1\oplus 2=3$ 。

可以证明，对于查询 $3,4,5$ ，子数组并不重要。

思路

        $bitwise XOR$表示：按位异或运算符。
    
        **前沿：**
    
        ​	这道题目的话我们基本只需要知道一件事情就很简单了，就是异或操作是有前缀和的性质的，因为异或操作的特征之一：相同为0，不同为1。如此假设我们求出了前l项和r项的异或和，那么我们要是想找到l~r项的异或和的话就只需要a[r] ^ a[l - 1]，前面的异或是相同的，所以会直接相同抵消为0。
    
        **思路：**
    
        ​	这道题目我们稍微推导一下就可以知道，如果一个子序列满足条件，就一定满足以下条件之一：
    
        - 全部异或和为0
        - 可以分为3段异或和，又由于3段异或和是相同的，所以l~第2段的右端点位置j的异或和为0.也就是说设三段的4个端点分别为**l, i, j, r**，那么我们其实是可以知道$a[i] = a[r]$的，同时$a[j] = a[l - 1]$的。如此我们只要使用一个$Map$存一下各个异或和对应的下标，然后我们在需要寻找对应异或和下标的时候对其进行二分查找即可，时间复杂度为$O(qlogn)$

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 2e5 + 10;

LL a[N];

void solve() {
    map<int, vector<int>> Map;
    int n, q, ii;
    cin >> n >> q;
    fore (ii, 1, n) cin >> a[ii];
    fore (ii, 1, n) {
        a[ii] ^= a[ii - 1];
        Map[a[ii]].push_back(ii);
    }

    while (q--) {
        int l, r, k;
        cin >> l >> r;
        k = a[r] ^ a[l - 1];
        if (k == 0) {
            cout << "YES" << ed;
            continue;
        }
        
        // 1、快速找到 i >= l的最小下标使得 s[i] = s[r]
		auto i = lower_bound(Map[a[r]].begin(),Map[a[r]].end(),l) ;
		if(i == Map[a[r]].end() || *i >= r){
			cout << "NO" << ed ;
			continue;
		}
		// 2、快速找到最小的 j > i 使 s[j] = s[l - 1]
		auto j = upper_bound(Map[a[l - 1]].begin(),Map[a[l - 1]].end(), *i);

		if(j == Map[a[l - 1]].end()){
		    cout << "NO" << ed;
		    continue;
		}
		if(*i < *j && *j < r) cout << "YES" << ed ;
		else cout << "NO" << ed ;
	} 
    cout << ed;
}
int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    while(_--) {
        solve();
    }
    re 0;
}