BBIN - Busqueda Binaria

Given an array of N non-decreasingly ordered integers, Q queries will be performed, each consisting of an integer. Use binary search to return the index of the first occurrence of the requested integer in the array.

Input

In the first line you will receive an integer N (1 <= N <= 10^5) and an integer Q (1 <= Q <= 10^5).

In the second line there are N integers separated by spaces, each integer takes a value between 1 and 10^9.

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

Output

For each query (in the order in which they were received) print a line consisting of an integer, the index of the first occurrence of the queried element, or -1 if not present in the array.

Example

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

Output:
1
3
-1
0

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

hide comments
2017-12-17 23:02:16
Simple Binary Search Problem

Last edit: 2017-12-17 23:14:16
2017-02-19 06:59:46
just a slight variation in the implementation of binary search and you are done



Last edit: 2017-02-19 07:00:17
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.