Lie

Two people are playing a game as a questioner and an answerer. The answerer is given a binary sequence of length N, where 1 ≤ N ≤ 1,000,000,000.

The questioner asks M questions, where 1 ≤ M ≤ 5,000. Each question asks whether the number of ones in the inclusive interval from position i to position j is even or odd. The answerer replies 0 if the count is even and 1 if the count is odd.

Given the questions and answers in order, find the first question at which the answers can no longer all be true at the same time.

Saying that the answerer lied on a question means that no binary sequence exists that satisfies every previous answer together with that answer.

The first line contains two integers N and M. Each of the next M lines contains three integers i, j, and a describing one question. The value a is the answer: 0 means the number of ones in the interval is even, and 1 means it is odd.

Print the number of the first question on which the answerer lied. If none of the answers contradict the earlier answers, print M+1.