eolymp
bolt
Try our new interface for solving problems
Problems

Range Variation Query

Range Variation Query

Time limit 1 second
Memory limit 122 MiB

The sequence a_n is given with the formula: a_n = n^2mod 12345 + n^3 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 data

The first line contains the number of queries k (k100 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 1x_iy_i100 000.

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

Output data

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.

Examples

Input example #1
7
1 3
2 4
-2 -100
1 5
8 9
-3 -101
2 3
Output example #1
34
68
250
234
1
Author В.Гольдштейн
Source Зимние сборы в Харькове 2010 День 2