Koishi 正在和 Satori 玩一个游戏。

有一个长度为 $10^{18}$ 的数组。在这个游戏中，Koishi 和 Satori 轮流对这个数组进行操作，Koishi 先手。在一名玩家的回合开始时，如果数组中只剩下一个元素，则该玩家立即输掉游戏。否则，她需要删除当前剩余数组的最左侧数字或最右侧数字。

这个游戏对 Koishi 来说太无聊了，所以她提出了以下修改后的规则。

数组中有 $n$ 个特殊的子段。具体来说，第 $i$ 个子段由三个整数 $(l_i, r_i, z_i)$ 描述。这意味着，在一名玩家的回合开始时，如果剩余的数组是子段 $[l_i, r_i]$，那么如果 $z_i = 1$，她将立即获胜；如果 $z_i = 0$，她将立即输掉游戏。

如果给定了某个 $x$ 的特殊子段 $(x, x, 1)$，则当一名玩家的回合开始时，如果剩余数组为 $[x, x]$，该玩家将立即获胜。重要的是，如果没有给定某个 $x$ 的特殊子段 $(x, x, 1)$，则按照原始规则，$[x, x]$ 被视为立即输掉游戏。

游戏共有 $q$ 局。在第 $i$ 局游戏开始时，Utuoho 会给两位玩家一个子段 $[a_i, b_i]$，并移走数组的其他所有部分。这意味着 Koishi 和 Satori 只在子段 $[a_i, b_i]$ 上进行游戏，而不是在整个数组上。所有 $q$ 局游戏都是独立的。

两位玩家总是采取最优策略。请告诉我们每一局游戏谁会获胜。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 2000$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)，分别表示特殊子段的数量和游戏的数量。

接下来 $n$ 行，每行包含三个整数：$l_i, r_i, z_i$ ($1 \le l_i \le r_i \le 10^9, 0 \le z_i \le 1$)。你可以假设对于任意 $i \neq j$，$(l_i, r_i) \neq (l_j, r_j)$ 成立。

之后是 $q$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i \le b_i \le 10^9$)，描述第 $i$ 局游戏的初始子段。

保证 $\sum (n + q) \le 9 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行包含 $q$ 个整数 $v_i$ ($0 \le v_i \le 1$)，中间不加空格：如果 Koishi 在第 $i$ 局游戏中输掉，则 $v_i = 0$；如果她获胜，则 $v_i = 1$。

样例

样例输入 1

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

样例输出 1

0010111101