有一个古老的帝国，这个帝国有 n 个城邦，这些城邦由恰好 n 条道路连结（每条路连结两个不同的城邦，保证任意两条道路连结的城邦组不同，即没有重边），所有城邦保证连通。
每个城邦有一个神秘的代号 x_i ，每个 x_i 都是一个 [0,p-1] 范围内的非负整数，其中 p 为一个已知的质数。
由于年代过于久远，这些 x_i 已经不为人知了，但是作为一个历史爱好者，你希望考证一下这些 x_i 的值。
幸运的是，你找到了一些线索，对于每条道路你都得到了一个方程，这个方程的形式为：设这条道路连结的两个城邦为 u , v ，以及有三个参数 a , b , c，那么有 a*x_u + b*x_v = c (mod p)，即这是一个在模质数 p 域下的方程。
现在你需要根据这些线索来求出一组满足条件的 x_i ，数据保证有解且解唯一。

第一行两个正整数 n , p ( 3 ≤ n ≤ 10^5 , 3 ≤ p ≤ 10^9 )。
接下来 n 行，每行五个整数 u , v , a , b , c 描述一条道路及其参数 ( 1 ≤ u,v ≤ n , 1 ≤ a,b < p , 0 ≤ c < p )。

输出 n 行，依次为 x_i (0 ≤ x_i < p)。

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

0
3
4
0
2
4