题目描述

有 $N$ 个位置，每个位置上的整数互不相同。共有 $Q$ 个回答，第 $i$ 个回答声称：区间 $[L_i,R_i]$ 中的最小值为 $V_i$。

请按照回答的先后顺序判断，最早从第几个回答开始，已有的所有回答不可能同时成立。

如果全部回答都可以同时成立，输出 $0$。

输入格式

第一行包含两个整数 $N,Q$。

接下来 $Q$ 行，每行包含三个整数 $L_i,R_i,V_i$，表示第 $i$ 个回答。

输出格式

输出一个整数，表示最早产生矛盾的回答编号；如果全部回答都没有矛盾，输出 $0$。

20 3
1 4 2
5 6 3
7 12 2

3

样例解释

第 $1$ 个和第 $3$ 个回答都声称区间最小值为 $2$，但两个区间没有公共位置。由于所有位置上的整数互不相同，这两个回答不可能同时成立。

数据范围与提示

• 对于 $50\%$ 的数据，$1 \le N \le 10000$，$1 \le Q \le 500$
• 对于全部数据，$1 \le N \le 10^6$，$1 \le Q \le 25000$
• $1 \le L_i \le R_i \le N$
• $1 \le V_i \le 10^8$