The sequence \textbf{a_n} is given with the formula: \textbf{a_n} = \textbf{n^2} \textbf{mod 12345} + \textbf{n^3 mod 23456}. You need to answer the next queries a lot of times: \begin{itemize} \item find the difference between the maximum and the minimum element among the values \textbf{a_i}, \textbf{a_\{i+1\}}, ..., \textbf{a_j}; \item assign to the element \textbf{a_i} the value of \textbf{j}. \end{itemize} \InputFile The first line contains the number of queries \textbf{k} (\textbf{k} ≤ \textbf{100 000}). Each of the next \textbf{k} lines contains one query. The \textbf{i}-th query contains the numbers \textbf{x_i}, \textbf{y_i}. If \textbf{x_i} > \textbf{0}, find the difference between the maximum and the minimum element among the values of \textbf{a_xi}...\textbf{a_yi}. It is known that \textbf{1} ≤ \textbf{x_i} ≤ \textbf{y_i} ≤ \textbf{100 000}. If \textbf{x_i} < \textbf{0}, assign to the element \textbf{a_\{-xi\}} the value of \textbf{y_i}. It is known that \textbf{-100 000} ≤ \textbf{x_i} ≤ \textbf{-1} and |\textbf{y_i}| ≤ \textbf{100 000}. \OutputFile For each query of the first type print in a separate line the difference between the maximum and the minimum element on a given segment.