Послідовність $a_n$ задано наступною формулою: $a_n$ = $n^2$ mod 12345 + $n^3$ mod 23456.

Потрібно багато разів відповісти на запити наступного виду:

знайти різницю між максимальним та мінімальним значенням серед елементів $a_i$, $a_{i+1}$, ..., $a_j$;

присвоїти елементу $a_i$ значення $j$.

Вхідні дані

Перший рядок містить натуральне число $k$ ($k$ ≤ $100 000$) - кількість запитів. Наступні k рядків містять запити, по одному в рядку. Запит номер $i$ описується двома цілыми числами $x_i$, $y_i$.

Якщо $x_i$ > $0$, то потрібно знайти різницю між максимальним і мінімальним значенням серед елементів $a_{x_i}$...$a_{y_i}$. При цьому 1 ≤ $x_i$ ≤ $y_i$ ≤ 100 000.

Якщо $x_i$ < 0, то потрібно присвоїти елементу $a_{-xi}$ значення $y_i$. При цьому -100 000 ≤ $x_i$ ≤ -1 та | $y_i$ | ≤ 100 000.

Вихідні дані

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