Trong tiết khoa học máy tính hôm nay, Tí đã học về cây tìm kiếm nhị phân. Cây tìm kiếm nhị phân là một cấu trúc dữ liệu rất thuận lợi cho bài toán tìm kiếm. Một cây tìm kiếm nhị phân gồm các giá trị \(w_{u}\) phân biệt có tính chất sau:

• Mỗi đỉnh có tối đa hai đỉnh con (trái và phải).
• Với mỗi đỉnh \(u\), các đỉnh \(v\) ở cây con bên trái đều có giá trị nhỏ hơn \(u\) (\(w_{u} > w_{v}\)).
• Với mỗi đỉnh \(u\), các đỉnh \(v\) ở cây con bên phải đều có giá trị lớn hơn \(u\) (\(w_{u} < w_{v}\)).

Nhận thấy đây là một cấu trúc dữ liệu thú vị và mới mẻ, Tí đã nghĩ ra một bài toán sau: Xét một cây nhị phân tìm kiếm gồm \(n\) đỉnh được đánh số từ \(1\) đến \(n\), đỉnh \(u\) có trọng số \(c_u\) và giá trị \(w_{u}\). Tại mỗi đỉnh \(u\), với đỉnh \(v\) (khác \(u\)) là đỉnh thuộc cây con gốc \(u\), đặt \(s_{u} = c_{u} + \sum w_{v}\). Hãy tìm cây nhị phân tìm kiếm có \(\max(s_{1}, s_{2}, \ldots, s_{n})\) nhỏ nhất. Nếu có nhiều cây thỏa mãn, hãy tìm cây có thứ tự từ điển lớn nhất.

Cây \(A\) có thứ tự từ điển lớn hơn cây \(B\) nếu dãy tiền thứ tự của cây \(A\) có thứ tự từ điển lớn hơn cây \(B\).

Dãy tiền thứ tự của một cây có thể thu được bằng cách duyệt các đỉnh theo thứ tự như sau: duyệt đỉnh gốc đầu tiên, sau đó duyệt cây con bên trái và cuối cùng là cây con bên phải.

Dãy \(a\) có thứ tự từ điển lớn hơn dãy \(b\) nếu tồn tại vị trí \(i\) sao cho \(a_{j} = b_{j}\) với mọi \(1 \leq j < i\) và \(a_{i} > b_{i}\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq n \leq 10^{5}\)) là số lượng đỉnh của cây tìm kiếm nhị phân.
• Dòng tiếp theo chứa \(n\) số nguyên \(c_{1}, c_{2}, \ldots, c_{n}\) (\(1 \leq c_{i} \leq 10^{9}\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(w_{1}, w_{2}, \ldots, w_{n}\) (\(1 \leq w_{1} < w_{2} < \ldots < w_{n} \leq 10^{9}\)).

Output

• Dòng đầu tiên chứa một số nguyên là \(\max(s_{1}, s_{2}, \ldots, s_{n})\) trong cây tìm kiếm nhị phân tìm được.
• Dòng tiếp theo chứa \(n\) số nguyên là dãy tiền thứ tự của cây.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 4 \times 10^{2}\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 3 \times 10^{3}\).
• Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
4 3 2 1
1 2 3 4

7
4 3 2 1

6
27 10 44 32 15 41
2 3 4 5 6 7

44
5 4 2 1 3 6