Range Variation Query

The sequence a_n is given with the formula: a_n = n²mod 12345 + n³ mod 23456.

You need to answer the next queries a lot of times:

• find the difference between the maximum and the minimum element among the values a_i, a_i+1, ..., a_j;
• assign to the element a_i the value of j.

Input

The first line contains the number of queries k (k ≤ 100 000). Each of the next k lines contains one query. The i-th query contains the numbers x_i, y_i.

If x_i > 0, find the difference between the maximum and the minimum element among the values of a_xi...a_yi. It is known that 1 ≤ x_i ≤ y_i ≤ 100 000.

If x_i < 0, assign to the element a_-xi the value of y_i. It is known that -100 000 ≤ x_i ≤ -1 and |y_i| ≤ 100 000.

Output

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.