阿普尔曼有一张很大的纸。该片材呈矩形,尺寸为 1 × n。你的任务是帮助阿普尔曼折叠这样一张纸。实际上,您需要执行 q 查询。每个查询将具有以下类型之一:
1. 在位置 pi 处折叠纸张。执行此查询后,尺寸为 1 × pi 的纸张最左侧部分必须位于尺寸为 1 × ([纸张的当前宽度] - pi)的纸张最右侧部分之上。
2. 如果我们进行后面描述的两次切割并仅考虑切割之间的碎片,请计算纸片的总宽度是多少。我们将在距当前纸张左边框距离 li 处进行一次切割,并在距当前纸张左边框距离 ri 处进行另一次切割。
请查看第一个测试示例的解释,以便更好地理解问题。
输入
第一行包含两个整数:n 和 q (1 ≤ n ≤ 105; 1 ≤ q ≤ 105) — 纸张的宽度和查询数。
以下 q 行中的每一行都包含采用以下格式的所描述的查询之一:
- "1 pi" (1 ≤ pi < [当前工作表宽度]) — 第一种类型查询。
- "2 li ri" (0 ≤ li < ri ≤ [当前工作表宽度]) — 第二种类型查询。
输出
对于第二类型的每个查询,输出答案。
示例
输入 #1
7 4 1 3 1 2 2 0 1 2 1 2
输出 #1
4 3
输入 #2
10 9 2 2 9 1 1 2 0 1 1 8 2 0 8 1 2 2 1 3 1 4 2 2 4
输出 #2
7 2 10 4 5
注意
下图显示了第一个示例查询时纸张的形状:
第一次折叠操作后,纸张的宽度等于 4,第二次折叠操作后,纸张的宽度等于 2。