From a young age, the boy Misha was worried about the issues of water delivery. When Misha was four years old, he brought water for watering plants in balloons instead of buckets, since it was easier to splash water in a bucket. When Misha was six years old, he built a water pipe in the apartment from juice tubes, thereby automating the watering of flowers in his room. Misha immediately used all the knowledge gained at school in his bold inventions: transferring water through wires, a toothpick pump, a tap from his mother's bottle of perfume — here is a far from complete list of the boy's inventions during his school years.
As you know, any talent should be given the opportunity to be realized, so Misha's mother sent her son to the Innovative Irrigation Olympiad (IOI). At this Olympiad, schoolchildren from all over Berland compete in the ability to deliver water for watering plants in the most bizarre ways. Knowing the list of Misha's inventions, it is easy to guess that holding such an Olympiad is very expensive, so after the first n Olympiad, it was decided to introduce a rule that would determine the venue for the next year's competition. The city for holding the Olympiad is chosen as follows: there are m cities in Berland, numbered from 1 to m, ready to host the competition. Each year the Olympiad is held in the city where it has been held the least number of times. If there are several such cities, then the Olympiad is held in the city with the smallest number among the cities with the minimum number of Olympiad events.
Misha's mother is very worried about her son, so she is interested in which city the Olympiad will be held in certain years. The only information that Misha's mom has is — venues of the Olympiad in the first n years. Help Misha's mom and she will ask Misha not to flood your apartment.
Input
The first line contains three integers n, m and q (1 ≤ n, m ≤ 500000 , 1 ≤ q ≤ 20) — the number of hosting the Olympiad before the introduction of the rule, the number of cities in Berland ready to host the Olympiad, and the number of years about which Misha's mother is interested in the venue of the Olympiad, respectively.
The next line contains n integers a
i (1 ≤ a
i ≤ m) — numbers of cities where the Olympiad was held in year i. Please note that before the adoption of the rule, the venue for the Olympiad could be chosen arbitrarily.
The next q lines contain integers k
i (n+1 ≤ k
i ≤ 10
18) — numbers of years for which Misha's mother is interested in the venue of the Olympiad.
Imprint
Print q integers. In the line with number i print a single integer — venue of the Olympiad in the year k
i.
Examples
| # |
Input |
Output |
| 1 |
6 4 10
3 1 1 1 2 2
7
8
9
10
11
12
13
14
15
16 |
4
3
4
2
3
4
1
2
3
4 |
| 2 |
4 5 4
4 4 5 1
15
9
13
6 |
5
3
3
3 |