Có ~n + 1~ ngọn núi, ngọn núi thứ ~i~ (~1 \le i \le n~) có độ cao ~h_i~. Có ~n~ con mèo đang sống, chú mèo ~i~ nằm ở ngọn núi ~i~, ngọn núi thứ ~n + 1~ có độ cao lớn nhất trong mọi hang (không có con mèo nào sống ở đó). Mỗi ngày những con mèo đều phải tập thể dục theo một quy luật cho trước, con mèo ~i~ sẽ thức hiện ~J_i~ lần nhảy, mỗi lần nhảy con mèo sẽ nhảy qua ngọn núi gần nhất cao hơn và có chỉ số lớn hơn chỉ số ngọn núi hiện tại nó đang đứng. Khi con mèo đã nhảy đến ngọn núi ~n + 1~ thì không thực hiện nhảy tiếp nữa.

Yêu cầu: Hãy xác định độ cao của ngọn núi mà mỗi con mèo sẽ đến sau khi tập thể dục xong (một ngon núi có thể chứa nhiều con mèo). Nếu vị trí mới của con mèo là ngọn núi ~n + 1~ thì ghi ~-1~.

Input:

• Dòng thứ nhất chứa số nguyên dương ~n~ (~1 \le n \le 10 ^ 6~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~h_1~, ~h_2~, …, ~h_n~ (~1 \le h_i \le 10 ^ 6~).
• Dòng thứ ba chứa ~n~ số nguyên dương ~J_1, J_2, … J_n~ (~1 \le J_i~ < ~10^6~).

Output:

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

Sample Input:

5 
3 6 7 6 4 
2 1 1 3 2 

Sample Output:

7 7 -1 -1 -1

Giải thích:

• Mèo đầu tiên nhảy ~2~ lần từ ngọn núi ~1 \rightarrow 2 \rightarrow 3~.
• Mèo thứ hai nhảy ~1~ lần từ ~2 \rightarrow 3~.
• Mèo thứ ba nhảy ~1~ lần từ ~3 \rightarrow 6 (n + 1)~ nên in ra ~-1~.
• Mèo thứ tư nhảy ~1~ lần từ ~4 \rightarrow 6 (n + 1)~ nên in ra ~-1~.
• Mèo thứ năm nhảy ~1~ lần từ ~5 \rightarrow 6 (n + 1)~ nên in ra ~-1~.

Subtask:

• ~20\%~ số test có ~n \le 20~.
• ~20\%~ số test tiếp theo có ~J_i \le 10~
• ~60\%~ số test còn lại không có điều kiện gì thêm.