You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

一条街道上有 $n$ 个路灯排成一排，编号 $1, 2, \ldots, n$ 。小 Z 喝醉了，初始在时刻 $0$ 时站在 $1$ 号路灯旁。

小 Z 从某个时间 $t_0$ ($t_0 \geq 0$) 开始游走。在时间 $t_0$ 之后，小 Z 每隔一个单位时间就会移动到相邻的路灯旁。如果小 Z 在时间 $t$ 在 $i$ 号路灯旁，则他在时间 $t + 1$ 必然移动到 $i - 1$ 号路灯或 $i + 1$ 号路灯旁。特殊的，小 Z 不会移动到街道边界之外，即他始终只停留在路灯 $1$ 和 $n$ 之间（包含边界）。例如，小 Z 在时间 $t_0 + 1$ 必然在 $2$ 号路灯旁。

你得知了一些路人提供的信息，每条信息都可以用整数 $p_i$ 和 $q_i$ 表示，代表在 $q_i$ 时刻某位路人看到到小 Z 在路灯 $p_i$ 旁边。你想找到小 Z 开始到处走动的时间 $t_0$ 。在收到信息的同时，你还想根据当前收到的信息推断 $t_0$ 可能的最大值和最小值。

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

输入格式

从 drunkard.in 文件读入数据。

第一行包含两个整数 $n$ 和 $m$，代表路灯的数量和操作次数。

接下来 $m$ 行分别包含一个操作 $op_i$，格式为以下其一：

• clue $p_i$ $q_i$：行人在时间 $q_i$ 看到小 Z 在灯柱 $p_i$ 旁边。
• min：你想根据当前收到的信息推断 $t_0$ 的最小可能值。
• max：你想根据当前收到的信息推断 $t_0$ 的最大可能值。

输出格式

输出到 drunkard.out 文件。

对于每个 min 或 max 操作，输出问题的答案。

对于 max 操作，如果 $t_0$ 可以为任意大的数（即不存在一个有限的最大值），那么答案为字符串 inf。

如果当前收到的信息不一致，那么答案为字符串 bad。

样例

10 7
clue 1 3
min
clue 3 5
max
clue 10 6
max
min

1
3
bad
bad

• 在第 1 条线索后，小 Z 可能在时间 1 开始向灯柱 2 走动，在时间 2 向灯柱 1 走动，但是不可能是由时间 0 便开始走动的。
• 在第 2 条线索后，小 Z 必须在时间 3 开始由灯柱 1 (从第 1 条线索得知) 向灯柱 3 走动，才能在时间 5 抵达灯柱 3。
• 在第 3 条线索后，即使小 Z 在时间 5 开始由灯柱 3 (从第 2 条线索得知) 向灯柱 10 走动，仍然不可能在时间 6 抵达灯柱 10。

样例 2

点击链接 ex_drunkard2.in 和 ex_drunkard2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于所有数据，

$10 \leq n \leq 10^9$，

$1 \leq m \leq 2 \times 10^5$，

$1 \leq p_i \leq n$，

$0 \leq q_i \leq 10^9$，

存在至少一个 min 或 max 操作，

$op_i$ 为 clue、min 或 max之一。