Công ty Hạnh Phúc có \(n\) nhân viên, được đánh số từ 1 đến \(n\). Nhân viên số 1 là giám đốc công ty, người này không có cấp trên. Các nhân viên khác đều có một cấp trên trực tiếp, cấp trên trực tiếp của \(i\) là \(p_i\).

Người \(y\) được gọi là thuộc phòng ban của người \(x\) nếu tồn tại một dãy \(x = u_1, u_2, ..., uₖ = y\) sao cho \(u_i\) là cấp trên trực tiếp của \(u_i₊_1\) với mọi \(i = 1, 2, ...,k-1\).

Dữ liệu đảm bảo không có hai người \(x\), \(y\) nào khác nhau mà thỏa mãn \(x\) thuộc phòng ban của \(y\) và \(y\) thuộc phòng ban của \(x\). Tức là quan hệ trong công ty tạo thành một cấu trúc cây, với gốc là đỉnh 1 và các cạnh mô tả các quan hệ cấp trên trực tiếp; mỗi phòng ban là một cây con.

Hiện tại, việc trao đổi thông tin chỉ có thể xảy ra giữa một nhân viên với cấp trên trực tiếp của anh ta. Để có thể trao đổi thông tin rộng hơn, công ty cần nâng cấp bảo mật.

Đầu tiên, mỗi nhân viên được cấp một số nguyên không âm dùng để mã hoá thông tin. Số nguyên được cấp cho người thứ \(i\) là \(a_i\).

Khi hai người \(u\) và \(v\) muốn trao đổi thông tin với nhau, hệ thống sẽ thiết lập một kênh mã hoá dựa vào các số nguyên của những người cần thiết. Độ bảo mật của kênh này là XOR của tất cả các số nguyên \(aₓ\) trên đường đi đơn từ \(u\) đến \(v\) trên cây.

Ở đây, phép toán XOR là phép toán có ký hiệu là ^ trong ngôn ngữ C++.

Yêu cầu

Để bảo mật thông tin nội bộ, mỗi nhân viên đều muốn biết độ bảo mật cao nhất của các kênh truyền tin bên trong phòng ban của mình.

Với mỗi nhân viên \(x\), hãy tính độ bảo mật cao nhất của các kênh truyền tin bên trong phòng ban của \(x\); tức là tìm đường đi đơn bên trong cây con gốc \(x\) mà có XOR của các số trên đường đi đó là lớn nhất có thể và in ra giá trị XOR tìm được.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương \(n\) là số nhân viên trong công ty;
• Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1, a_2, ..., a_n\) là các số được cấp cho các nhân viên;
• Dòng thứ ba chứa \(n - 1\) số nguyên dương \(p_2, p_3, ..., p_n\) là cấp trên trực tiếp của các nhân viên.

Dữ liệu ra:

• Ghi \(n\) dòng, dòng thứ \(x\) là độ bảo mật cao nhất của các kênh truyền tin bên trong phòng ban của \(x\).

Input 1

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

Output 1

7
7
3
6
1
2
3
4

Giải thích:

• Phòng ban của 1: Kênh (1, 8) hoặc kênh (4, 5) hoặc kênh (8, 7).
• Phòng ban của 2: Kênh (4, 5).
• Phòng ban của 3: Kênh (3, 3) hoặc kênh (7, 7).
• Phòng ban của 4: Kênh (4, 8).
• Phòng ban của 5: Kênh (5, 5).
• Phòng ban của 6: Kênh (6, 6).
• Phòng ban của 7: Kênh (7, 7).
• Phòng ban của 8: Kênh (8, 8).

Ràng buộc:

• Trong tất cả các test: \(n \le 10^5\); \(a_i \le 10^9\).
• Có 12% số test với \(n \le 500\) và \(a_i < 32\).
• Có 16% số test với \(n \le 5000\).
• Có 20% số test với \(p_i = [i/2]\).
• Có 24% số test với \(a_i < 32\).
• Có 28% số test với ràng buộc gốc.