Background

就是二分查找

Description

给你一串不严格上升的数列，让你查找其中的数target，当输入的字符为A时，求小于等于target的最后一个数的下标（从0开始）；输入的字符为B时，输出大于等于target的第一个数的下标；当输入的字符为C时，输出小于target的最后一个数的下标；当输入的字符为D时，输出大于target的第一个数的下标。

Input

第一行输入数列长度n，查找次数m；n,m不大于1e6； 第二行输入n个数，代表不严格上升的子序列； 第三行输入target和一个大写字符（只有A，B，C，D）代表你需要进行的操作方式。

Output

共有m行，输出相应的下标（从0开始）

找不到输出-1

Samples

4 1

1 2 2 3

3 A

3

Limitation

1s, 1024KiB for each test case.