Каркас веж

Limits: 2 sec., 256 MiB

Сьогодні у Зеника важке завдання — з’єднати $n$ веж в єдину мережу.

Усі вежі розташовані в ряд, $i$-та вежа в координаті $x_i$, її висота $y_i$. Зеник може проводити кабелі між вершинами двох веж, кабель повинен бути прямим і не перетинатись з іншими вежами. Більш формально, Зеник може провести кабель між вежами $i$ та $j$, якщо відрізок між точками $(x_i, y_i)$ та $(x_j, y_j)$ не перетинається з жодною вежею, тобто для жодної вежі $k$ ($i < k < j$) кабель не може проходити нижче $y_k$. Зауважте, що кабелі можуть перетинатись між собою.

Зеник хоче провести кабелі так, щоб кожна вежа була з’єднана з кожною іншою напряму або через інші вежі.

Йому цікаво, яку мінімальну суму довжин кабелів він може досягти.

Input

У першому рядку задано єдине ціле число $n$ — кількість веж.

У наступних $n$ рядках задано по 2 цілих числа $x_i$ та $y_i$ — координата та висота $i$-ої вежі.

Output

Нехай $d_1, d_2, \dots, d_{n-1}$ — довжини кабелів, які використає Зеник.

Виведіть єдине число $d_1^2\ XOR\ d_2^2\ XOR\ \dots\ XOR\ d_{n-1}^2$.

Зауважте, що вам потрібно мінімізувати саме $d_1 + d_2 + \dots + d_{n-1}$. Гарантується, що для всіх розв’язків, які мінімізують суму довжин кабелів, відповідне значення буде однаковим.

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

В прикладі вигідно провести такі кабелі:

• між першою та другою вежею довжиною $\sqrt{34}$

• між другою та третьою вежею довжиною $\sqrt{37}$

• між другою та четвертою вежею довжиною $\sqrt{10}$

Вам потрібно вивести $34\ XOR\ 37\ XOR\ 10 = 13$.

Зауважте, що між першою та третьою вежею проводити кабель не можна, адже він перетнеться з другою вежею.