Back

D. Less Than Me?

Worth 5 point(s) - Runtime Limit: 3 seconds

Summary

Given an array of N integers and Q queries, Q (1 < Q < N < 106), determine how many array elements are less than and to the left of the value at each query index.
For example, if the array contains integers

________________________________
Index   | 0 1 2 3 4 5 6 7 8 9 10
Content | 3 5 2 8 6 9 11 1 7 6 3
________________________________

The query 4 will give the result 3 since the first four values in the array contain three values less than 6. The query 8 would give the result 5.
You may assume that elements in the array are randomly distributed although many duplicates may exist.

Input

The first line of input contains a single decimal integer P, (1 ≤ P ≤ 10000), which is the number of datasets that follow. Each dataset should be processed identically and independently.
Each dataset comprises three lines of text. The first line consists of two space-separated integers: N, the number of elements in the array, and Q, the number of queries. The second line contains N space separated integers representing the values in the Array. Each value is in \([−10^9, 10^9]\). Those values are randomly distributed. The third line contains Q space-separated integer queries, each one in \([1, N − 1]\).

1
11 2
3 5 2 8 6 9 11 1 7 6 3
4 8

Output

For each dataset output Q lines of text, each one giving the query number, starting at 1, then a space, and then the result of the query

1 3
2 5