一行中有 $$$n$$$ 个城市,编号从 $$$1$$$ 到 $$$n$$$。
城市将建设广播电台。第 $$$i$$$ 个城市的车站高度为 $$$h_i$$$,范围为 $$$w_i$$$。如果满足以下约束,它可以向城市 $$$j$$$ 广播信息:
- $$$i \le j \le w_i$$$,以及
- 对于每个$$$k$$$,使得$$$i < k \le j$$$,以下条件成立:$$$h_k < h_i$$$。
一开始,对于每个城市 $$$i$$$,$$$h_i = 0$$$ 和 $$$w_i = i$$$。
然后 $$$q$$$ 事件将会发生。在第 $$$i$$$ 事件期间,将发生以下其中一项:
- 城市 $$$c_i$$$ 将重建其车站,使其高度严格成为所有车站中最高的,并且 $$$w_{c_i}$$$ 将设置为 $$$g_i$$$。
- 让 $$$b_j$$$ 为可以向城市 $$$j$$$ 广播信息的电台数量。打印满足 $$$l_i \le j \le r_i$$$ 的所有 $$$j$$$ 的 $$$b_j$$$ 之和。
您的任务是对所有事件做出反应并打印所有查询的答案。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2\cdot10^5$$$) — 城市数量和事件数量。
然后是 $$$q$$$ 行。第 $$$i$$$ 行以整数 $$$p_i$$$ 开头($$$p_i = 1$$$ 或 $$$p_i = 2$$$)。
如果$$$p_i = 1$$$ 将会重建一个站。然后是两个整数 $$$c_i$$$ 和 $$$g_i$$$ ($$$1 \le c_i \le g_i \le n$$$) — 重建电台的城市及其新的广播范围。
如果 $$$p_i = 2$$$ 您将收到一个查询。然后是两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — 查询中的城市范围。
输出
对于每个查询,在单行中打印给定时间间隔内 $$$b_j$$$ 的总和。
示例
输入 #1
1 3 2 1 1 1 1 1 2 1 1
输出 #1
1 1
输入 #2
5 10 1 3 4 2 3 5 1 1 5 2 1 5 1 4 5 2 2 4 1 2 3 2 1 3 1 5 5 2 2 5
输出 #2
4 10 5 4 5
注意
在第一个测试用例中,只有$$$1$$$车站在重建之前和之后到达城市$$$1$$$。
在第二个测试用例中,每次重建后,数组 $$$b$$$ 如下所示:
1. $$$[1, 1, 1, 2, 1]$$$;
2. $$$[1, 2, 2, 3, 2]$$$;
3. $$$[1, 2, 2, 1, 2]$$$;
4. $$$[1, 1, 2, 1, 2]$$$;
5. $$$[1, 1, 2, 1, 1]$$$.