ACM-ICPC INC 2008 - Practice Session

Problem C

Math for a Birthday Present Again

Time Limit: 1s
Last year Jane received a box full of balls from his father on her 2nd birthday. Each balls was uniquely labeled from 0 to 9 and they used the balls to play a game. First, John took N balls from the box and gave them to his daughter. Next, he would ask one of these two request:

"Give me the ball with the lowest number from what you have now" (let's call it the lowest-query)
"Give me the ball with the highest number from what you have now" (let's call it the highest-query)

For each ball he received from his daughter, he put it back into the box, and then he continued his requests until there was no more ball left on Jane.

Write a program to simulate in what order did the balls will be put back into the box. Let's make the problem more interesting. Instead of 10 balls, we want your program able to handle up to 50,000 balls (uniquely labeled from 0 to 49,999).

Input

The first line of input contains an integer T, the number of test cases follow.

Each test case begins with two integer N and K (1 <= K <= N <= 50,000), the number of ball that Jane have at the beginning and the number of request respectively. The second line contains N integers A1..n, (0 <= Ai <= 49,999), denoting the label for each ball. The third line contains K integers, 0 or 1, represents the order of request made by John. 0 (zero) denotes the lowest-query and 1 (one) denotes the highest-query.

Output

For each case, output the sequence of balls that Jane will give to her father according to the request order. Each number in the sequence should be separated by a single space.

Sample Input	Output for Sample Input
2 5 4 2 9 1 3 7 0 1 0 1 8 6 2 1 3 5 9 7 0 6 0 0 1 0 1 1	1 9 2 7 0 1 9 2 7 6

Source: BNPC-HS 2007 Qualification Round
Modified for INC 2008 - Practice Session