Tower Framework

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Today Zenik has a difficult task — to connect \(n\) towers into a single network.

All towers are located in a row, the \(i\)-th tower is at coordinate \(x_i\), and its height is \(y_i\). Zenik can run cables between the tops of two towers, the cable must be straight and not intersect with other towers. More formally, Zenik can run a cable between towers \(i\) and \(j\) if the segment between the points \((x_i, y_i)\) and \((x_j, y_j)\) does not intersect with any tower, meaning that for no tower \(k\) (\(i < k < j\)) can the cable pass below \(y_k\). Note that cables can intersect with each other.

Zenik wants to run cables so that each tower is connected to every other directly or through other towers.

He is interested in what minimum sum of cable lengths he can achieve.

Input

The first line contains a single integer \(n\) — the number of towers.

The next \(n\) lines contain 2 integers \(x_i\) and \(y_i\) each — the coordinate and height of the \(i\)-th tower.

Output

Let \(d_1, d_2, \dots, d_{n-1}\) be the lengths of the cables that Zenik will use.

Output a single number \(d_1^2\ XOR\ d_2^2\ XOR\ \dots\ XOR\ d_{n-1}^2\).

Note that you need to minimize \(d_1 + d_2 + \dots + d_{n-1}\) specifically. It is guaranteed that for all solutions that minimize the sum of cable lengths, the corresponding value will be the same.

Constraints

\(2 \le n \le 5 \cdot 10^5\),

\(1 \le x_i, y_i \le 10^9\),

\(x_i < x_{i + 1}\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 1 2 4 7 5 1 7 8	13

Notes

In the example, it is optimal to run the following cables:

• between the first and second tower with length \(\sqrt{34}\)

• between the second and third tower with length \(\sqrt{37}\)

• between the second and fourth tower with length \(\sqrt{10}\)

You need to output \(34\ XOR\ 37\ XOR\ 10 = 13\).

Note that it is forbidden to run a cable between the first and third tower because it would intersect with the second tower.