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.
• indexOfSquareEqualsK: Use the Binary Search algorithm to find the last position of a number in the given sorted array whose square is equal to k. If such a number exists, output its position. If no such number exists, output -1.
• countMinSumSubarray: Use the Sliding Window algorithm to count how many contiguous subarrays of length L have the minimum sum among all subarrays of length L.
• 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 contiguous subarrays of length L 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 one string f, representing the function that needs to be tested ("multiplicationEqualsK", "sumFromLToR", "indexOfSquareEqualsK", "countMinSumSubarray", "sumOfSquaresEqualsK" or "countMaxSumSubarray")

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

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

For the next q lines, the input format depends on the value of f.

• For "multiplicationEqualsK", each query contains one positive integer k (0 ≤ k ≤ ~10^{18}~).
• For "sumFromLToR", each query contains two integers L and R (0 ≤ L ≤ R < n).
• For "indexOfSquareEqualsK", each query contains one positive integer k (1 ≤ k ≤ ~10^{18}~).
• For "countMinSumSubarray", each query contains one positive integer L (1 ≤ L ≤ n).
• For "sumOfSquaresEqualsK", each query contains one positive integer k (1 ≤ k ≤ ~10^{18}~).
• For "countMaxSumSubarray", each query contains one positive integer L (1 ≤ L ≤ 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. 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 "indexOfSquareEqualsK", print one integer representing the last index i such that ~ai^{2}~ = k. If no valid index exists, print -1.
• For "countMinSumSubarray", print one integer representing the number of contiguous subarrays of length L 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
• For "countMaxSumSubarray", print one integer representing the number of contiguous subarrays of length L whose sum is maximum.

Example

Input 1

multiplicationEqualsK
5 3
1 2 4 3 6
12
8
10

Output 1

2 6
2 4
-1

Input 2

sumFromLToR
6 3
1 4 3 2 2 1
0 1
2 3
4 4

Output 2

5
5
2

Input 3

indexOfSquareEqualsK
5 3
1 3 3 4 6
9
16
25

Output 3

2
3
-1

Input 4

countMinSumSubarray
5 3
3 1 2 1 2
2
3
4

Output 4

3
1
1

Input 5

sumOfSquaresEqualsK
5 2
9 0 4 5 6
16
1

Output 5

0 4
-1

Input 6

countMaxSumSubarray
7 3
9 0 4 1 8 0 2
3
2
1

Output 6

2
2
1