You have to complete two following functions:

• Function 1: Using the Binary Search algorithm to find the index of the integer V in the given sorted array (A[i-1] ≤ A[i]). All elements are distinct. If V does not exist in the array, output -1. If you use any the built-in library, you will be marked 0 for this question.
• Function 1: Using the Sliding Window algorithm to find the minimum sum of any contiguous subarray of length K. Notes: If you use other algorithms, this question will be marked 0.

Input

• The first line contains a string F – name of the functions (BinarySearch or SlidingWindow), an integer N representing the length of array A (1 ≤ 𝑵 ≤ 10^6) and an integer T – number of queries
• The second line contains N integers A[i] (|𝑨[𝒊]| ≤ 10^9, 0 ≤ 𝒊 < 𝑵).
• With each of the next T lines: If F is BinarySearch, each of the next T lines contains an integer V (V is the integer that need found in the array, |𝑽| ≤ 10^9). If F is SlidingWindow, each of the next T lines contains an integer K (K is the length of subarray, 1 ≤ 𝑲 ≤ 𝑵 ≤ 10^6)

  Output

Output as the following instructions:

• Binary Search: The index of integer V in array A. If V does not exist in the array, output -1.
• Sliding Window: The minimum possible sum.

Example 1

Input

SlidingWindow 9 4
2 2 2 2 2 2 2 2 0
4
2
1
3

Output

6
2
0
4

Example 2

Input

BinarySearch 10 4
0 1 2 3 4 5 6 7 8 9
1
2
8
10

Output

1
2
8
-1