老师要求全班 N 位同学排成一排，并从左到右报数 1∼N，每位同学要记住自己报数的数字和别人报数的数字之后，老师将同学们随机打乱，重新排成一排。

接下来，老师提出了 Q 个问题，每个问题要求从第 L i ​ 个人开始，到第 R i ​ 个人结束，这个区间 [L i ​ ,R i ​ ] 范围内的最小报数值是多少。

请输出最早发生矛盾的提问编号。

输入 第一行包含两个整数 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

样例2

输入

30 5

1 6 10

15 20 20

4 10 10

5 8 5

12 13 11

输出

4