Centennial Woodpecker

Time limit2sMemory limit512 MB

Summary

A ship moves right and can only turn right; stars block it. Count the energy spent before a coordinate exceeds 1e10, or report that it never happens.

Level: Medium6 of 10
Topics: Simulation, Implementation, Hash map, Math
Solved: No attempts yet

Problem

The map of a galaxy far, far away is an infinite plane divided into unit squares. Some squares contain stars, and flying through them is dangerous. The remaining squares are safe.

The spaceship <> emerges from a wormhole in the square $(0, 0)$ and initially moves to the right (that is, in the direction of increasing first coordinate). After a hard battle the ship's engine is damaged, so the ship can only turn right by a right angle. The ship is controlled by an autopilot, which, if the next square along the current course is safe, moves the ship into it without spending energy. Otherwise the autopilot stays in the current square and turns, spending one unit of energy to do so.

You must determine how many units of energy the ship will spend until one of its coordinates exceeds $10^{10}$ in absolute value, or determine that this will never happen.

Input

The first line of input contains an integer $n$ , the number of stars in the galaxy ( $0 \le n \le 1000$ ).

Each of the following $n$ lines contains two integers $x_i$ and $y_i$ , the coordinates of one star ( $-10^9 \le x_i, y_i \le 10^9$ ). It is guaranteed that no two stars occupy the same square and that the square $(0, 0)$ contains no star.

Output

Print a single number, the number of units of energy the ship will spend during its journey if the journey ends, or <<oo>> if it never ends.

Examples2

Example 1
Input
```
4
2 0
-2 -1
0 3
1 -3
```
Expected output
```
2
```

Example 2

Input

Expected output

oo