Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

H. Sakurako's Test
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sakurako will soon take a test. The test can be described as an array of integers n and a task on it:

Given an integer x, Sakurako can perform the following operation any number of times:

  • Choose an integer i (1in) such that aix;
  • Change the value of ai to aix.

Using this operation any number of times, she must find the minimum possible median of the array a.

Sakurako knows the array but does not know the integer x. Someone let it slip that one of the q values of x will be in the next test, so Sakurako is asking you what the answer is for each such x.

The median of an array of length n is the element that stands in the middle of the sorted array (at the n+22-th position for even n, and at the n+12-th for odd)

Input

The first line contains one integer t (1t104)  — the number of test cases.

The first line of each test case contains two integers n and q (1n,q105)  — the number of elements in the array and the number of queries.

The second line of each test case contains n integers a1,a2,,an (1ain)  — the elements of the array.

The following q lines each contain one integer x (1xn).

It is guaranteed that the sum of n across all test cases does not exceed 105. The same guarantee applies to the sum of q across all test cases.

Output

For each test case, output q integers  — the answer for each query.

Example
Input
2
5 5
1 2 3 4 5
1
2
3
4
5
6 3
1 2 6 4 1 3
2
1
5
Output
0 1 1 1 2 
1 0 2