Inspector Byteasar's Investigation

Inspector Byteasar is investigating a crime at a software development company. He has collected m records from n employees. Each employee works during a single contiguous period of the day. Every record is written by an employee at a specific time t and states that, besides himself, there were x other employees online (so the total online count is x+1 at that moment).

A set of records (taken in their input order) is considered consistent if it is possible to assign each employee an interval [s,e] (with s and e real numbers, and s ≤ e) during which that employee is present in the office, such that for every record with time t and claimed total online count (x+1) the following holds. Define, for the prefix of records under consideration, that for each employee who appears at least once the forced (or mandatory) interval is [L, R] where L is the minimum time at which the employee has recorded and R is the maximum time. Then at any record time t, if F(t) denotes the number of employees whose forced interval covers t and U = n - (number of employees who have appeared in any record in the prefix), the record’s claim is possible only if

( F(t) \leq x+1 \leq F(t)+U )

Additionally, if two or more records share the same time t, they must all report the same total count (i.e. the same value of x+1).

Your task is to determine the maximum integer k (0 (\leq k \leq m)) such that the first k records are mutually consistent.

inputFormat

The first line contains two integers n and m (1 (\leq n, m \leq 10^5)). Each of the following m lines contains three integers: p, t, and x (1 (\leq p \leq n), 0 (\leq t \leq 10^9), 0 (\leq x \leq n-1)), where employee p wrote a record at time t stating that there were x other employees online.

outputFormat

Output the maximum integer k (0 (\leq k \leq m)) such that the first k records are mutually consistent.

sample

3 4
1 10 0
2 20 0
3 15 1
2 30 0

2