This is an approximation problem

Cat Noku arranging n circles for a party.

The i-th circle has radius \(r_i\) and weight \(w_i\).

Cat Noku must arrange the circles in the plane such that no two overlap.

Let \((x_i, y_i)\) be the final position of the center of the i-th circle in the arrangement. The coordinates must be at integer positions.

Then, his score will equal \(\frac{\sum_{i=1}^{n} w_i}{\sum_{i=1}^{n} w_i \sqrt{x_i^2 + y_i^2}} \cdot 10^9\). His score will be zero if any two circles are overlapping. It is ok for two circles to touch.

Find any such arrangement that maximizes the score. Note, this is an approximation problem, so you do not need to find an optimal answer.

Input Format

The first line of input will contain a single integer n. The next n lines of input will each contain two integers \(r_i, w_i\).

Output Format

Print n lines with two integers each. The i-th line denotes the center of the i-th circle in the arrangement.

The absolute values of the output coordinates must be at most 10^9.

Test case generation

n will be chosen uniformly at random between 3 and 1,000.

\(r_i, w_i\) will be chosen uniformly at random between 1 and 1,000.

During the contest, 100 tests will be provided. After the contest ends, 100 additional cases will be generated, and the combined results will be used to determine your final score.