BBIN2 - Búsqueda Binaria 2


Given an array of N integers in non-decreasing order, you're going to receive Q queries. Each of them contains a single integer. For each query use binary search to respond with the index of the last occurence of the given integer in the array.

Input

In the first line there is an integer N (1 <= N <= 10^5) and an integer Q (1 <= Q <= 10^5).

In the second line, N integers separated by a single space. Each integer takes a values between 1 and 10^9.

Then Q lines follows, each one with an integer between 1 and 10^9, representing a query.

Output

For each query (in the same order they were given) print a line with a single integer, the index of the last occurence of the corresponding element, or -1 if it is not in the given array.

Example

Input:
10 4
1 3 4 5 5 6 7 8 8 17
9
1
Output:
1
4
-1
0


Added by:BerSub
Date:2016-09-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU