迅风的班上一共有 n 个人，学号为 1～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。