You are given an array of integers. Your task is to implement the following two functions:

• multiplicationEqualsK: Use the Two Pointers algorithm to find two numbers in the array whose product is equal to a given integer ~k~. If such a pair exists, output the two numbers. If no such pair exists, output -1. If there are more than one pair, output the pair of two elements with maximum difference.
• sumFromLToR: Use the Prefix Sum algorithm to calculate the sum of elements from index ~L~ to index ~R~, inclusive.
• containSquareEqualsK: Use the Binary Search algorithm to check if there is an element in the array whose square is equal to ~k~. If such a number exists, output ~Yes~. If no such number exists, output ~No~.
• countMinSumSubarray: Use the Sliding Window algorithm to count how many subarrays of length ~w~ have the minimum sum among all subarrays of length ~w~.
• sumOfSquaresEqualsK: Use the Two Pointers algorithm to find two numbers in the array such that the sum of their squares is equal to ~k~. If there are more than one pairs, output the pair of two elements with maximum difference. If such a pair exists, output the two numbers. If no such pair exists, output -1.
• countMaxSumSubarray: Use the Sliding Window algorithm to count how many subarrays of length ~w~ whose sum is maximum. Notes: If you use any the built-in library (except Arrays.sort), or other algorithms, this question will be marked 0.

Input

The first line contains two positive integers ~n~ (1 ≤ ~n~ ≤ 2 × ~10^{5}~) and ~q~ (1 ≤ ~q~ ≤ ~10^{3}~), representing the number of elements in the array and the number of queries.

The second line contains ~n~ positive integers a1, a2, ..., an (0 ≤ ai ≤ ~10^{9}~).

Each of next ~q~ lines, the input can be in one of the following formats:

• multiplicationEqualsK k
• sumFromLToR L R
• containSquareEqualsK k
• countMinSumSubarray w
• sumOfSquaresEqualsK k
• countMaxSumSubarray w

(0 ≤ ~k~ ≤ ~10^{18}~, 0 ≤ ~L~ ≤ ~R~ < ~n~, 1 ≤ ~w~ ≤ ~n~)

Output

For each query, print the result on a separate line.

• For "multiplicationEqualsK", print the two integers representing a pair of numbers in the array whose product is equal to ~k~. If no valid pair exists, print ~-1 -1~. If there are more than one pair, output the pair with maximum difference.
• For "sumFromLToR", print one integer representing the sum of elements from index ~L~ to index ~R~, inclusive.
• For "containSquareEqualsK", print ~Yes~ if the array exists index i such that ~a[i]^{2}~ = ~k~. If no valid index exists, print ~No~.
• For "countMinSumSubarray", print one integer representing the number of contiguous subarrays of length ~w~ that have the minimum sum.
• For "sumOfSquaresEqualsK", print two integers representing a pair of numbers in the array such that the sum of their squares is equal to ~k~. If no valid pair exists, print ~-1 -1~
• For "countMaxSumSubarray", print one integer representing the number of contiguous subarrays of length ~w~ whose sum is maximum.

Example

Input

7 8
1 4 2 3 4 3 6
sumFromLToR 1 2
containSquareEqualsK 8
sumOfSquareEqualsK 5
multiplicationEqualsK 15
countMinSumSubarray 1
countMaxSumSubarray 2
containSquareEqualsK 15

Output

6
Yes
1 2
-1 -1
1
1
-1