题目描述

$Bob$ 在玩一个开关灯的游戏，最开始有 $n$ 盏熄灭的灯，每盏灯都有一个独立开关，按一次开关，灯的状态会反转，即原来是灭，按了开关后亮，原来是亮，按了开关后灭。

将亮灭交替出现的连续一段定义为“最美交替段”，例如如果用 1 表示亮，0 表示灭，$5$ 盏灯的状态为 10100 ，其中 1,0,10,01,010,1010 都是“最美交替段”，其中最长的长度是 $4$ 。

$Bob$ 要进行 $q$ 次操作，给次操作给定三个整数 $x$ $l$ $r$ , 表示现在将 $x$ 位置的灯状态反转，然后你需要回答区间 $[l,r]$ 内最长“最美交替段”长度。

输入格式

第一行，两个整数 $n$ 和 $q$

接下来 $q$ 行，每行 $3$ 个整数 $x$ $l$ $r$

输出格式

$q$ 行，每行一个整数，表示区间 $[l,r]$ 内最长“最美交替段”长度。

6 2
2 1 6
4 1 6

3
5

10 10
5 1 7
2 2 6
4 4 4
9 5 9
6 3 7
4 4 8
8 8 10
7 2 10
6 2 8
5 2 7

3
3
1
2
2
2
2
2
4
2

下发数据：down.zip

数据规模与约定

所有数据满足： $1\le n,q \le 2 \times 10^5, 1 \le l \le r \le n$ 。

$Subtask1$: $1 \le n,q \le 10^3$ , $20$ 分

$Subtask2$: $1\le n,q \le 2 \times 10^5$ , $l=1,r=n$ , $40$ 分

$Subtask3$: 无其他限制, $40$ 分