题目来自第 31 次 CSP 认证 T5，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 2.0 秒

空间限制： 512 MB

题目描述

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

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

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

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

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

西西艾弗岛事先在狄迪吉岛中安插了一系列间谍，得到的情报消息如下：敌军将选择西西艾弗岛的两座城市作为进攻的“起点”和“终点”，并派遣军队在进攻起点城市登陆，沿两座城市间唯一的路径进攻至终点城市。同时，间谍还背负着另外一个重要的使命：影响敌军对于起点和终点城市的决策，使得敌军受到的总损失尽可能大，其中“总损失” $T$ 定义为敌军经过的每条道路上的“受到阻击的损失”减去“发掘宝物的收益”之和。如果从起点城市到终点城市经过的路径编号分别为 $c_1,c_2,...,c_{k-1},c_k$，那么 $T=\sum\limits_{i=1}^k (b_{c_i}-w_{c_i})$。

此外，遗迹中宝物的价值与所处的环境属性密切相关，而阴阳龙的“现身”会使得环境的阴阳属性发生变化，这会使得敌军通过现身位置处的某一条道路时“发掘宝物的收益” $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\leq n \leq 10^5, 0 \leq m \leq 10^5, 1 \leq u_i,v_i \leq n, 1 \leq x_i \leq n-1, 0 \leq w_i,b_i,y_i \leq 10^9$。

• 特殊性质 A：$u_i=i,v_i=i+1$。
• 特殊性质 B：$0 \leq w_i,y_i \leq 10^8 \leq b_i$。
• 特殊性质 C：保证任意两座城市均可在经过不超过 $100$ 条道路的前提下互相到达。