#6193. 「美团 CodeM 复赛」神秘代号

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: rapiz

题目描述

给定质数 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

样例

样例输入

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

数据范围与提示

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