时间限制：1秒　　内存限制：256M

---

【题目描述】

　　有长度为 \(n\) 的整数序列：\(a[1]..a[n]\)，每个元素的都在 \(1..10^9\) 之间，但并不知道每个元素具体的值。

　　现在给出关于这个序列的 \(m\) 条些信息，每条信息格式为：\(x\ y\ v（x≤y）\)，表示序列第 \(x\) 个元素到第 \(y\)个元素之间最大元素的值为 \(v\)，即 \(v= max\{\ a[i]\ |\ x≤i≤y\ \}\)。不保证这些信息都正确。

　　\(m\) 条信息逐条给出，请你编程判断一下，给出信息是否有矛盾之处，若有请输出最早出现与之前信息有矛盾的那条?

【输入格式】

　　第一行：两个用空格隔开的整数 \(n\) 和 \(m\)。
　　第 \(2\) 到 \(m+1\) 行：每行为三个用空格隔开的整数：\(a\ b\ v\)，描述了一条信息。

【输出格式】

　　若所有信息都没有矛盾，则输出 0 ，否则输 \(1..m\)之间的一个整数，表示最出现矛盾的信息的编号。

【输入输出样例】

　Input

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

　Output

3

【数据限制】

　　\(100\%\) 的数据满足：\(1 ≤ n ≤ 1000000\)，\(1≤m≤100000\)。

【来源】

　　Mr.he