题目描述

迅风的班上一共有 $n$ 个人，学号为 $1\sim n$。每个同学都对班里其他所有同学有一个好感度，这个好感度始终是自然数。一开始每个人对其他人的好感度为 $0$。

接下来在这个班级里按时间顺序发生了 $m$ 件事情。每件事情发生后，会让一位同学对另一位同学的好感度增加或减少。

迅风想在每一件事发生后，立刻知道如果他随便选两个同学 $p,q$，那么 $p$ 对 $q$ 好感度的最大值是多少。你能帮帮他吗？

注意：好感度不是相互的。$p$ 对 $q$ 的好感度可以不等于 $q$ 对 $p$ 的好感度。

输入格式

输入的第一行有两个正整数 $n,m$，分别表示同学的人数和事情的个数。

之后有 $m$ 行，每行有四个正整数 $op,a,b,c$ 描述一次事情：

• 如果 $op$ 为 $1$，表示事情发生后，$a$ 号同学对 $b$ 号同学的好感度增加了 $c$；
• 如果 $op$ 为 $2$，表示事情发生后，$a$ 号同学对 $b$ 号同学的好感度减少了 $c$。

输出格式

输出共 $m$ 行，每行一个整数，表示一个同学对另一个同学的好感度最大值。

样例 #1

样例输入 #1

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

样例输出 #1

4
6
4

提示

样例解释

事件 $1$ 后 $1$ 对 $2$ 为 $4$，最大为 $4$；事件 $2$ 后 $2$ 对 $1$ 为 $6$，最大为 $6$；事件 $3$ 后 $2$ 对 $1$ 变为 $3$，最大为 $4$。

数据规模与约定

对于所有数据，保证 $2\leq n,m\leq 100$，$1\leq a,b\leq n$，$1\leq c\leq 10^5$，且任意时刻任何人对其他所有人的好感度都是自然数。