Cho mảng số nguyên ~A ~ gồm ~N ~ phần tử, các phần tử đôi một phân biệt. Bạn cần thực hiện lần lượt ~Q~ lệnh, mỗi lệnh thuộc một trong bốn loại thuật toán sau:

• BinarySearch: Tìm kiếm nhị phân trên mảng đã sắp xếp.
• SlidingWindow: Cửa sổ trượt trên mảng ban đầu.
• PrefixSum: Tổng tiền tố (mảng cộng dồn) trên mảng ban đầu.
• TwoPointer: Hai con trỏ trên mảng đã sắp xếp.
• Nếu bạn dùng bất kỳ các thuật toán nào khác, kết quả của bạn sẽ được tính 0 điểm.

Input

• Dòng ~~1: Số nguyên dương ~N~ ~(1 \le N \le 10^5)~.
• Dòng ~2~: ~N ~ số nguyên phân biệt ~A_0, A_1, \dots, A_{N-1}~ ~(|A_i| \le 10^9)~.
• Dòng ~3~: Số nguyên dương ~Q ~ ~(1 \le Q \le 10^5)~.

• ~Q~ dòng tiếp theo: Mỗi dòng mô tả một lệnh, có dạng:

  • BinarySearch X

    • Tìm chỉ số của ~X ~ trong mảng ~A ~ đã được sắp xếp tăng dần (bản sao).
    • Vì các phần tử phân biệt nên nếu tồn tại thì chỉ số là duy nhất. Nếu không tìm thấy, in ra -1.

  • SlidingWindow K

    • Tìm tổng nhỏ nhất của một dãy con liên tiếp có độ dài đúng ~K ~ trong mảng ~A ~ ban đầu.

  • PrefixSum L R

    • Tính tổng các phần tử từ chỉ số ~L~ đến ~R~ ~(0 \le L \le R < N)~ trong mảng ~A ~ ban đầu.

  • TwoPointer S

    • Đếm số cặp chỉ số ~i < j~ sao cho ~A_i + A_j = S~ trong mảng ~A~.

Output

• Với mỗi lệnh trong ~Q~ dòng, in ra một số nguyên là kết quả tương ứng, mỗi kết quả trên một dòng.

Example Input

6
5 3 8 1 2 6
6
BinarySearch 5
SlidingWindow 3
PrefixSum 1 4
TwoPointer 7
BinarySearch 10
SlidingWindow 2

Example Output

3
9
14
2
-1
3