# 1104 : Tian Ji's Horse Race Again

Time Limit: 2 Sec Memory Limit: 128 Mb Submitted: 62 Solved: 14## Description

Last time, the king of the country Qi lost to Tian Ji in a horse race as Tian using a little trick. Today, the king invites Tian to play another horse race. The king and Tian both have *n* horses, and no two horses have the same speed. They will play *n* rounds in this match. The horses on each side must appear in descending order of speed, and each of the horses must be used in one round. The horse with a faster speed will win in a single round. Since Tian’s horses are not so nice as the king’s, the king allows Tian to exchange some horses with him.

If Tian can exchange at most *k* horses with the king, what is the maximum number of rounds that Tian can win?

## Input

There will be at most 200 test cases. Each case begins with two integers *n*, *m*(1 ≤ *m* ≤ *n* ≤ 10^{5}), the number of horses on each side and the number of queries. The next line contains *n* positive integers, denoting the speeds of **king**’s horses in descending order. Then the following line contains *n* positive integers, denoting the speeds of **Tian**’s horses in descending order. The speed of each horse will not exceed 10^{6}, and no two horses have the same speed. The queries are defined by the following *m* lines, and each line contains one integer *k*(0 ≤ *k* < *n*). The size of the whole input file does not exceed 10MB.

## Output

For each query, print the maximum number of rounds that Tian can win, when he can exchange at most *k* horses with the king.

## Sample Input

4 3 8 7 6 4 5 3 2 1 0 2 1 3 1 7 3 2 8 6 5 0

## Sample Output

0 4 2 3

## Hint

## Author

Staginner