小红的01串（六）
题号：NC285892
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红定义一个字符串是好串，当且仅当该字符串任意一对相邻字符都不同。

现在小红拿到了一个字符串，初始所有字符都是'0'，她希望你能维持以下操作：
· 输入1 \ l \ r，将第l个字符到第r个字符修改为'1'。
· 输入2\ l\ r ，将第l个字符到第r个字符取反（即'1'变'0'，'0'变'1'）。
· 输入3 \ l \ r ，查询将第l个字符到第r个字符对应子串修改为好串的最小修改次数（每次可以修改一个字符）。

输入描述:

第一行输入两个正整数n,q，代表字符串长度、操作次数。
接下来的q行，每行输入三个正整数op,l,r，分别代表操作类型和操作的区间。
1\leq n \leq 10^9
1\leq q \leq 10^5
1\leq l \leq r \leq n
保证至少有一次操作3。

输出描述:

对于每次操作3输出一行，代表该次询问的答案。
示例1

输入

复制 
1000000000 2
1 2 999999999
3 1 10

输出

复制 
4

说明

查询的子串为"0111111111"，最少需要修改4次才能变成好串。