추측 게임

바이트맨과 비트맨이 다음 게임을 한다. 비트맨은 0과 1로만 이루어진 길이 $1{,}000{,}000{,}000$의 수열을 하나 몰래 적어 둔다. 바이트맨의 목표는 이 수열을 알아맞히는 것이다.

바이트맨은 비트맨에게 다음 형태의 질문을 반복해서 던진다.

당신의 수열에서 $b$번째 원소부터 $e$번째 원소까지로 이루어진 부분수열의 합은 짝수인가요, 홀수인가요?

한동안 게임을 진행하던 바이트맨은 비트맨이 정직하지 않게 답하고 있다고 의심하기 시작했다. 그는 맨 앞에서부터 몇 번째 질문까지의 답이 서로 모순 없이 성립할 수 있는지 알고 싶다.

첫 $m$개의 답과 완전히 일치하는 0과 1의 수열이 실제로 존재하도록 하는 가장 큰 $m$을 구하는 프로그램을 작성하라.

첫 번째 줄에 바이트맨이 던진 질문의 개수 $n$ ($0 \le n \le 100{,}000$)이 주어진다.

이어지는 $n$개의 줄에는 각 질문과 그에 대한 비트맨의 답이 세 정수 $b$, $e$, $s$ ($1 \le b \le e \le 1{,}000{,}000{,}000$, $s \in \{0, 1\}$)로 주어지며, 세 값은 공백 하나로 구분된다. $b$와 $e$는 질문에서 부분수열의 첫 원소와 마지막 원소의 위치이다. $s = 0$은 합이 짝수라는 답, $s = 1$은 합이 홀수라는 답을 뜻한다.

첫 $m$개의 답과 모순되지 않는 0과 1의 수열이 존재하는 가장 큰 정수 $m$을 한 줄에 출력한다.