거짓말

두 사람이 질문자와 답변자가 되어 게임을 한다. 답변자에게는 길이 N(1 ≤ N ≤ 1,000,000,000)인 이진 수열이 주어진다.

질문자는 M(1 ≤ M ≤ 5,000)개의 질문을 한다. 각 질문은 수열의 i번째 항부터 j번째 항까지, 양 끝을 포함한 구간에 1이 짝수 번 나타나는지 홀수 번 나타나는지를 묻는다. 답변자는 짝수이면 0, 홀수이면 1이라고 답한다.

질문과 답변이 순서대로 주어진다. 처음으로, 지금까지의 답변과 함께 동시에 만족하는 이진 수열이 더 이상 존재하지 않게 되는 질문 번호를 구하라.

어떤 질문에서 답변자가 거짓말을 했다는 것은, 그 질문 이전까지의 답변들과 그 질문의 답변을 모두 만족하는 이진 수열이 존재하지 않는다는 뜻이다.

첫째 줄에 정수 N과 M이 주어진다. 이어서 M개의 줄에 각 질문을 나타내는 정수 i, j, a가 주어진다. a는 답변자의 답으로, 해당 구간에 1이 짝수 번 있으면 0, 홀수 번 있으면 1이다.

답변자가 처음으로 거짓말을 한 질문의 번호를 출력한다. 모든 답변이 앞선 답변들과 모순되지 않으면 M+1을 출력한다.