AGPC01F - Can you search?

Shimlin loves to play with array. One day she was playing a game of finding the smallest number in an array but soon she got bored as the game was too easy for her. She asked her ghost friend to make the game more interesting. After thinking for a while the ghost came up with an idea. The ghost will give her some queries. In each query the ghost will tell her a number bi (less than the given array size) and Shimlin will have to answer the smallest number among first bi elements of the given array.

The ghost gave you the responsibility to find the correct answer of each query so that he can match the answer with Shimlin's answer.

Input

Input starts with T (1 ≤ T ≤ 100), denoting the number of test cases.

Each of the test cases contains 3 lines.

In the first line there are two positive integer numbers n and q (1 ≤ n ≤ 10^5, 1 ≤ q ≤ 10^5) — size of the array and number of queries.

The second line contains n integers a1, a2 ... an (1 ≤ ai ≤ 10^5) — elements of the array.

The third line contains q integers b1, b2 ... bq (1 ≤ bi ≤ n) — range of query.

Output

For each query print one integer in a line— the minimum number in that range.

Example

Input:
1
4 2
2 2 3 1
3 4

Output:
2
1

Added by:imranziad
Date:2017-04-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:AIUB Girls Programming Contest - Spring 2016-17

hide comments
2019-05-29 12:36:42
pistachio: thanks, there are empty lines indeed. Couldn't localize them, so I checked every input if empty.
2019-04-16 22:46:56
Warning! There are empty lines between test cases.
2019-01-13 22:46:44
I got TLE in java =<
help pls
2017-12-23 09:41:13
I am getting tle in python.Please provide me some suggestion


Last edit: 2017-12-23 16:13:29
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.