310267: CF1807D. Odd Queries

D. Odd Queriestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have an array $a_1, a_2, \dots, a_n$. Answer $q$ queries of the following form:

• If we change all elements in the range $a_l, a_{l+1}, \dots, a_r$ of the array to $k$, will the sum of the entire array be odd?

Note that queries are independent and do not affect future queries.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 consists of $2$ integers $n$ and $q$ ($1 \le n \le 2 \cdot 10^5$; $1 \le q \le 2 \cdot 10^5$) — the length of the array and the number of queries.

The second line of each test case consists of $n$ integers $a_i$ ($1 \le a_i \le 10^9$) — the array $a$.

The next $q$ lines of each test case consists of $3$ integers $l,r,k$ ($1 \le l \le r \le n$; $1 \le k \le 10^9$) — the queries.

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

Output

For each query, output "YES" if the sum of the entire array becomes odd, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

ExampleInput

2
5 5
2 2 1 3 2
2 3 3
2 3 4
1 5 5
1 4 9
2 4 3
10 5
1 1 1 1 1 1 1 1 1 1
3 8 13
2 5 10
3 8 10
1 10 2
1 9 100

Output

YES
YES
YES
NO
YES
NO
NO
NO
NO
YES

Note

For the first test case:

• If the elements in the range $(2, 3)$ would get set to $3$ the array would become $\{2, 3, 3, 3, 2\}$, the sum would be $2+3+3+3+2 = 13$ which is odd, so the answer is "YES".
• If the elements in the range $(2, 3)$ would get set to $4$ the array would become $\{2, 4, 4, 3, 2\}$, the sum would be $2+4+4+3+2 = 15$ which is odd, so the answer is "YES".
• If the elements in the range $(1, 5)$ would get set to $5$ the array would become $\{5, 5, 5, 5, 5\}$, the sum would be $5+5+5+5+5 = 25$ which is odd, so the answer is "YES".
• If the elements in the range $(1, 4)$ would get set to $9$ the array would become $\{9, 9, 9, 9, 2\}$, the sum would be $9+9+9+9+2 = 38$ which is even, so the answer is "NO".
• If the elements in the range $(2, 4)$ would get set to $3$ the array would become $\{2, 3, 3, 3, 2\}$, the sum would be $2+3+3+3+2 = 13$ which is odd, so the answer is "YES".

题目大意：给定一个数组 $a_1, a_2, \dots, a_n$，回答 $q$ 个查询，每次查询的形式是：如果将数组中 $a_l, a_{l+1}, \dots, a_r$ 的所有元素改为 $k$，整个数组的和是否会变成奇数？注意，查询是独立的，不会影响后续查询。

输入输出数据格式：

输入：
- 第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 2 \cdot 10^5$；$1 \le q \le 2 \cdot 10^5$），分别表示数组的长度和查询的数量。
- 第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$），表示数组 $a$。
- 接下来的 $q$ 行，每行包含三个整数 $l, r, k$（$1 \le l \le r \le n$；$1 \le k \le 10^9$），表示一个查询。

输出：
- 对于每个查询，如果整个数组的和变为奇数，输出 "YES"，否则输出 "NO"。
- 输出可以是任何大小写形式，例如 "yEs"、"yes"、"Yes" 或 "YES" 都会被认为是肯定的回答。

示例：

输入：
```
2
5 5
2 2 1 3 2
2 3 3
2 3 4
1 5 5
1 4 9
2 4 3
10 5
1 1 1 1 1 1 1 1 1 1
3 8 13
2 5 10
3 8 10
1 10 2
1 9 100
```

输出：
```
YES
YES
YES
NO
YES
NO
NO
NO
NO
YES
```

注意：对于第一个测试用例，如果将 (2, 3) 范围内的元素设置为 3，数组将变为 {2, 3, 3, 3, 2}，和为 13，是奇数，所以答案是 "YES"。如果将 (2, 3) 范围内的元素设置为 4，数组将变为 {2, 4, 4, 3, 2}，和为 15，是奇数，所以答案是 "YES"。以此类推。题目大意：给定一个数组 $a_1, a_2, \dots, a_n$，回答 $q$ 个查询，每次查询的形式是：如果将数组中 $a_l, a_{l+1}, \dots, a_r$ 的所有元素改为 $k$，整个数组的和是否会变成奇数？注意，查询是独立的，不会影响后续查询。 输入输出数据格式： 输入： - 第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 2 \cdot 10^5$；$1 \le q \le 2 \cdot 10^5$），分别表示数组的长度和查询的数量。 - 第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$），表示数组 $a$。 - 接下来的 $q$ 行，每行包含三个整数 $l, r, k$（$1 \le l \le r \le n$；$1 \le k \le 10^9$），表示一个查询。 输出： - 对于每个查询，如果整个数组的和变为奇数，输出 "YES"，否则输出 "NO"。 - 输出可以是任何大小写形式，例如 "yEs"、"yes"、"Yes" 或 "YES" 都会被认为是肯定的回答。 示例： 输入： ``` 2 5 5 2 2 1 3 2 2 3 3 2 3 4 1 5 5 1 4 9 2 4 3 10 5 1 1 1 1 1 1 1 1 1 1 3 8 13 2 5 10 3 8 10 1 10 2 1 9 100 ``` 输出： ``` YES YES YES NO YES NO NO NO NO YES ``` 注意：对于第一个测试用例，如果将 (2, 3) 范围内的元素设置为 3，数组将变为 {2, 3, 3, 3, 2}，和为 13，是奇数，所以答案是 "YES"。如果将 (2, 3) 范围内的元素设置为 4，数组将变为 {2, 4, 4, 3, 2}，和为 15，是奇数，所以答案是 "YES"。以此类推。