题目描述

在一个有 $n$ 名成员的社团中，每位成员对其他所有成员都有一个好感度，好感度始终是非负整数。初始时所有人之间的好感度均为 $0$。

接下来按时间顺序发生了 $m$ 件事。每件事会让某位成员对另一位成员的好感度增加或减少一定的数值。

社团管理员想在每件事发生后，立刻知道所有成员之间好感度的最大值是多少。你能帮帮他吗？

注意：好感度不是相互的。成员 $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$ 件事。事件 1 后 $1$ 对 $2$ 好感度为 $4$，最大值 $4$；事件 2 后 $2$ 对 $1$ 好感度为 $6$，最大值 $6$；事件 3 后 $2$ 对 $1$ 好感度降为 $3$，最大值回到 $4$。

【数据范围】

对于全体数据，保证 $2 \le n, m \le 100$，$1 \le a, b \le n$，$1 \le c \le 10^5$，且任意时刻好感度都是非负整数。