D. Odd Queries

本文主要是介绍D. Odd Queries，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You have an array a1,a2,…,an�1,�2,…,��. Answer q� queries of the following form:

• If we change all elements in the range al,al+1,…,ar��,��+1,…,�� 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≤t≤1041≤�≤104). The description of the test cases follows.

The first line of each test case consists of 22 integers n� and q� (1≤n≤2⋅1051≤�≤2⋅105; 1≤q≤2⋅1051≤�≤2⋅105) — the length of the array and the number of queries.

The second line of each test case consists of n� integers ai�� (1≤ai≤1091≤��≤109) — the array a�.

The next q� lines of each test case consists of 33 integers l,r,k�,�,� (1≤l≤r≤n1≤�≤�≤�; 1≤k≤1091≤�≤109) — the queries.

It is guaranteed that the sum of n� over all test cases doesn't exceed 2⋅1052⋅105, and the sum of q� doesn't exceed 2⋅1052⋅105.

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.

Example

input

Copy

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

Copy

YES
YES
YES
NO
YES
NO
NO
NO
NO
YES

Note

For the first test case:

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

解题说明：水题，根据题目意思直接求和累加进行判断即可。

#include<stdio.h>
int a[200005];
int main()
{int t;int n, q;int l, r, k;int sum = 0;int i, j, x;scanf("%d", &t);for (i = 1; i <= t; i++) {scanf("%d %d", &n, &q);for (j = 1; j <= n; j++) {scanf("%d", &x);a[j] = a[j - 1] + x;}for (j = 0; j < q; j++) {scanf("%d %d %d", &l, &r, &k);sum = (a[l - 1] - a[0]) + (a[n] - a[r]) + k * (r - l + 1);if (sum % 2 == 0){printf("NO\n");}else{printf("YES\n");}}}return 0;
}

这篇关于D. Odd Queries的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---