Каркас веж

Обмеження: 2 сек., 256 МіБ

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

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

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

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

Вхідні дані

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

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

Вихідні дані

Нехай \(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}\). Гарантується, що для всіх розв’язків, які мінімізують суму довжин кабелів, відповідне значення буде однаковим.

Обмеження

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

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

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 2 4 7 5 1 7 8	13

Примітки

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

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

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

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

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

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