题目背景

本题分值按 COCI 原题设置，满分 $160$。

题目描述

一个新城镇刚刚在一个小国家落成。 像往常一样，Mirko 获得了首席税务监察员的职位。 他的职责是确保镇上所有不同公司的充分会计处理。

沿大街有 $N$ 个营业厅，从左到右编号为 $1\sim N$。一开始所有的办公室都是空的； 随着时间的推移，公司将进出这些办公室。 不时，Mirko 会经过一些办公室，只检查这些办公室中目前最富有的一家。

搬入的公司用四个整数来描述：

• $T$：搬入的日期。此处设小镇建成当天为 $1$。

• $K$：办公室序号。

• $Z$：公司的每日利润（如果公司亏损，则可能为负数）。

• $S$：搬入当天公司账户余额。

如果办公室 $K$ 中已经有一家公司，则当新公司搬入时，该公司搬出。

新公司直到搬入后的第二天才开始营业（或赚取利润）。

米尔科的巡视由三个整数描述：

• $T$：巡视的日期。小镇建成当天为 $1$。

• $A,B$：Mirko 将会经过 $[A,B]$ 内所有办公室。

由于 Mirko 只在一天结束时工作，所以到 Mirko 散步时，所有公司都已经完成了当天的业务并公布了当天的利润。

帮助 Mirko 编写一个程序，在每次闲逛时查找 Mirko 路过的当前最富有的公司的账户余额。

输入格式

输入的第一行包含两个正整数，$N\ (1 ≤ N ≤ 10^5)$ 和 $M \ (1 ≤ M ≤ 3\times 10^5)$， 分别表示办公室和巡视的数量。

接下来 $M$ 行，每一行包含一个事件的描述，格式为 1 T K Z S（公司搬入）或 2 T A B（Mirko 的巡视）。

所有事件都按时间顺序给出，每天最多发生一个事件（即 $T$ 将是严格递增）。 最后一个事件的天数将小于 $10^6$, 所有 $Z$ 和 $S$ 数字的绝对值 值将小于 $10^6$。

输出格式

对于 Mirko 的每一次巡视，输出一行包含 Mirko 检查的公司的账户余额，或者如果他将经过的所有办公室都是空的，则输出单词 nema。

2 4
1 1 1 2 4
1 2 2 3 2
2 5 1 2
2 7 1 2

12
17

3 6
1 1 1 4 -2
1 2 2 2 6
2 3 3 1
2 4 3 1
1 5 3 -6 20
2 6 2 3

8
10
14

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
nema
7
31
17