体育课上，老师要求全班 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
30 5 1 6 10 15 20 20 4 10 10 5 8 5 12 13 11
4
50000 20 1940 7904 2755 926 2492 23962 2053 5465 21629 318 5089 4345 6610 9711 8047 7830 7877 13071 9757 9919 11725 14 745 25072 8040 8538 34629 912 5526 17773 5735 7605 3815 7035 7240 24392 9659 9703 20089 9950 9995 15660 5584 6517 10638 1222 1390 1467 8801 8842 25170 1900 2183 24449 3493 6758 8405 9081 9530 16319
16
共有 20 位同学，将同学们随机打乱后。
第 1 个问题问第 1 位到第 4 位这 4 位同学中 ，最小拿到的数值，回答为 2。
第 2 个问题问第 5 位到第 6 位这 2 位同学中 ，最小拿到的数值，回答为 3。
第 3 个问题问第 7 位到第 12 位这 6 位同学中 ，最小拿到的数值，回答为 2。
第 3 个问题的回答，显然和第 1 个问题的回答是矛盾的，因为如果 [1,4] 中最小拿到的数值为 2，就意味着在 [7,12] 范围内不能有人拿到出数字 2。
对于 50\%，1 \leq N \leq 10000，1 \le Q \le 500。
对于 100\%，1 \leq N \leq 1,000,000，1 \leq Q \leq 25,000，1 \leq L_i \leq R_i \leq N， 1 \leq V_i \leq 10^8。