题目背景

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：https://www.cspro.org/。

题目描述

上回提到，西西艾弗岛下方有一个庞大的遗迹群，栖息着一种名为“阴阳龙”的神兽。然而隔壁的狄迪吉岛盯上了西西艾弗岛，决定发动一场战争，试图从遗迹群中掠夺有价值的宝物。由此，西西艾弗岛不得不陷入一场漫长的阻击战中，史称“阴阳龙阻击战”。

狄迪吉岛拥有胜过西西艾弗岛的科技实力和武装水平，西西艾弗岛很快发现形势不妙：全歼敌军似乎是不可能的，唯一的策略是凭借主场作战的优势和人海战术，尽可能给敌军带来损失，当敌军发现发动进攻的损失明显超过收益时，就会无趣而归。

具体而言，西西艾弗岛共有 $n$ 座城市，有 $n - 1$ 条道路连接这些城市，使得所有城市之间均可以通过道路互相到达。容易发现，任意两座城市之间都有唯一一条不经过重复城市的路径。

由于缺乏城市巷战的实力，西西艾弗岛决定将防御重心放在道路上。在每条道路上均派遣了一定的军队防守，当敌军经过时对其发动阻击。虽然由于实力的差距，并不能阻止敌军通过道路，但仍然可以对敌军造成一定的损失。

然而，敌军具有更强的科技，可以趁机对道路附近的遗迹进行探索，并掠夺其中的宝物——这也正是敌军发动战争的意义所在。如此，敌军通过一条道路时，“发掘宝物的收益”$w$ 和“受到阻击的损失”$b$ 两个值是独立的。

西西艾弗岛事先在狄迪吉岛中安插了一系列间谍，得到的情报消息如下：敌军将选择西西艾弗岛的两座城市作为进攻的“起点”和“终点”，并派遣军队在进攻起点城市登陆，沿两座城市间唯一的路径进攻至终点城市。同时，间谍还背负着另外一个重要的使命：影响敌军对于起点和终点城市的决策，使得敌军受到的总损失尽可能大，其中“总损失”定义为敌军经过的每条道路上的“受到阻击的损失”减去“发掘宝物的收益”之和，即 $\text{总损失} = \sum_{e\ \text{是路径上的每条边}} (b_e - w_e)$。

此外，遗迹中宝物的价值与所处的环境属性密切相关，而阴阳龙的“现身”会使得环境的阴阳属性发生变化，这会使得敌军通过现身位置处的某一条道路时“发掘宝物的收益”$w$ 发生变化。

这样的“阴阳龙现身”事件共会发生 $m$ 次，你的任务就是帮助间谍计算出在所有事件前及每次事件后，敌军对于起点和终点城市的决策应当怎样改变，以最大化敌军的总损失。

输入格式

从标准输入读入数据。

第 $1$ 行，两个非负整数 $n, m$，分别表示西西艾弗岛的城市数和“阴阳龙现身”事件数。

接下来 $n - 1$ 行，每行 $4$ 个非负整数 $u_i, v_i, w_i, b_i$，表示第 $i$ 条道路连接城市 $u_i$ 和 $v_i$，敌军在这条道路上“发掘宝物的收益”为 $w_i$，“受到阻击的损失”为 $b_i$。

接下来 $m$ 行，每行 $2$ 个非负整数 $x_i, y_i$，表示一次“阴阳龙现身”事件，使得第 $x_i$ 条道路的“发掘宝物的收益”变为 $y_i$。

输出格式

输出到标准输出。

输出 $m + 1$ 行，每行一个非负整数，分别表示在所有事件前及每次事件后，对敌军造成的最大总损失。

5 3
1 2 6 4
2 3 2 1
3 4 5 3
3 5 8 5
3 2
4 3
1 1

0
1
3
4

提示

样例 1 解释

在最初，由于敌人攻打每一条道路都会有正收益，因此间谍最好的策略就是将进攻起点和终点选为同一座城市，这样敌军的总损失为 $0$。

第 $1$ 次事件后，间谍可以将进攻起点和终点分别选在城市 $3$ 和 $4$，这样敌军的总损失为 $3 - 2 = 1$。

第 $2$ 次事件后，间谍可以将进攻起点和终点分别选在城市 $4$ 和 $5$，这样敌军的总损失为 $(3 - 2) + (5 - 3) = 3$。

第 $3$ 次事件后，间谍可以将进攻起点和终点分别选在城市 $1$ 和 $5$，这样敌军的总损失为 $(4 - 1) + (1 - 2) + (5 - 3) = 4$。

数据范围

对于所有测试数据保证：$2 \le n \le 10^5, 0 \le m \le 10^5, 1 \le u_i, v_i \le n, 1 \le x_i \le n - 1, 0 \le w_i, b_i, y_i \le 10^9$。

测试点编号	$n \le$	$m \le$	特殊性质
1	20		无
2	300		^
3 ~ 4	3000		A
5 ~ 6	^		B
7 ~ 9			无
10	$10^5$	0	A
11	^	^	B
12			无
13 ~ 15		$10^5$	A
16 ~ 18		^	B
19 ~ 21			C
22 ~ 25			无

特殊性质 A：$u_i = i, v_i = i + 1$。

特殊性质 B：$0 \le w_i, y_i \le 10^8 \le b_i$。

特殊性质 C：保证任意两座城市均可在经过不超过 $100$ 条道路的前提下互相到达。