## 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

3

5

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 |