1034  Haybale Guessing
Time Limit : 2 Second
Memory Limit : 128 MB
Submission: 13
Solved: 4
 Description
 The cows, who always have an inferiority complex about their intelligence, have a new guessing game to sharpen their brains.
A designated 'Hay Cow' hides behind the barn and creates N (1 <= N <= 1,000,000) uniquelysized stacks (conveniently numbered 1..N)of hay bales, each with 1..1,000,000,000 bales of hay.
The other cows then ask the Hay Cow a series of Q (1 <= Q <= 25,000)questions about the the stacks, all having the same form:
What is the smallest number of bales of any stack in the range of stack numbers Ql..Qh (1 <= Ql <= N; Ql <= Qh <= N)?
The Hay Cow answers each of these queries with a single integer A whose truthfulness is not guaranteed.
Help the other cows determine if the answers given by the Hay Cow are selfconsistent or if certain answers contradict others.
 Input
 * Line 1: Two spaceseparated integers: N and Q
* Lines 2..Q+1: Each line contains three spaceseparated integers that
represent a single query and its reply: Ql, Qh, and A
 Output
 * Line 1: Print the single integer 0 if there are no inconsistencies among the replies (i.e., if there exists a valid realization of the hay stacks that agrees with all Q queries). Otherwise,print the index from 1..Q of the earliest query whose answer is inconsistent with the answers to the queries before it.
 sample input

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

3
 hint
 source
 USACO JAN08