Given an integer array A. You have to complete three following functions:

• Function 1: Using the Sliding Window algorithm to find the maximum sum of any contiguous subarray of length K.
• Function 2: Use the Two Pointers technique to find two elements in the array whose sum equals S and output them in ascending order.
• Function 3: Use the Prefix Sum technique to compute the sum of elements from index L to R (inclusive). Notes: If you use other algorithms, this question will be marked 0.

Input

The first line contains two integers N representing the length of array A (1 ≤ N ≤ 10^6) and F which is the number of functions.

The second line contains N integers A[i] (|𝑨[𝒊]| ≤ 10^9, 0 ≤ i < N).

Each of F functions has following information, which is suitable for each type of fucntions: name of function (SlidingWindow, TwoPointer, or PrefixSum) and some needed information related to the function.

• SlidingWindow K (K is the length of subarray, 1 ≤ K ≤ N ≤ 10^6)
• TwoPointer S (S is the standard sum, S ≤ 10^18)
• PrefixSum L R (0 ≤ L ≤ R < N)

  Output

Output as the following instructions:

• Sliding Window: The largest possible sum
• Two Pointer: Two elements in the array whose sum equals S and output them in ascending order. If there are no pair matches the condition, output -1 and -1. If more than one pair exist, output the pair with the minimum difference.
• Prefix Sum: For each range query, output a single integer representing the sum of elements in the subarray from index L to R (inclusive). Each result should be printed on a separate line, in the same order as the queries appear in the input.

Example

Input

7 3
-1 2 4 -1 6 -10 1
SlidingWindow 4
TwoPointer 10
PrefixSum 2 4

Output

11
4 6
9