题目描述

一条街道上有 $n$ 个路灯排成一排，编号 $1,2,…,n$ 。一个酒鬼初始在时刻 $0$ 时站在 $1$ 号路灯旁。

酒鬼从某个时间 $t_0$ ($t_0≥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$ 可能的最大值和最小值。

路人提供的信息也有可能不一致。一旦你发现提供的信息有矛盾，只需停止计算并报告信息不一致。

输入格式

第一行一个整数 $T$ ($1≤T≤100$)， 代表数据组数。

对于每组数据：

第一行包含两个整数 $n, m$ ($2≤n≤10^9,1≤m≤2×10^5$)，代表街道上路灯的数量和操作次数。

接下来 $m$ 行，每行描述一个操作，为以下三种类型之一：

• $0$ $p_i$ $q_i$：路人在时间 $q_i$ 看到酒鬼在路灯 $p_i$ 旁边 ($1≤p_i≤n,0≤q_i≤10^9$)。
• $1$：根据当前收到的信息推断， $t_0$ 可能的最小值。
• $2$：根据当前收到的信息推断， $t_0$ 可能的最大值。

保证所有数据的 $m$ 之和不会超过 $5×10^6$。

输出格式

对于每个询问，输出一行代表询问的答案。

对于 $2$ 询问（即询问 $t_0$ 可能的最大值），如果 $t_0$ 可以为任意大，输出 $\text{inf}$。

如果当前收到的信息已经不一致， 对于后续的所有询问均输出 $\text{bad}$。

输入样例

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

输出样例

0
inf
3
1
bad
bad