Description
Elephants love to eat KuoTA (鍋貼), so Elfnt decided to open a restaurant called "八方來財", serving delicious KuoTA to satisfy their cravings.
On the grand opening day, many groups of elephants are lining up outside the restaurant. Each group consists $a_i$ elephants. To serve them efficiently and maximize profit, Elfnt follows a strategy:
- From time to time, Elfnt announces that a table with $x_j$ seats is available.
- When a table becomes available, the group with the largest number of elephants not exceeding $x_j$ gets to leave the line and enter the restaurant.
- If there are multiple groups with the same number of elephants, the one that is earliest in the queue gets chosen.
Each group can only enter the restaurant once, and each table can only seat one group.
Input
The first line contains two integers $n$ and $k$, representing the number of elephant groups and the number of tables that will become available.
The second line contains $n$ integers $a_1, a_2, ..., a_n$, where $a_i$ is the number of elephants in the $i$-th group (in queue order).
The third line contains $k$ integers $x_1, x_2, ..., x_k$, where $x_j$ is the number of seats of the $j$-th available table.
Constraints
- $1 \leq n, k \leq 2 \times 10^5$
- $1 \leq a_i, x_j \leq 10^9$
Subtask
- (Testcases 1-4) The number of elephants in each groups is distinct, i.e., $a_i \neq a_k \ \forall \ i \neq k$
- (Testcases 5-8) No additional constraints.
Output
Output a single line containing $n$ integers, each followed by a space (including the last one) and NO \n in the end.
The $i$-th number represents the order in which the $i$-th group enters the restaurant ($1$-based).
If a group never gets a seat, output $-1$ for that group.
Note
Visualizations for Sample 1 and Sample 2:
Sample1:
Sample2:
