在一个小国里，一个新城镇刚刚落成。和往常一样，Mirko 获得了首席税务监察员的职位。他的职责是确保镇上所有不同公司的账目正确。

主街旁有 $N$ 个办公室，从左到右依次编号为 $1$ 到 $N$。起初，所有办公室都是空的；随着时间的推移，公司会搬进和搬出这些办公室。Mirko 会不时路过其中一些办公室，并仅审计这些办公室中当前最富有的那家公司的账目。

一家公司搬入由四个整数描述：

• $T$ – 搬入日期，从城镇落成（即第 $1$ 天）开始编号，
• $K$ – 办公室编号，
• $Z$ – 公司的每日利润（如果公司亏损，则可能为负数），
• $S$ – 搬入当天公司账户的余额。

如果办公室 $K$ 中已经有一家公司，那么在新公司搬入时，原公司就会搬出。新公司在搬入后的第二天才开始营业（或赚取利润）。

Mirko 的巡查由三个整数描述：

• $T$ – 巡查日期，从城镇落成开始编号，
• $A$ 和 $B$ – Mirko 将路过编号在 $A$ 和 $B$ 之间（含 $A$ 和 $B$）的所有办公室。

由于 Mirko 仅在一天结束时工作，因此在 Mirko 巡查时，所有公司都已结束当天的营业并结算了当天的利润。

请编写一个程序，帮助 Mirko 找出在每次巡查中，他所路过的办公室中当前最富有的公司的账户余额。

输入格式

输入的第一行包含两个正整数 $N$（$1 \le N \le 100\,000$）和 $M$（$1 \le M \le 300\,000$），分别表示办公室的数量和事件的数量。

接下来的 $M$ 行，每行包含一个事件的描述，格式为以下两者之一：

• 1 T K Z S（表示公司搬入）
• 2 T A B（表示 Mirko 的巡查）

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

输出格式

对于 Mirko 的每次巡查，输出一行，包含 Mirko 将要审计的公司的账户余额；如果他路过的所有办公室都是空的，则输出单词 nema（不带引号）。

样例

输入样例 1

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

输出样例 1

12
17

输入样例 2

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

输出样例 2

8
10
14

输入样例 3

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

输出样例 3

-1
nema
7
31
17