题目描述

作为新一代巡查系统 lzx 正在 ban IP

他在一棵树的任意一节点 $a$ 上，他首先会前往所有节点，然后他会前往终点 $b$，然后瞬移到 $a$ 并开始新的一轮暴政，他从 $a$ 到任意一个节点 $c$ 再到 $b$ 的时间为 $a,c$ 两点之间唯一简单路径上边权的异或和异或 $c,b$ 两点之间唯一简单路径上边权的异或和（设为 $dis(a,c) \oplus dis(c,b)$）。

这棵树有 $n$ 个节点

现在要求 $\sum_{c=1}^n dis(a,c) \oplus dis(c,b)$

输入格式

共 $n+q$ 行

第 $1$ 行：四个正整数 $n,q,a,b$

第 $2 \sim n$ 行：每行三个整数 $u,v,w$ 表示 $u$ 与 $v$ 之间有一条权值为 $w$ 的边

第 $n+1 \sim n+q$ 行：每行两个整数 $u,v,w$ 表示将 $u$ 与 $v$ 之间的边的权值修改为 $w$

输出格式

$q$ 行每行一个整数，表示修改后 $\sum_{c=1}^n dis(a,c) \oplus dis(c,b)$

5 2 1 4
2 1 3
5 2 4
2 3 7
3 4 1
1 2 4
2 3 4

10
5

提示

$1 \le n,q \le 5 \times 10^5$

所有 $w$ 满足 $1 \le w \le 10^8$

样例解释

第一次修改前

第一次修改后

第二次修改后