P2898 [USACO08JAN] Haybale Guessing G

题目描述

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

3