Game

Koishi is playing a game with Satori.

There is an array of length $10^{18}$. In the game, Koishi and Satori take turns operating on this array, and Koishi goes first. When it comes to a player's turn, if there is only one element left in the array, she loses the game immediately. Otherwise, she needs to delete either the leftmost number or the rightmost number of the remaining array.

It is too boring for Koishi, so she comes up with the following rules.

There are $n$ sub-segments of this array that are special. Specifically, the $i$-th sub-segment is described by three integers $(l_i,r_i,z_i)$, which means that when it comes to a player's turn, if the remaining array is the sub-segment $[l_i,r_i]$, she will win immediately if $z_i=1$ or lose immediately if $z_i=0$. Moreover, if there is a special sub-segment $(x,x,1)$, then the player will immediately win when the remaining array is $[x,x]$ (In default case, when there is only one number, the player will lose).

There will be $q$ games, At the beginning of the $i$-th game, Utuoho will give two players the sub-segment $[a_i,b_i]$ and take away all other parts of the array. That means Koishi and Satori only play on subsegment $[a_i,b_i]$. All the $q$ games are independent.

Two players always use the optimal strategy. Please tell them who will win in each game.

The first line contains an integer $T(1 \leq T \leq 2 \times 10^3)$ - the number of test cases. Then $T$ test cases follow.

The first line of each test case contains two integers $n, q(1 \leq n, q \leq 10^5)$ - the number of sub-segments and the number of games.

Then $n$ lines follow, each line contains $3$ integers $l_i, r_i, z_i(1\leq l_i\leq r_i\leq 10^9,0 \leq z_i \leq 1)$, satisfing that for any $i\neq j$, $(l_i,r_i)\neq (l_j,r_j)$ holds.

Then $q$ lines follow, each line contains $2$ integers $a_i, b_i(1\leq a_i\leq b_i\leq 10^9)$ - the initial sub-segment of the $i$-th game.

It is guaranteed that $\sum (n+q)\leq 9 \times 10^5$.

For each test case, output one line with $q$ integers $v_i(0 \leq v_i \leq 1)$ without spaces, that $v_i = 0$ if Koishi will lose in the $i$-th game and $v_i = 1$ if she will win in the $i$-th game.

1
5 10
1 2 0
3 3 1
3 4 1
2 4 1
1 3 0
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

0010111101

2021“MINIEYE杯”中国大学生算法设计超级联赛（6）