D. Нечётные запросы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив $$$a_1, a_2, \dots, a_n$$$. Ответьте на $$$q$$$ таких запросов:

  • Если сделать каждый элемент подотрезка массива $$$a_l, a_{l+1}, \dots, a_r$$$ равным $$$k$$$, будет ли сумма всего массива нечетной?

Обратите внимание, что запросы независимы и не влияют на будущие запросы.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит количество наборов входных данных $$$t$$$ ($$$1 \le t \le 10^4$$$). Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит $$$2$$$ целых числа $$$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$$$ строк содержат по $$$3$$$ целых числа $$$l,r,k$$$ ($$$1 \le l \le r \le n$$$; $$$1 \le k \le 10^9$$$) — запросы.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$ и сумма $$$q$$$ не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого запроса выведите «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\}$$$, сумма будет равна $$$2+3+3+3+2 = 13$$$, что нечетно, поэтому ответ будет «YES».
  • Если элементы на подотрезке $$$(2, 3)$$$ сделать равными $$$4$$$, то массив станет равняться $$$\{2, 4, 4, 3, 2\}$$$, сумма будет равна $$$2+4+4+3+2 = 15$$$, что нечетно, поэтому ответ будет «YES».
  • Если элементы на подотрезке $$$(1, 5)$$$ сделать равными $$$5$$$, то массив станет равняться $$$\{5, 5, 5, 5, 5\}$$$, сумма будет равна $$$5+5+5+5+5 = 25$$$, что нечетно, поэтому ответ будет «YES».
  • Если элементы на подотрезке $$$(1, 4)$$$ сделать равными $$$9$$$, то массив станет равняться $$$\{9, 9, 9, 9, 2\}$$$, сумма будет равна $$$9+9+9+9+2 = 38$$$, что четно, поэтому ответ будет «NO».
  • Если элементы на подотрезке $$$(2, 4)$$$ сделать равными $$$3$$$, то массив станет равняться $$$\{2, 3, 3, 3, 2\}$$$, сумма будет равна $$$2+3+3+3+2 = 13$$$, что нечетно, поэтому ответ будет «YES».