背景

弱弱的LXY总是做弱弱的题

题目描述

弱弱的LXY又在玩猜数字游戏。
总共有n个互不相同的正整数，LXY每次猜一段区间的最小值。形如[li,ri]这段区间的数字的最小值一定等于xi。
我们总能构造出一种方案使得LXY满意。直到…… LXY自己猜的就是矛盾的！
例如LXY猜[1,3]的最小值是2，[1,4]的最小值是3，这显然就是矛盾的。
你需要告诉LXY，它第几次猜数字开始就已经矛盾了。

输入

第一行两个数n和T，表示有n个数字，LXY猜了T次。
接下来T行，每行三个数分别表示li,ri和xi。

输出

输出一个数表示第几次开始出现矛盾，如果一直没出现矛盾输出T+1。

样例 1

输入样例1

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

输出样例1

3

限制

Time Limit:2000ms Memory Limit:128MB

数据范围

对于50%的数据n<=8，T<=10。
对于80%的数据n<=1000，T<=1000。
对于100%的数据1<=n,T<=1000000,1<=li<=ri<=n,1<=xi<=n（但并不保证一开始的所有数都是1~n的）。

p.s.

不知道哪里来的水题