Задача 6D. Range Variation Query ≡

Условие

В начальный момент времени последовательность a_n задана следующей формулой: a_n = n² mod 12345 + n³ mod 23456.

Требуется много раз отвечать на запросы следующего вида:

• Найти разность между максимальным и минимальным значениями среди элементов a_i, a_i + 1, …, a_j.
• Присвоить элементу a_i значение j.

Формат входного файла

Первая строка входного файла содержит натуральное число k — количество запросов (1 ≤ k ≤ 100 000).

Следующие k строк содержат запросы, по одному на строке. Запрос номер i описывается двумя целыми числами x_i, y_i.

Если x_i > 0, то требуется найти разность между максимальным и минимальным значениями среди элементов a_xi, …, a_yi. При этом 1 ≤ x_i ≤ y_i ≤ 100 000.

Если x_i < 0, то требуется присвоить элементу a_|xi| значение y_i.

В этом случае  − 100 000 ≤ x_i ≤  − 1 и |y_i| ≤ 100 000.

Формат выходного файла

Для каждого запроса первого типа в выходной файл требуется вывести одну строку, содержащую разность между максимальным и минимальным значениями на соответствующем отрезке.

Ограничения

Примеры тестов

7
1 3
2 4
-2 -100
1 5
8 9
-3 -101
2 3

34
68
250
234
1