Description

小雷在绘制一张藏宝图，把藏宝图视为一个足够大的平面坐标系，藏宝图中心点为坐标原点（0,0）。现有编号为1至N的N个宝藏，已知1号宝藏坐标为（0,0）以及M条宝藏位置关系的信息，每条宝藏位置关系信息如下：给定四个整数p,q,a,b;q号宝藏位置的坐标为：(p_x+a,p_y+b)，其中(p_x,p_y)表示p号宝藏的坐标。、 例如：p=1,q=2,a=1,b=1;已知1号宝藏坐标为（0,0）,2号宝藏的坐标为（0+1,0+1）即（1,1）。 请根据已知信息计算出每个宝藏的具体坐标并按编号顺序依次输出；如果某个宝藏的坐标无法计算得到，则输出-1。 例1： N=3，M=2； 两条宝藏位置关系如下 1 2 1 1 2 3 1 2 1号宝藏坐标为（0,0）； 由第1条宝藏位置关系可知，2号宝藏坐标为（0+1,0+1），即为（1,1）； 由第2条宝藏位置关系可知，3号宝藏坐标为（1+1,1+2）即（2,3）。

Format

Input

第一行包含两个整数N和M，分别表示宝藏的数量以及宝藏位置关系信息的数量，整数间以一个空格隔开； 接下来M行每行包含四个整数p,q,a,b,整数间以一个空格隔开； 数据保证计算出的宝藏坐标是唯一的。

Output

共N行。 如果第i号宝藏的坐标能够计算出，则输出两个整数x，y，分别表示第i号宝藏位置的x坐标与y坐标；如果不能计算出第i号宝藏的坐标，则输出-1.

Samples

3 2
1 2 1 1
2 3 1 2

0 0
1 1
2 3

3 2
1 2 1 2
2 1 -1 -2

0 0
1 2
-1

Limitation

测试点1~10:1<=N,M<=10⁵,1<=p,q<=N,p!=q,-10⁹<=a,b<=10⁹。