Description

给一个长度为 $n$ 的数组 $q$ 个条件，数组中的数字互不相同，每个条件格式形如 $l_i,r_i,x_i$ 表示这个数组的区间 $[l_i,r_i]$ 内的最小值为 $x_i$，输出最早与前面的条件有矛盾的条件的编号，如果所有条件都不发生矛盾，输出 $0$。

Input Format

第一行两个整数，分别是 $n$ 和 $q$。

第二行至第 $q+1$ 行，每行三个整 $l_i,r_i,x_i$ 描述一个条件。

Output Format

仅一个整数，表示最早发生矛盾的条件的编号。如果所有条件都没有发生矛盾，输出 $0$。

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

3

Hint

对于 $100\%$ 的数据，保证：

• $1 \le q \le 25000$
• $1 \le n \le 10^6$
• $1 \le l_i \le r_i \le n$
• $1 \le x_i \le 10^9$