Một công ty Startup Tin học được thành lập và có \(n+2\) nhân viên được phân thành \(n+2\) cấp bậc từ thấp đến cao đánh số lần lượt \(0, 1, 2, \ldots, n+1\). Nhân viên cấp \(0\) là nhân viên thường và có mức lương thấp nhất, nhân viên cấp \(n+1\) là CEO và có mức lương cao nhất; các nhân viên cấp \(1, 2, \ldots, n\) sẽ có mức lương là \(s_1,s_2,\ldots,s_n\). Một điều ngạc nhiên là với \(i>j\) thì không nhất thiết \(s_i>s_j\).

Sau một năm làm việc, tiểu ban khen thưởng của công ty quyết định thực hiện \(p_i\) lần tăng cấp liên tiếp cho nhân viên thứ \(i\) \((i=1,2,\ldots,n)\). Tiểu ban kỷ luật thực hiện \(q_i\) lần giảm cấp liên tiếp cho nhân viên \(i\).

Việc tăng lương một lần cho nhân viên \(i\) được thực hiện bằng cách tăng lên cấp \(k>i\) nhỏ nhất mà \(s_k>s_i\); Nếu nhân viên \(i\) được tăng cấp \(p_i\) lần thì quá trình trên lặp lại \(p_i\) lần, tuy nhiên chỉ được tăng đến cấp tối đa \(n+1\).

Việc giảm cấp một lần cho nhân viên \(i\) được thực hiện bằng cách giảm xuống cấp \(k<i\) lớn nhất mà \(s_k<s_i\); Nếu nhân viên \(i\) bị giảm cấp \(q_i\) lần thì quá trình trên được thực hiện \(q_i\) lần, tuy nhiên chỉ được giảm đến cấp tối thiểu là \(0\).

Có hai khả năng là tiểu ban khen thưởng làm việc trước rồi mới đến tiểu ban kỷ luật hoặc ngược lại.

Mỗi nhân viên có cấp \(1,2,\ldots,n\) đều mong muốn rằng lương của mình sang năm mới là lớn nhất có thể sau khi xử lý. Hỏi rằng với nhân viên cấp \(i\) thì trong trường hợp lý tưởng đó, anh (cô) ta có cấp bậc bao nhiêu?

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1 \leq n \leq 5 \times 10^5)\)
• Dòng thứ hai chứa \(n\) số nguyên \(s_1,s_2,\ldots,s_n\) \((0 \leq s_i \leq 10^9)\)
• Dòng thứ ba chứa \(n\) số nguyên \(p_1,p_2,\ldots,p_n\) \((0 <p_i \leq 10^9)\)
• Dòng thứ tư chứa \(n\) số nguyên \(q_1,q_2,\ldots,q_n\) \((0 <q_i \leq 10^9)\)

Output

• Một dòng chứa \(n\) số nguyên, số nguyên thứ \(i\) là cấp bậc mới của nhân viên có cấp bậc cũ là \(i\) theo phương án mà \(i\) mong muốn.

Example

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

8 11 4 3 11 4 11 1 11 11