13899번 - Coordinates 스페셜 저지다국어

In this problem, you are an advisor to a galactic empire that tries to locate all the rebel bases on a planet Taboo. The map of the planet Taboo is a grid of size 10⁸ ×10⁸ and a position of a rebel based can be described by coordinate (x,y) where 0 ≤ x, y < 10⁸.

The empire captures a number of the rebels that surrender and interrogate them about the locations of the bases. Unfortunately, each surrendered rebel can only tell how far along X axis and Y axis a pair of bases are. Your job in this problem is to help reconstructing possible coordinates of all the bases that is consistent with all the interrogations.

First line consists of two integers, N and M where 1 ≤ N ≤ 100 000 is the number of bases and N ≤ M ≤ 1 000 000 is the number of captured rebels.

The next M lines consist of 4 integers, a_i, b_i, dx_i, and dy_i where 1 ≤ a_i , b_i ≤ N, -10⁸ ≤ dx_i, dy_i ≤ 10⁸ indicating that the x-coordinate of base bi subtracted with the x-coordinate of base a_i is dx_i and the y-coordinate of base b_i subtracted with the y-coordinate of base a_i is dy_i

It is guaranteed that we can always deduce the positions of the bases from the input. 

The output consists of N lines each line consists of 2 integers x_j and y_j indicating possible position of the j th base. You can answer any solution that is consistent with all the interrogations. Translation of map is possible to outside of [0, 10⁸], however, the output coordinate of each base must be between -10⁹ to 10⁹

This is one of the possible coordinates, assuming that the first base is at (0,0)