Card Game

Interview

Time limit1.2sMemory limit512 MB

Summary
Minsu holds M distinct blue cards and must answer each of K plays by discarding the smallest blue card larger than Cheolsu's card, or answering 0 when none exists.
Level

Medium6 of 10

Topics
Binary search, Greedy, Sorting, Array
Solved
No attempts yet

Problem

Cheolsu and Minsu enjoy a card game. The rules of this card game are as follows.

  1. There are N red cards. The cards are numbered 1 through N in order. Choose M of these cards.
  2. There are N blue cards. The cards are numbered 1 through N in order. Among the blue cards with the same numbers as those chosen from the red cards, choose M of them.
  3. Cheolsu holds the red cards, and Minsu holds the blue cards.
  4. Cheolsu and Minsu each play one of their chosen cards face down. Then they turn the cards over, and whoever has the larger number wins. They do this K times, and whoever wins more times wins overall. A card that has been played must be discarded.

Cheolsu is an excellent magician, so he can manipulate the card he will play however he likes. That is, he may discard a card and secretly bring it back without Minsu knowing, or play a card Minsu does not have.

Minsu is an excellent psychologist, so he can figure out which card Cheolsu will play. Therefore, if Minsu has a card larger than the card Cheolsu plays, he decided to play the smallest among those cards.

The cards Cheolsu plays over the K turns are given as input. Output which cards Minsu plays. Assume that Minsu never fails to play a card.

Input

The first line gives three natural numbers N, M, K. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000))

The next line gives M natural numbers representing card numbers. Each is at least 1 and at most N, and they are all distinct.

The next line gives K natural numbers. The i-th number is the number of the card Cheolsu plays on his i-th turn. The cards Cheolsu plays are also between 1 and N.

Output

Output numbers over K lines. The i-th line must contain the number of the card Minsu plays on his i-th turn.

Examples1

  1. Example 1

    Input
    10 7 5
2 5 3 7 8 4 9
4 1 1 3 8
    Expected output
    5
2
3
4
9