Delete

题目描述

输入 \(n\) 个数，\(m\) 次操作，你要支持以下操作：

• 删除第 \(l\) 至 \(r\) 个数。注意已经删过的数不会再次删除。

• 将第 \(l\) 至 \(r\) 个数中删去的恢复。

• 询问第 \(l\) 至 \(r\) 个数的和。

输入格式

第一行两个整数 \(n,m\)。

随后 \(n\) 行，每行 \(3\) 个整数 \(opt,l,r\)，分别表示操作序号、操作左端点和右端点。

输出格式

对于最后一个操作，输出结果。

样例 #1

样例输入 #1

6 4
1 1 4 5 1 4
1 3 5
3 1 6
2 4 6
3 1 4

样例输出 #1

6
7

提示

对于 \(50\%\) 的数据，\(1 \le n \le 3000,1 \le m \le 3000\)。

对于 \(100\%\) 的数据，\(1 \le n \le 10^6,1 \le m \le 10^6,1 \le a_i \le 10^9\)。