【题目描述】

仙人掌镇这次只有一棵树。

镇上有 $𝑛$位居民，居民之间有 $𝑛−1$段友谊，恰好构成一棵树。为了举办联谊舞会，镇长给每段友谊准备了一张双面联谊卡。

第 $𝑖$张联谊卡对应居民 $𝑢_𝑖$ 和 $𝑣_𝑖$之间的友谊。卡片正面写着 $𝑎_𝑖$，反面写着$𝑏_𝑖$。舞会当天，每张联谊卡都会被翻开一面。

如果一张联谊卡翻到正面，对应的两位居民就可以凭这段友谊组成舞伴；如果翻到反面，这段友谊本场不能用来组成舞伴。翻到正面的卡片分值为 $𝑎_𝑖$，翻到反面的卡片分值为 $𝑏_𝑖$。

确定所有联谊卡的朝向后，镇长会尽可能多地安排舞伴。每位居民最多参加一对舞伴，所以镇长需要从正面联谊卡中选出尽可能多张卡，并且不能让两张被选中的卡涉及同一位居民。选出的卡数就是最多舞伴对数。

这一场舞会的热闹度定义为： 最多舞伴对数×所有联谊卡分值的乘积

请你求出所有可能的舞会的热闹度之和。由于答案可能很大，请输出其对 998244353 取模的结果。

注意：最多舞伴对数只与哪些联谊卡翻到正面有关，不是卡片分值之和。对于同一场舞会，即使存在多种最多的安排方式，也只将最多舞伴对数计入一次。

【输入格式】

第一行一个整数 $𝑛$。

接下来$𝑛−1$行，每行四个整数 $𝑢_𝑖,𝑣_𝑖,𝑎_𝑖,𝑏_𝑖$，表示一张连接居民$𝑢_𝑖$ 和$𝑣_𝑖$的联谊卡， 以及它的正面分值$𝑎_𝑖$、反面分值$𝑏_𝑖$。

【输出格式】

输出一行一个整数，表示所有可能的舞会的热闹度之和对 998244353 取模的结果。

2
1 2 3 5

3

3
1 2 2 3
2 3 5 7

39

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

277

【样例1解释】

共有两种卡片朝向：

•卡片翻到反面，不能安排舞伴，热闹度为 0×5=0；

•卡片翻到正面，可以安排 1 对舞伴，热闹度为 1×3=3。 答案为 3。

【样例2解释】

设两张联谊卡分别对应 𝑒1,𝑒2。四种卡片朝向下的热闹度分别为：

•两张卡都翻到反面：0×3×7=0；

•只有 𝑒1 对应的卡翻到正面：1×2×7=14；

•只有 𝑒2 对应的卡翻到正面：1×3×5=15；

•两张卡都翻到正面：最多只能安排 1 对舞伴，热闹度为 1×2×5=10。

答案为 0+14+15+10=39。

【样例3解释】

当连接 1−2 和 3−4 的两张联谊卡翻到正面，其余卡翻到反面时，最多可以安排 2 对舞伴。这场舞会的热闹度为：

2×2×4×5=80

枚举全部 8 种卡片朝向，热闹度之和为 277。

【数据范围】

对于所有数据：$1≤𝑛≤10^5，1≤𝑢_𝑖,𝑣_𝑖 ≤𝑛，𝑢_𝑖 ≠𝑣_𝑖，0≤𝑎_𝑖,𝑏_𝑖 ≤10^9$。

输入保证给出的是一棵树。

本题共有 100 个独立测试点，每个测试点 1 分。