Refugee

A civil war has broken out in country A.

Because of this, many refugees of the civil war have come to country B, and country B has built a refugee camp for them.

The following figure shows the refugee camp on the coordinate plane. The blue line is a river, and the red dots are the residence locations of the refugees.

There is one river in the refugee camp that flows along the line (x=0).

The refugees must use this river to obtain water, but the water quality is poor, so a water treatment facility is to be built.

However, because of budget issues, the water treatment facility can be built at only one point on the river, so it is to be built at the location that minimizes the sum of the distances each refugee travels to reach the facility.

Even at this moment, refugees keep arriving. Whenever people move into the refugee camp, report the location where the water treatment facility must be built and the sum of the travel distances at that time.

The distance between two coordinates ((x_1, y_1)) and ((x_2, y_2)) is computed as (|x_1 - x_2| + |y_1 - y_2|).

The first line gives the number of refugees (N).

Then (N) lines follow, each giving the location ((x_i, y_i)) of the (i)-th refugee to move in, separated by spaces.

Print the answer over (N) lines, separated by spaces.

On the (i)-th line, print the (y)-coordinate of the water treatment facility that minimizes the sum of the distances the refugees from the (1)-st through the (i)-th to move in travel to the facility, and the sum of the travel distances at that time, separated by spaces.

If multiple locations satisfy this, print the location with the smallest (y)-coordinate.

• 1 ≤ (N) ≤ 105
• -109 ≤ (x_i), (y_i) ≤ 109, and all coordinates are integers.