图上方程组

时间限制:30s      空间限制:512MB

题目描述


输入格式

第一行有三个整数V,E,P
接下来E行,每行四个整数x,y,a,b分别表示x与y有一无向边,a(x,y)=a,b(x,y)=b。显然根据题意默认a(y,x)=-a
b(y,x)=b。输入数据保证没有自环和重边。


输出格式

一共E行,按输入数据给定边的顺序,输出最小的大于等于
零的C(x,y)值。很显然c(y,x)=-c(x,y) mod p.但是不需要
输出c(y,x)
如果无解,输出-1


样例输入

3 3 7
1 2 15 -6
2 3 22 8
3 1 1 -69

样例输出

1
1
1


提示

V<=100,E<=2000,P<=10^18


题目来源

基尔霍夫定理