You are given an integer array ~A~ with ~N~ elements.

There are ~T~ independent instructions.
Each instruction asks for a specific operation on the array, and the result must be printed immediately.

Your task is to process all instructions efficiently.

Input

• Line 1: Two integers ~N~ and ~T~

  • ~N~: number of elements in the array
  • ~T~: number of instructions
  • ~1 ≤ N, T ≤ 2·10^{5}~

• Line 2: ~N~ integers
  ~A_0, A_1, ..., A_{N-1}~ ~(0 ≤ A_i ≤ 10^{5})~

• Next ~T~ lines: each line contains one instruction in one of the following forms:

  • sumsub i j
    → Sum of elements from ~A_i~ to ~A_j~ (inclusive)

  • maxleft i
    → Maximum value in ~A_0~ to ~A_{i-1}~
    → If ~i = 0~, output -1

  • minright i
    → Minimum value in ~A_{i+1}~ to ~A_{N-1}~
    → If ~i = N-1~, output -1

  • sumof k
    → Two values whose sum equals ~k~
    → If none exists, output -1 -1

  • maxk l
    → Maximum subarray sum with length exactly ~l~
    → If ~l > N~, output -1

  • mink l
    → Minimum subarray sum with length exactly ~l~
    → If ~l > N~, output -1

  • countk k
    → Number of subarrays with sum equal to ~k~
    → If none exists, output -1

Output

Print ~T~ lines.
Each line contains the answer for the corresponding instruction.

📌 Example

Input

7 4
5 1 3 2 4 6 1
sumsub 1 4
maxleft 3
sumof 7
maxk 3

Output

10
5
3 4
11

💡 Explanation

Each instruction corresponds to a classic array operation.
Efficient algorithms are required due to the large constraints.