题目描述

给定质数 $p$ 和 $n$ 个形如 $a_i x_u + b_i x_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 \le 10^5$ , $3 \le p \le 10^9$