Brownie Points I

Time limit1sMemory limit128 MB

Summary
Given a fixed crossing point, split the remaining brownie points into the four quadrants and count Stan's two quadrants versus Ollie's two.
Level

Easy3 of 10

Topics
Geometry, Implementation
Solved
No attempts yet

Problem

Stan and Ollie play the game of Odd Brownie Points. A number of brownie points sit in the plane at integer coordinates. Stan moves first and draws a vertical line. This line must pass through at least one brownie point, and it may pass through several points that share the same xx-coordinate. Ollie then draws a horizontal line, which must pass through a brownie point that already lies on Stan's vertical line.

The two lines split the plane into four quadrants. The quadrant that contains points with arbitrarily large positive coordinates is the top-right quadrant.

Each player scores from the brownie points inside the quadrants. A brownie point that lies on either line (i.e., a line passes through it) counts for no one. Stan earns one point for every uncrossed brownie point in the top-right and bottom-left quadrants. Ollie earns one point for every uncrossed brownie point in the top-left and bottom-right quadrants.

Given the point through which both lines are drawn, compute Stan's and Ollie's scores.

Input

The input contains several test cases. The first line of each test case holds a positive odd integer nn (1<n<2000001 < n < 200000), the number of brownie points. Each of the next nn lines holds two integers: the xx-coordinate and the yy-coordinate of one brownie point. No two brownie points share the same location. The input ends with a line that contains a single 00 in place of nn.

Output

For each test case, print one line with two integers separated by a single space: Stan's score followed by Ollie's score. Both lines are drawn through the point that lies exactly in the middle of that test case's list of points, i.e., the n+12\frac{n+1}{2}-th point given.

Examples1

  1. Example 1

    Input
    11
    3 2
    3 3
    3 4
    3 6
    2 -2
    1 -3
    0 0
    -3 -3
    -3 -2
    -3 -4
    3 -7
    0
    
    Expected output
    6 3