Cho một hình đa giác, nhiệm vụ của bạn là tính số điểm nguyên nằm bên trong hoặc trên đường viền hình đa giác. Một điểm nguyên là điểm mà tọa độ của nó là những số nguyên.

Một hình đa giác bao gồm \(n\) điểm \((x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)\). Các cặp điểm \((x_i, y_i)\) với \((x_{i+1}, y_{i+1})\) thì kề nhau với mọi \(i = 1, 2, \dots, n - 1\), và cặp điểm \((x_1, y_1)\) với \((x_n, y_n)\) thì cũng kề nhau.

Input

• Dòng đầu tiên chứa một số nguyên \(n\): số lượng đỉnh của đa giác.
• Sau đó, bao gồm \(n\) dòng miêu tả các điểm. Dòng thứ \(i\) chứa hai số nguyên \(x_i, y_i\).
• Dữ kiện đề đảm bảo rằng hình đa giác này là đa giác đơn, nói cách khác là nó không có cặp cạnh nào cắt nhau.

Constraints

• \(3 \leq n \leq 10^5\)
• \(-10^6 \leq x, y \leq 10^6\)

Output

• In ra hai số nguyên: số lượng điểm nguyên ở trong hình đa giác và số điểm nguyên nằm trên đường viền đa giác.

Example

4
1 1
5 3
3 5
1 4

6 8