Một tựa game P giấu tên vừa ra mắt thời gian gần đây.Tựa game đã thu hút rất nhiều người chơi tham gia. Game được nhà phát hành giới thiệu với rất nhiều cơ chế và chế độ chơi thú vị, trong đó chế độ chơi có tên Vượt ải liên hoàn là chế độ chơi được nhiều người chơi đánh giá là điểm thú vị nhất của game.
Chế độ chơi Vượt ải liên hoàn có cơ chế chơi như sau:
- Chế độ chơi sẽ gồm ~N~ ~(1 \le N \le 10^5)~ màn chơi, với mỗi màn chơi thứ ~i~ sẽ có yêu cầu về kinh nghiệm của người chơi là ~a_i~ ~(1 \le a_i \le 10^9)~.
- Người chơi phải vượt ải liên tục qua các màn chơi, nếu thất bại ở màn chơi bất kì thì trò chơi sẽ kết thúc, người chơi sẽ được tổng kết kết quả và không được chơi những màn chơi sau.
- Khi vượt màn chơi thứ ~i~ , người chơi sẽ nhận tương ứng ~a_i~ kinh nghiệm và tất cả kinh nghiệm nhận được khi vượt qua các màn chơi sẽ được cộng vào kinh nghiệm của người chơi sau khi vượt qua tất cả các màn chơi mà người chơi có thể vượt qua.
Hiện tại đang có ~M~ ~(1 \le M \le 10^5)~ người chơi đang chơi chế độ này, với người chơi thứ ~j~ sẽ có lượng kinh nghiệm là ~b_j~ ~(1 \le b_i \le 10^9)~. Điều kiện tối thiểu để một người chơi thứ ~j~ có thể vượt qua màn chơi thứ ~i~ là lượng kinh nghiệm của người chơi thứ ~j~ phải nhiều hơn hoặc bằng lượng kinh nghiệm mà màn chơi thứ ~i~ yêu cầu ~(a_i \le b_j)~.
Yêu cầu: Với mỗi người chơi thứ ~j~, hãy tính lượng kinh nghiệm người chơi đó nhận được sau khi vượt qua tất cả các màn chơi mà người chơi đó có thể vượt qua.
Dữ liệu vào
- Dòng đầu tiên gồm ~2~ số nguyên dương ~N~ và ~M~ tương ứng với số lượng màn chơi và số lượng người chơi ~(1 \le N, M \le 10^5)~.
- Dòng thứ hai gồm ~N~ số nguyên không âm ~a_1, a_2, a_3, ..., a_N~ tương ứng với lượng kinh nghiệm mà màn chơi yêu cầu ~(0 \le a_i \le 10^9)~.
- Dòng thứ hai gồm ~M~ số nguyên không âm ~b_1, b_2, b_3, ..., b_M~ tương ứng với lượng kinh nghiệm người chơi đang có ~(0 \le b_j \le 10^9)~.
Dữ liệu ra
- Một dòng duy nhất gồm ~M~ số nguyên không âm ~k_1, k_2, k_3, ..., k_M~ với mỗi ~k_j~ tương ứng với lượng kinh nghiệm tối đa mà người chơi thứ ~j~ có thể nhận được.
Giới hạn
- Có ~70\%~ test ứng với ~N,M \le 10^4~.
- Có ~30\%~ test ứng với ~N,M \le 10^5~.
Ví dụ
Input
4 3
1 3 2 5
3 2 6
Output
6 1 11
Giải thích
- Người chơi đầu tiên có lượng kinh nghiệm là ~3~, màn chơi tối đa mà người chơi có thể vượt qua là màn thứ ~3~, lượng kinh nghiệm mà người chơi này có thể nhận được là ~1 + 3 + 2 = 6~.
- Người chơi thứ ~2~ có lượng kinh nghiệm là ~2~, màn chơi tối đa mà người chơi có thể vượt qua là màn thứ ~1~, lượng kinh nghiệm mà người chơi này có thể nhận được là ~1~.
- Người chơi thứ ~3~ có lượng kinh nghiệm là ~6~, người chơi có thể vượt qua tất cả các màn chơi, lượng kinh nghiệm mà người chơi này nhận được là ~1 + 3 + 2 + 6 = 11~.
Bình luận