Physical Education Lessons

올해 Alex는 학교를 졸업했고, 이제 Berland State University의 신입생이다. 프로그래밍을 공부하는데도 체육 수업에 출석해야 한다는 사실은 그에게 정말 뜻밖이었다. 학기가 곧 끝나지만, 안타깝게도 Alex는 아직 단 한 번의 수업에도 출석하지 않았다!

Since Alex는 퇴학당하고 싶지 않으므로, 이 날들에 체육 수업에 출석할 수 있도록 학기가 끝날 때까지 남은 근무일의 수를 알고 싶어 한다. 하지만 BSU에서는 근무일의 수를 계산하는 일이 복잡하다.

학기가 끝나기 전까지 n일이 남아 있으며(1부터 n까지 번호가 매겨진다), 처음에는 모든 날이 근무일이다. 그 후 대학 직원들은 q개의 명령을 하나씩 차례로 공표한다. 각 명령은 세 수 l, r, k로 나타낸다.

• k = 1이면 l부터 r까지의 모든 날(양 끝 포함)이 휴무일이 된다. 이 날들 중 일부가 이전의 어떤 명령에 의해 근무일이 되었더라도, 해당 날들은 다시 휴무일이 된다.
• k = 2이면 l부터 r까지의 모든 날(양 끝 포함)이 근무일이 된다. 이 날들 중 일부가 이전의 어떤 명령에 의해 휴무일이 되었더라도, 해당 날들은 다시 근무일이 된다.

각 명령 후에 남은 근무일의 수를 구하는 Help Alex!

첫 번째 줄에는 정수 n 하나가, 두 번째 줄에는 정수 q (1 ≤ n ≤ 109, 1 ≤ q ≤ 3·105) 하나가 주어진다. 이들은 각각 학기가 끝나기 전까지 남은 날의 수와 명령의 수이다.

이어서 q개의 줄이 주어지며, i-th 줄에는 i-th 명령 (1 ≤ li ≤ ri ≤ n, 1 ≤ ki ≤ 2)을 나타내는 세 정수 li, ri, ki이 주어진다.

q개의 정수를 출력한다. 그중 i-th 정수는 처음 i개의 명령이 공표된 후 학기가 끝날 때까지 남은 근무일의 수와 같아야 한다.