游走

Problem Description

一条街道上有 $n$ 个路灯排成一排，编号 $1, 2, \ldots, n$ 。一个酒鬼初始在时刻 $0$ 时站在 $1$ 号路灯旁。 酒鬼从某个时间 $t_0$ ($t_0 \geq 0$) 开始游走。在时间 $t_0$ 之后，酒鬼每隔一个单位时间就会移动到相邻的路灯旁。如果酒鬼在时间 $t$ 在 $i$ 号路灯旁，则他在时间 $t + 1$ 必然移动到 $i - 1$ 号路灯或 $i + 1$ 号路灯旁。特殊的，酒鬼不会移动到街道边界之外，即他始终只停留在路灯 $1$ 和 $n$ 之间（包含边界）。例如，酒鬼在时间 $t_0 + 1$ 必然在 $2$ 号路灯旁。 你得知了一些路人提供的信息，每条信息都可以用整数 $p_i$ 和 $q_i$ 表示，代表在 $q_i$ 时刻某位路人看到酒鬼在路灯 $p_i$ 旁边。你想找到酒鬼开始到处走动的时间 $t_0$ 。在收到信息的同时，你还想根据当前收到的信息推断 $t_0$ 可能的最大值和最小值。 路人提供的信息也有可能不一致。一旦你发现提供的信息有矛盾，只需停止计算并报告信息不一致。

Input

第一行一个整数 $t\ (1\le t\le 100)$， 代表数据组数。 对于每组数据： 第一行包含两个整数 $n,\ m\ (2 \leq n \leq 10^9, 1 \leq m \leq 2 \times 10^5)$，代表街道上路灯的数量和操作次数。 接下来 $m$ 行，每行描述一个操作，为以下三种类型之一：

• $0\ p_i\ q_i$：路人在时间 $q_i$ 看到酒鬼在路灯 $p_i$ 旁边 $(1 \leq p_i \leq n, 0 \leq q_i \leq 10^9)$。
• $1$：根据当前收到的信息推断， $t_0$ 可能的最小值。
• $2$：根据当前收到的信息推断， $t_0$ 可能的最大值。 保证所有数据的 $m$ 之和不会超过 $5\times 10^6$。

Output

对于每个询问，输出一行代表询问的答案。 对于 $2$ 询问（即询问 $t_0$ 可能的最大值），如果 $t_0$ 可以为任意大，输出 $\textbf{inf}$。 如果当前收到的信息已经不一致， 对于后续的所有询问均输出 $\textbf{bad}$。

Sample Input

1
11 9
1
2
0 3 5
2
0 1 3
1
0 10 6
2
1

Sample Output

0
inf
3
1
bad
bad

Source

2024“钉耙编程”中国大学生算法设计超级联赛（3）