Haybale Guessing#10155
The cows, who always have an inferiority complex about their intelligence, have invented a new guessing game to sharpen their brains.
A designated "Hay Cow" hides behind the barn and creates uniquely sized stacks of hay bales, conveniently numbered 1, \ldots, n). Each stack contains between and 10^9 bales of hay.
The other cows then ask the Hay Cow a series of questions about the stacks. All questions have the following form:
What is the smallest number of bales in any stack whose number is in the range (q_l,\ldots,q_h), where 1 \le q_l \le n and q_l \le q_h \le n?
The Hay Cow answers each query with a single integer , but the answers may not always be truthful.
Help the other cows determine whether the answers given by the Hay Cow are mutually consistent, or whether some answer contradicts the answers to previous queries.
The first line contains two integers: n~(1 \le n \le 10^6) and q~(1 \le q \le 25000). Each of the next line contains three integers representing a query and its answer: q_l, q_h, and .
Print one integer if all answers are consistent (i.e., if there exists a valid assignment of sizes to the hay stacks that agrees with all queries).
Otherwise, print the index of the earliest query, from to , whose answer is inconsistent with the answers to the preceding queries.
Example 1