题目描述

M 国有 $n$ 座城市，城市之间有一些道路相连， 使得整个 M 国的地图形如一个树形结构。

小 Y 是 M 国的一个商人，他打算在M国的城市之间进行一次贸易。

经过市场调查，小 Y 得知，现在市面上可供贸易的货物共有 $m$ 种，第种货物有三种属性 $a_i, b_i,p_i$。他可以选择任意一种货物，在任意一座城市以 $a_i$ 元的价格买入，沿道路到达任意一座城市并以 $b_i$ 元的价格卖出，但贸易行为是有风险的，每当小 Y 试图经过一条道路时，他手上的货物都有 $p_i$ 的概率损毁，一旦损毁小 Y 就无法卖出货物，只能白白承担全部损失。

为了进一步进行市场调查, 并分析比较选择哪种货物更赚钱, 小 Y 决定随机选择两座城市（可能相同）作为起点和终点，并在这两座城市之间展开贸易。

你需要帮小 Y 计算：对于每一种货物而言，小 Y 选择这种货物并按如上策略进行贸易的的期望收益是多少。

输入格式

第一行为两个正整数 $n,m$。

接下来 $n-1$ 行，每行两个正整数 $u_i,v_i$，表示一条连接 $u_i$ 和 $v_i$ 的道路。

接下来 $m$ 行，每行四个非负整数 $a_i,b_i,x_i,y_i$，表示一种货物的各种属性，其中 $p_i=\frac {x_i}{y_i}$。

输出格式

输出 $m$ 行，每行一个非负整数，分别表示每种货物的期望收益对 $998244353$ 取模的结果。

如果答案用既约分数表示为 $\frac x y$，你只需要输出整数 $z$，使得 $0\le z<998244353$ 且 $yz\equiv x\pmod{998244353}$。

样例

3 4
1 2
1 3
1 2 1 2
0 2 1 3
2 3 0 1
2 3 1 1

887328314
603876215
1
998244352

对于第一种货物：有 $\frac 1 3$ 的概率起点与终点选在同一座城市，此时货物损毁的概率为 $0$；有 $\frac 4 9$ 的概率起点与终点选在相邻两座城市，此时货物损毁的概率为 $\frac 1 2$；有 $\frac 2 9$ 的概率起点与终点选在不相邻的两座城市，此时货物损毁的概率为 $\frac 3 4$。若货物未损毁可获益 $1$ 元，否则损失 $1$ 元。故期望收益为 $\frac 1 3\times 1+\frac 4 9\times(\frac 1 2\times 1-\frac 1 2\times 1)+\frac 2 9\times (\frac 1 4\times 1-\frac 3 4 \times 1) = \frac{2}{9}$。

对于第二、三、四种货物：答案分别为 $\frac {118}{81}$、$1$、$-1$。

数据范围及约定

对于全部的数据，保证 $1\le n,m\le 10^5$，$1\le u_i,v_i\le n$，$0\le a_i,b_i<998244353$，$y_i\not=0$，输入的图保证是一棵树。