题目描述

太空中一共有n座星球，它们之间可以通过空间传送装置进行转移。空间传送装置分为m种，第i种装置可以用4个参

数a_i,b_i,c_i,d_i来描述。因为时空抖动的问题，在非整数时刻禁止使用空间传送装置。如果在整数s时刻使用装

置，那么需要花费((a_i*s+b_i) mod c_i)+d_i单位时间才能完成传送。现在是s时刻，小Q位于1号星球，请写一个

程序计算从1号星球到每个星球最少需要的时间。

输入格式

第一行包含4个正整数n,m,s,e(2<=n<=100000,1<=m<=50,1<=s<=2000,1<=e<=200000)

分别表示星球的个数、空间传送装置的种类数、当前的时间以及空间传送装置的个数。

接下来m行，每行4个正整数a_i,b_i,c_i,d_i(1<=a_i,b_i,c_i,d_i<=2000)，依次描述每种装置的参数。

接下来e行，每行3个正整数u_i,v_i,w_i(1<=u_i,v_i<=n,u_i!=v_i,1<=w_i<=m)

表示从星球u_i可以使用第w_i种装置单向传送到星球v_i。

输出格式

输出n-1行，每行一个整数，第i行表示从1到i+1的最少所需时间，若无解输出-1。

样例

样例输入

3 2 1 3
1 1 5 1
2 2 7 1
1 2 1
2 3 2
3 1 1

样例输出

3
6

HINT 1到3：在时刻1使用第一种装置从1传送到2，花费时间3，再等待2单位时间，于时刻6使用第二种装置到达3，花费时间1。