F. Удивительные самозванцы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы гордый стример по имени Джиджи Мурин. Сегодня вы будете играть в игру с $$$n$$$ зрителями, пронумерованными от $$$1$$$ до $$$n$$$.

В игре каждый игрок является либо членом экипажа, либо самозванцем. Вы не знаете роли каждого зрителя.

Существует $$$m$$$ утверждений, пронумерованных от $$$1$$$ до $$$m$$$, которые могут быть истинными или ложными. Для каждого $$$i$$$ от $$$1$$$ до $$$m$$$, утверждение $$$i$$$ является одним из двух типов:

  • $$$0\:a_i\:b_i$$$ ($$$1 \leq a_i \leq b_i \leq n$$$) — среди зрителей $$$a_i, a_i + 1, \ldots, b_i$$$ нет самозванцев;
  • $$$1\:a_i\:b_i$$$ ($$$1 \leq a_i \leq b_i \leq n$$$) — среди зрителей $$$a_i, a_i + 1, \ldots, b_i$$$ есть хотя бы один самозванец.

Ответьте на $$$q$$$ вопросов следующего вида:

  • $$$l\:r$$$ ($$$1 \leq l \leq r \leq m$$$) — возможно ли, что все утверждения $$$l, l + 1, \ldots, r$$$ истинны?

Обратите внимание, что не гарантируется, что среди всех зрителей есть хотя бы один самозванец, и не гарантируется, что среди всех зрителей есть хотя бы один член экипажа.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$) — количество зрителей и количество утверждений.

$$$i$$$-я из следующих $$$m$$$ строк содержит три целых числа $$$x_i$$$, $$$a_i$$$, $$$b_i$$$ ($$$x_i \in \{0, 1\}$$$, $$$1 \leq a_i \leq b_i \leq n$$$) — описание утверждения $$$i$$$.

Следующая строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество вопросов.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \leq l \leq r \leq m$$$) — описание вопроса.

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

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

Для каждого вопроса выведите «YES», если возможно, что запрашиваемые утверждения все истинны. В противном случае выведите «NO».

Вы можете выводить ответ в любом регистре (верхнем или нижнем). Например, строки «yEs», «yes», «Yes», и «YES» будут распознаны как положительные ответы.

Пример
Входные данные
4
4 3
1 1 3
1 2 4
0 2 3
1
1 3
5 2
0 1 5
1 1 5
3
1 1
2 2
1 2
1 2
0 1 1
1 1 1
2
1 1
2 2
7 9
1 2 2
1 4 5
0 5 6
1 2 2
1 1 1
0 4 7
0 3 7
0 2 7
0 6 6
5
1 5
2 6
3 7
4 8
5 9
Выходные данные
YES
YES
YES
NO
YES
YES
YES
NO
YES
NO
YES
Примечание

В первом наборе входных данных есть $$$4$$$ зрителя и $$$3$$$ утверждения. Утверждения следующие:

  • Утверждение $$$1$$$: Среди зрителей $$$1$$$, $$$2$$$ и $$$3$$$ есть хотя бы один самозванец;
  • Утверждение $$$2$$$: Среди зрителей $$$2$$$, $$$3$$$ и $$$4$$$ есть хотя бы один самозванец;
  • Утверждение $$$3$$$: Среди зрителей $$$2$$$ и $$$3$$$ нет самозванцев.

Мы можем видеть, что возможно, что все утверждения $$$1$$$, $$$2$$$ и $$$3$$$ истинны. Например, это один из возможных сценариев:

  • Зритель $$$1$$$ — самозванец;
  • Зритель $$$2$$$ — член экипажа;
  • Зритель $$$3$$$ — член экипажа;
  • Зритель $$$4$$$ — самозванец.

Во втором наборе входных данных есть $$$5$$$ зрителей и $$$2$$$ утверждения. Утверждения следующие:

  • Утверждение $$$1$$$: Среди зрителей $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ и $$$5$$$ есть хотя бы один самозванец;
  • Утверждение $$$2$$$: Среди зрителей $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$ и $$$5$$$ нет самозванцев.

Мы можем видеть, что возможно, что утверждение $$$1$$$ истинно, и возможно, что утверждение $$$2$$$ истинно. Однако невозможно, чтобы оба утверждения $$$1$$$ и $$$2$$$ были истинны.