Hotel Queries

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

There are $n$ hotels numbered from $1$ to $n$. Hotel $i$ currently has $h_i$ free rooms. There are $m$ groups arriving in order, and group $j$ requires $r_j$ rooms in one hotel.

For each group, choose the smallest hotel index whose number of free rooms is at least $r_j$. Then decrease that hotel's free-room count by $r_j$. If no hotel can accommodate the group, it is not assigned.

Input

The first line contains $n,m$.

The second line contains $h_1,h_2,\ldots,h_n$.

The third line contains $r_1,r_2,\ldots,r_m$.

Output

Print $m$ integers. The $j$-th integer is the selected hotel index, or $0$ if the group cannot be assigned.

Subtasks

• Subtask 1 — 20%: $1\le n,m\le 50$.
• Subtask 2 — 30%: $1\le n,m\le 5000$.
• Subtask 3 — 50%: $1\le n,m\le 2\cdot 10^5$, $1\le h_i,r_i\le 10^9$.

Examples

Input

8 5
3 2 4 1 5 5 2 6
4 4 7 1 1

Output

3 5 0 1 1

Explanation

The sample is processed in order; every printed item/line corresponds to an operation that requires output.