eolymp
Problems

Range Variation Query

Range Variation Query

The sequence an is given with the formula: an = n2mod 12345 + n3 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 ai, ai+1, ..., aj;
  • assign to the element ai the value of j.

Input

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 xi, yi.

If xi > 0, find the difference between the maximum and the minimum element among the values of axi...ayi. It is known that 1xiyi100 000.

If xi < 0, assign to the element a-xi the value of yi. It is known that -100 000xi-1 and |yi| ≤ 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.

Time limit 1 second
Memory limit 122.17 MiB
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