Andrew and William are playing a game involving an array of integers. At the beginning of the game, Andrew is shown an array of ~N~ distinct positive integers: ~a_1, a_2, \dots, a_N~. However, William does not get to see the array.

Instead, Andrew makes ~M~ statements about the array. Each statement is in the form of three integers L R X, which means the minimum value among the elements from index ~L~ to ~R~ (inclusive) is ~X~.

However, Andrew is not always honest, and some of his statements may contradict previous ones. William wants to determine whether all of Andrew's statements can be true at the same time — i.e., whether they are mutually consistent.

Your task is to help William by analyzing the ~M~ statements and identifying the first one (by input order) that contradicts any earlier ones. If all statements are consistent, print 0.

Input Specification

The first line includes two integers, ~N~ and ~M~ (~N \le 10^6~, ~M \le 3\times 10^4~), the size of the array and the number of statements Andrew made.

Each of the following ~M~ lines contains three integers, ~L~ ~R~ ~X~, representing one of Andrew's statement that the minimal value among ~a_L~ to ~a_R~ is ~X~ (~1 \le L \le R \le N~, ~1 \le X \le 10^9~)

Output Specification

Print ~0~ if Andrew's statements are all consistent. Otherwise, print the index from ~1~ to ~M~ of the earliest statement which is inconsistent with statements before it.

Constraints

Subtask	Points	Additional constraints
~1~	~20~	~N \le 100~, ~M \le 20~.
~2~	~40~	~M \le 1\,000~.
~3~	~40~	No additional constraints

Sample Input 1

18 4
2 10 6
5 18 6
3 11 9
11 15 12

Sample Output 1

3

Sample Input 2

5 3
2 4 3
1 4 1
4 4 5

Sample Output 2

0