Coordinates

You advise a galactic empire that wants to locate every rebel base on the planet Taboo. The map of Taboo is a grid of size $10^8 \times 10^8$, and the position of a base is a coordinate $(x, y)$ with $0 \le x, y < 10^8$.

The empire captured rebels who surrendered and interrogated them about the bases. Each captured rebel only tells how far apart two bases are along the $x$ axis and along the $y$ axis. Reconstruct coordinates for all bases that agree with every interrogation.

The first line contains the number of bases $N$ and the number of captured rebels $M$. ($1 \le N \le 100\,000$, $N \le M \le 1\,000\,000$)

Each of the next $M$ lines contains four integers $a_i$, $b_i$, $dx_i$, $dy_i$. ($1 \le a_i, b_i \le N$, $-10^8 \le dx_i, dy_i \le 10^8$) The $x$ coordinate of base $b_i$ minus the $x$ coordinate of base $a_i$ is $dx_i$, and the $y$ coordinate of base $b_i$ minus the $y$ coordinate of base $a_i$ is $dy_i$.

The interrogations never contradict each other, and they determine the position of every base.

Print $N$ lines. Line $j$ contains the coordinates $x_j$ and $y_j$ of base $j$, separated by a space.

Translating the whole map keeps every interrogation satisfied. To make the answer unique, print the coordinates that place base 1 at $(0, 0)$. Under that rule the absolute value of every printed coordinate is at most $10^9$.