#103463. [BZOJ 3463] [COCI2012] Inspector

在一个小国家中，一个新的小镇终于建成了！如往常一样，Mirko 获得了首席税务巡查员的职位。他的任务是保证正确地计算各公司的收入情况。一共有 家办公室坐落在主干道上，从左到右被编号为 。一开始，所有办公室一开始都是空的。随后，一些公司会搬入或搬出某些办公室。Mirko 时不时地会经过某些办公室并审查在这些办公室中，最富有的公司的账目。

一个公司被以如下的方式描述：

• : 表示搬入的第一天。

• : 表示搬入的办公室的标号。

• : 公司每日的盈利。（可以是负值表示亏损）

• : 公司搬入时的公司财务情况。（即公司的账户资金，也可以是负值）

如果一家公司已经在 办公室了，当有新公司要进入 办公室时，这家公司会立刻搬出。

新公司第一天并不会运营，盈利从第二天开始计算。

Mirko 的审查以 个整数来描述：

• : 审查的时间。

• 和 : Mirko 会检查 办公室至 办公室（包括 和 ）之间的公司。

Mirko 只会在一天结束时检查，所有公司这时已经计算完成了当天利润。

第一行包含 2 个正整数： 表示办公室的数量和 表示事件的个数。

接下来 行，遵循以下格式：1 T K Z S 或 2 T A B（含义如题目描述）。其中 会严格递增，并且最后一天小于 , 且 。 （注意 可能大于）

对于每次 Mirko 的审查，每行输出一个整数，表示当天最富有的公司的资产（可以为负）。

如果 Mirko 经过的所有办公室中都没有公司入驻，则输出 。

样例输入 #1

5 9
1 1 5 4 -5
2 2 3 5
1 3 4 6 9
2 4 1 2
1 6 2 2 3
2 8 2 1
1 9 4 0 17
2 10 5 5
2 11 1 4

样例输出 #1

-1
nema
7
31
17

By Jason Hsiao