题目描述

给定质数 $p$ 和 $n$ 个形如 $a_ix_u + b_ix_v \equiv c_i \pmod p$ 的方程，这个方程组有 $x_1 \dots x_n$ 这些变量，求出一组 $x_1 \dots x_n$ 的解。

数据保证有解且解唯一。

输入格式

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

接下来 $n$ 行，第 $i$ 行五个整数 $u , v , a_i , b_i , c_i$ 描述一个方程及其参数。保证给出的无序数对 $(u, v)$ 互不相同。

输出格式

$n$ 行，第 $i$ 行输出 $x_i$ 的值，注意 $0\le x_i < p$。

数据范围与提示

$3\le n\le10^5 , 3\le p\le 10^9$

$1\le u,v\le n , 1\le a,b<p , 0\le c<p$