题目描述

迅风的班上一共有 $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$ 行，每行一个整数，表示一个同学对另一个同学的好感度最大值。

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

4
6
4

提示

【样例 1 解释】

班里有 $2$ 位同学，发生了 $3$ 件事情。下面用表格来整理这三件事情。

【数据范围】

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