[Usaco2008 Jan]猜数游戏

为了提高逻辑推理能力，奶牛们设计了一个新的猜数游戏。

游戏开始前，一头奶牛会在牛棚后摆放 $N$ 堆干草。所有草堆排成一条直线，从左到右依次编号为 $1$ 到 $N$。每堆干草的捆数均为正整数，且任意两堆干草的捆数都不相同。

游戏开始后，另一头奶牛会提出 $Q$ 个问题。每个问题给出三个整数 $Q_l$、$Q_h$ 和 $A$，表示编号在 $Q_l$ 到 $Q_h$ 之间的草堆中，捆数最少的一堆有 $A$ 捆干草。

然而，这些回答不一定正确。请判断是否存在一种满足上述要求的干草摆放方案，使给出的回答全部成立。如果不能，请找出最早出现矛盾的回答。

输入格式

第一行包含两个以空格分隔的整数 $N$ 和 $Q$，分别表示草堆数量和问题数量。

接下来 $Q$ 行，每行包含三个以空格分隔的整数 $Q_l$、$Q_h$ 和 $A$，表示编号在 $Q_l$ 到 $Q_h$ 之间的草堆中，最少的干草捆数为 $A$。

输出格式

如果存在一种干草摆放方案，使所有回答均成立，输出 $0$。

否则，输出一个整数 $m$，表示前 $m-1$ 个回答可以同时成立，但加入第 $m$ 个回答后产生矛盾。

样例输入

20 4
1 10 7
5 19 7
3 12 8
11 15 12

样例输出

3

样例解释

前两个回答都表示对应区间的最小值为 $7$。由于任意两堆干草的捆数不同，这两个区间中的最小值 $7$ 必须来自同一堆干草，因此该草堆必定位于两个区间的交集，即编号为 $5$ 到 $10$ 的范围内。

这个范围包含在第 $3$ 个问题所询问的区间 $[3,12]$ 中，因此该区间的最小值不可能是 $8$。故第 $3$ 个回答与之前的回答产生矛盾。

数据范围

• $1\le N\le 10^6$；
• $1\le Q\le 2.5\times 10^4$；
• $1\le Q_l\le Q_h\le N$；
• $1\le A\le 10^9$。

来源与许可

本题为 USACO 2008 January 试题「猜数游戏」，题面与测试数据整理自 BZOJ。

样例 1

输入

20 4
1 10 7
5 19 7
3 12 8
11 15 12

输出

3