题目描述

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}$。

输出格式

第一行输出一个$n$。

接下来输出 $n$ 行，每行一个非负整数，分别表示距离为i的点对数对 $998244353$ 取模的结果。

样例

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

3
4
2
0

数据范围及约定

对于全部的数据，保证 $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$，输入的图保证是一棵树。