Problem G
Candies
It’s Rabbit’s birthday! He invited $m$ guests. To ensure that the guests do not feel sad or bored, Rabbit bought $n$ boxes of candies. Rabbit loves variety, so the candies were different. The $i$-th box contained $a_i$ candies.
On the designated day, guests started arriving at Rabbit’s house early in the morning. Each guest is characterized by their shyness $b_i$. This means that upon entering Rabbit’s home and seeing the boxes of candies, they would take one candy from each box that contains at least $b_i$ candies. For example, Winnie-the-Pooh as the impudent one (with minimal shyness) would take one candy from each box which had at least one candy.
In the evening, after the guests had left, Rabbit became curious about how many candies each guest had eaten. Help him determine this.
Input
The first line contains an integer $n$ ($1 \leq n \leq 100{\, }000$) — the number of boxes of candies. The next line contains $n$ integers $a_i$ ($1\leq a_i \leq 10^9$) — the number of candies in each box.
Next, the following line contains an integer $m$ ($1\leq m \leq 100{\, }000$) — the number of guests. The fourth line contains $m$ integers $b_i$ ($1 \leq b_i \leq 10^9$) — the shyness of the guests.
Output
Output should contain $n$ lines, where the $i$-th line should contain the number of candies eaten by the $i$-th guest.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 3 1 1 2 1 1 |
3 1 |