F. Wonderful Impostors
data structures; implementation; two pointers
You are a proud live streamer known as Gigi Murin. Today, you will play a game with \(n\) viewers numbered \(1\) to \(n\).In the game, each player is either a crewmate or an impostor. You don't know the role of each viewer.There are \(m\) statements numbered \(1\) to \(m\), which are either true or false. For each \(i\) from \(1\) to \(m\), statement \(i\) is one of two types: \(0\:a_i\:b_i\) (\(1 \leq a_i \leq b_i \leq n\)) — there are no impostors among viewers \(a_i, a_i + 1, \ldots, b_i\); \(1\:a_i\:b_i\) (\(1 \leq a_i \leq b_i \leq n\)) — there is at least one impostor among viewers \(a_i, a_i + 1, \ldots, b_i\).Answer \(q\) questions of the following form: \(l\:r\) (\(1 \leq l \leq r \leq m\)) — is it possible that statements \(l, l + 1, \ldots, r\) are all true?Note that it is not guaranteed that there is at least one impostor among all viewers, and it is not guaranteed that there is at least one crewmate among all viewers.
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 contains two integers \(n\), \(m\) (\(1 \leq n, m \leq 2 \cdot 10^5\)) — the number of viewers, and the number of statements.The \(i\)-th of the next \(m\) lines contains three integers \(x_i\), \(a_i\), \(b_i\) (\(x_i \in \{0, 1\}\), \(1 \leq a_i \leq b_i \leq n\)) — describing statement \(i\).The next line contains a single integer \(q\) (\(1 \le q \le 2 \cdot 10^5\)) — the number of questions.Each of the next \(q\) lines contains two integers \(l\) and \(r\) (\(1 \leq l \leq r \leq m\)) — describing a question.It is guaranteed that the sum of \(n\) over all test cases does not exceed \(2 \cdot 10^5\), the sum of \(m\) over all test cases does not exceed \(2 \cdot 10^5\), and the sum of \(q\) over all test cases does not exceed \(2 \cdot 10^5\).
For each question, output ""YES"" if it is possible that the requested statements are all true. Otherwise, output ""NO"".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.
In the first test case, there are \(4\) viewers and \(3\) statements. The statements are as follows: Statement \(1\): There is at least one impostor among viewers \(1\), \(2\), and \(3\); Statement \(2\): There is at least one impostor among viewers \(2\), \(3\), and \(4\); Statement \(3\): There are no impostors among viewers \(2\) and \(3\). We can see that it is possible that statements \(1\), \(2\), and \(3\) are all true. For example, this is one possible scenario: Viewer \(1\) is an impostor; Viewer \(2\) is a crewmate; Viewer \(3\) is a crewmate; Viewer \(4\) is an impostor. In the second test case, there are \(5\) viewers and \(2\) statements. The statements are as follows: Statement \(1\): There is at least one impostor among viewers \(1\), \(2\), \(3\), \(4\), and \(5\); Statement \(2\): There are no impostors among viewers \(1\), \(2\), \(3\), \(4\), and \(5\). We can see that it is possible that statement \(1\) is true, and it is possible that statement \(2\) is true. However, it is not possible that both statements \(1\) and \(2\) are true.