题目描述

体育课上，老师要求全班 $N$ 位同学排成一排，并从左到右给了每位同学一个 互不相同 的数字，每位同学要记住自己拿到的数字和别人拿到的数字之后，老师将同学们随机打乱，重新排成一排。

接下来，老师提出了 $Q$ 个问题，每个问题要求某位同学根据自己的记忆回答，从第 $L_i$ 个人开始，到第 $R_i$ 个人结束，这个区间 $[L_i, R_i]$ 范围内的同学拿到的最小数字是多少。

同学们很努力回忆之前的拿到的数字，但人的记忆力是有限的，很多同学都无法准确的记住每位同学一开始拿到的数值，因此回答和实际值相比较可能会出现偏差。

老师要求同学们观察，第几个提问，同学回答的数字，和前面已经回答过的同学回答的数字是矛盾的？

如果有多个问题，同学回答的数字，和前面已经回答过的同学回答的数字是矛盾的，请输出最早发生矛盾的提问编号。

如果所有提问同学们的答案都没有矛盾，输出 0。

输入格式

第一行包含两个整数 $N$ 和 $Q$，分别表示同学的数量和提问的数量。

接下来 $Q$ 行，每行包含三个整数 $L_i, R_i, V_i$，表示在第 $i$ 个问题中，同学回答在 $[L_i, R_i]$ 区间中，拿到最小的数值为 $V_i$。

输出格式

输出一个整数，表示最早同学的回答，和之前已经的回答，发生矛盾的提问编号。如果所有提问的回答都没有矛盾，输出 0。

样例

输入

20 3
1 4 2
5 6 3
7 12 2

输出

3

数据范围

对于 $50\%$，$1 \le N \le 10000$，$1 \le Q \le 500$。

对于 $100\%$，$1 \le N \le 1,000,000$，$1 \le Q \le 25,000$，$1 \le L_i \le R_i \le N$，$1 \le V_i \le 10^8$。