Məsələlər
Range Variation Query
Range Variation Query
Последовательность \textbf{a_n} задается следующей формулой: \textbf{a_n} = \textbf{n^2} \textbf{mod 12345} + \textbf{n^3 mod 23456}.
Требуется много раз отвечать на запросы следующего вида:
\begin{itemize}
\item найти разность между максимальным и минимальным значением среди элементов \textbf{a_i}, \textbf{a_\{i+1\}}, ..., \textbf{a_j};
\item присвоить элементу \textbf{a_i} значение \textbf{j}.
\end{itemize}
\InputFile
Первая строка содержит натуральное число \textbf{k} (\textbf{k} ≤ \textbf{100 000}) - количество запросов. Следующие \textbf{k} строк содержат запросы, по одному в строке. Запрос номер \textbf{i} описывается двумя целыми числами \textbf{x_i}, \textbf{y_i}.
Если \textbf{x_i} > \textbf{0}, то требуется найти разность между максимальным и минимальным значением среди элементов \textbf{a_xi}...\textbf{a_yi}. При этом \textbf{1} ≤ \textbf{x_i} ≤ \textbf{y_i} ≤ \textbf{100 000}.
Если \textbf{x_i} < \textbf{0}, то требуется присвоить элементу \textbf{a_\{-xi\}} значение \textbf{y_i}. При этом \textbf{-100 000} ≤ \textbf{x_i} ≤ \textbf{-1} и |\textbf{y_i}| ≤ \textbf{100 000}.
\OutputFile
Для каждого запроса первого типа требуется вывести в отдельной строке разность между максимальным и минимальным значением на соответствующем отрезке.
Giriş verilənləri #1
7 1 3 2 4 -2 -100 1 5 8 9 -3 -101 2 3
Çıxış verilənləri #1
34 68 250 234 1