Arshu and Aman are two friends who love coding. Arshu is boasting about how he can solve questions based on segment trees in no time. Aman decides to teach him a lesson and gives him a problem. Aman gives him an array of N numbers. Arshu has to fulfil M. operations.
Each operation has one of the following two types:

U X Y : Update the value at the Xth index of the array with Y. Q X C : Calculate the length of the longest subarray that starts at Xth index and satisfy following inequality A[X]-C = V =A[X] + C Where V is any value from the chosen subarray.

Arshu is having a hard time solving the problem and he doesn't want to lose to Aman. Naturally, he turns to his other coding friend which happens to be you.Help Arshu for this challenge.

 

 

Input

 

• The first line of the input contains two integers N and M as descibed above.
• Next line contains N space separated integers denoting elements of the array.
• Each of the next M lines contain one operation as descibed above.

 

Output

 

• For each query operation,you need to print following two values.
  V1 : Length of the longest subarray that starts at Xth index and satisfy mentioned inequality. V2 : Minimum value Z such that following inequality holds A[X] - Z = V = A[X] + Z Where V is any value from the chosen subarray . If in case there does not exist any such subarray then print -1 -1 to the output .

 

Constraints

 

• 1 = N,M = 2*10⁵
• 1 = X = N
• 1 = Y = 10⁹
• -10⁹ = C = 10⁹

 

Example

Input: 5 5 1 2 3 4 5 Q 1 3 U 2 6 Q 1 3 Q 1 -1 Q 1 6 Output: 4 3 1 0 -1 -1 5 5