There is a flock of hungry pigeons in Michael's backyard! Fortunately, it has started raining. Every minute, for the next
minutes, one earthworm will surface from his backyard.
The -th pigeon
has a beak size of
. Additionally, the
-th worm
will have a diameter of
. A pigeon can eat a worm if and only if the pigeon's beak size is strictly larger than the worm's diameter.
A pigeon's satisfaction is defined as the number of worms that the pigeon has eaten, and the flock's satisfaction is defined to be the minimum satisfaction among all pigeons in the flock. The hungry pigeons want to know: for all , what is the maximum possible satisfaction of the flock right after the
-th minute?
Constraints
For all subtasks:
for all
for all
Subtask 1 [10%]
Subtask 2 [10%]
Subtask 3 [20%]
Subtask 4 [30%]
Subtask 5 [30%]
No additional constraints.
Input Specification
The first line of input will contain two space-separated integers and
.
The second line will contain space-separated integers
.
The third line will contain space-separated integers
.
Output Specification
For all , output the maximum satisfaction of the flock right after the
-th minute, separated by spaces.
Sample Input
3 7
6 3 10
4 8 3 2 1 10 7
Sample Output
0 0 0 1 1 1 2
Explanation of Sample Output
The first three worms are too large for the second pigeon to eat, so the second pigeon must have a satisfaction of . Thus, the first three answers are
.
Then, after the fourth minute, it is possible for all pigeons to have a satisfaction of (e.g. the pigeons of beak sizes
,
, and
can eat worms of diameter
,
, and
, respectively). Thus, the next answer is
.
After the fifth minute, it is possible for any individual pigeon to eat at least worms. However, there are not enough worms for all the pigeons to have a satisfaction of
at the same time, so the maximum possible satisfaction of the flow is still
. The same situation occurs after the sixth minute, since no pigeon is able to eat the worm of size
.
After the seventh minute, it is finally possible for the flock to have a satisfaction of .
Comments