Có ~n + 1~ cây cột, đánh số bắt đầu từ ~1~ đến ~n + 1~ tính từ trái qua phải. Cây cột thứ ~i~ có độ cao ~h_i~ ~(i = 1..n,\ 0 < h_i \le 10^9,\ 0 < n \le 10^6,\ h_i \in \mathbb{Z})~, cây cột ~n + 1~ có độ cao lớn hơn mọi cây cột trước đó, ta ký hiệu độ cao này là ~-1~ (vì không cần biết chính xác).

Trên mỗi cây cột hiện có một con cào cào đang sống. Đến tuổi trưởng thành, mỗi con cào cào đều muốn đi tìm một chỗ sống tốt đẹp hơn bằng cách nhảy sang cây cột cao hơn gần nhất bên phải. Cào cào ở cây cột thứ ~i~ có thể thực hiện được ~x_i~ bước nhảy ~(0 < x_i < n)~.

Ví dụ: Có ~8~ cây cột với độ cao tương ứng từ trái sang phải là ~3, 1, 4, 5, 6, 2, 3~ và ~8~. Số bước nhảy mỗi cào cào có thể thực hiện là ~1, 2, 1, 3, 4, 2, 1, 2~. Sau khi di chuyển hết khả năng của mình, cào cào ở cây cột ~1~ sẽ tới được cây cột ~3~ với độ cao là ~4~, còn cào cào ở cây cột ~4~ tới được cây cột ~n + 1~ (độ cao ~-1~).

Yêu cầu

Hãy xác định độ cao nơi ở mới của mỗi con cào cào.

Dữ liệu đầu vào

Gồm ba dòng:

• Dòng thứ nhất chứa số nguyên ~n~.
• Dòng thứ hai chứa ~n~ số nguyên ~h_1, h_2, ..., h_n~.
• Dòng thứ ba chứa ~n~ số nguyên ~x_1, x_2, ..., x_n~.

Dữ liệu đầu ra

Gồm một dòng chứa ~n~ số nguyên là độ cao nơi ở mới của mỗi con cào cào.

Ràng buộc dữ liệu

• Có 50% số test ~n \le 10^4~;
• Có 50% số test còn lại ~n \le 10^6~.

Ví dụ

Ví dụ 1

INPUT

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

OUTPUT

4 5 5 -1 -1 8 8 -1