eolymp
bolt
Try our new interface for solving problems
Problems

Square Counting

Square Counting

Time limit 1 second
Memory limit 64 MiB

A simple polygon with vertices having integer coordinates is placed on a checker board. Determine the number of light and dark squares completely encompassed by the polygon.

Input data

Contains several tests (at most 25). Each test case starts with the number n (3 n 100) of vertices in the polygon. Each of the next n lines contains two integers x and y (0x 10000, 0 y 10000), describing the coordinates of the polygon vertices. The input ends with a case when n equals 0, which should not be processed. You can assume that the top left corner has coordinate (0, 0). The picture above corresponds to the first sample input.

Output data

For each test case, output a line containing two space separated integers, the number of light and dark squares completely encompassed by the polygon in descending order.

Examples

Input example #1
11
2 1
6 4
10 1
15 3
13 8
15 11
9 9
11 5
7 11
1 7
4 8
4
0 0
0 1
1 1
1 0
0
Output example #1
27 25
1 0