Phân phòng khách sạn (Hotel Queries)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $n$ khách sạn trên một con phố, đánh số từ $1$ đến $n$. Khách sạn $i$ hiện còn $h_i$ phòng trống. Có $m$ đoàn khách đến lần lượt. Đoàn thứ $j$ cần $r_j$ phòng và toàn bộ thành viên phải ở cùng một khách sạn.

Với mỗi đoàn, hãy chọn khách sạn có chỉ số nhỏ nhất còn ít nhất $r_j$ phòng. Sau khi xếp đoàn vào khách sạn đó, số phòng trống của khách sạn giảm đi $r_j$. Nếu không có khách sạn phù hợp, đoàn không được xếp phòng.

Input

Dòng đầu chứa hai số nguyên $n,m$.

Dòng thứ hai chứa $n$ số nguyên $h_1,h_2,\ldots,h_n$.

Dòng thứ ba chứa $m$ số nguyên $r_1,r_2,\ldots,r_m$.

Output

In $m$ số. Số thứ $j$ là chỉ số khách sạn được chọn cho đoàn thứ $j$, hoặc $0$ nếu không thể xếp đoàn.

Subtask

• 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$.

Ví dụ

Input

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

Output

3 5 0 1 1

Giải thích

Đoàn cần $4$ phòng được xếp vào khách sạn $3$ trước, rồi đoàn tiếp theo vào khách sạn $5$. Đoàn cần $7$ phòng không có nơi phù hợp nên nhận $0$.