Problem B
Concurrent Contests
Because of some scheduling issues, there are $m$ different programming contests scheduled on the same day, at the same time. There are $n$ people who would like to participate in these contests, but because all contests happen simultaneously, each participant can only compete in one contest. Everyone wants to choose the contest in which to participate such that their expected winnings are maximized.
Every contest has a single cash prize for the winner (no-one else gets a prize). Furthermore, every participant has a skill level, which determines their winning probability. If the sum of skill levels over all participants in a contest is $t$, then the winning probability in this contest of a participant with skill level $s$ is $\frac{s}{t}$.
Find a distribution of the participants over the contests, such that it is impossible for any person to switch to a different contest and increase their expected winnings. It is guaranteed that such a distribution exists.
Input
The input consists of:
-
One line with two integers $n$ and $m$ ($1\leq n\leq 2\cdot 10^5$, $1 \leq m \leq 100$), the number of contestants and the number of contests.
-
One line with $n$ integers $s$ ($1\leq s\leq 10^9$), the skill levels of the contestants.
-
One line with $m$ integers $p$ ($1 \leq p \leq 10^9$), the prizes for the winners of the contests.
The sum of all skill levels is at most $10^9$.
Output
For each contest, output the number of contestants that should participate in this contest, followed by the $1$-based indices of the contestants that should participate in this contest.
If there are multiple valid solutions, you may output any one of them.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 3 2 5 10 3 7 1 100 50 75 |
4 4 2 6 1 1 5 1 3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 2 9 10 8 10 100 |
0 3 2 3 1 |
