Bạn đang chơi trò chơi điện tử nổi tiếng Escape the BThouse. Như bạn có thể đã đoán, mục tiêu là thoát khỏi ngôi nhà.

Ngôi nhà bao gồm $n$ căn phòng, được đặt thành một hàng và đánh số từ $1$ đến $n$, cùng với $n+1$ cánh cửa giữa các căn phòng. Cánh cửa thứ $1$ là lối thoát nằm ở phòng $1$, tương tự cánh cửa thứ $n+1$ là lối thoát từ phòng $n$. Tất cả các cánh cửa khác $2 \le i \le n$ kết nối các phòng $(i-1, i)$. Mục tiêu của bạn là thoát khỏi ngôi nhà thông qua cánh cửa thứ $1$ hoặc thứ $n+1$.

Để mở cánh cửa thứ $i$, cần ít nhất $b_i$ điểm kinh nghiệm. Kinh nghiệm có thể đạt được bằng cách giải các nhiệm vụ trong các căn phòng, với nhiệm vụ trong phòng $i$ mang lại $a_i$ điểm kinh nghiệm. Về mặt hình thức, để giải một nhiệm vụ, chỉ cần bước vào phòng đó là đủ. Ngoài ra, trò chơi có tích hợp cơ chế kiếm tiền: tại bất kỳ thời điểm nào, bạn có thể mua một lượng kinh nghiệm tùy ý với giá $1$ đơn vị kinh nghiệm cho $1$ đồng xu trong trò chơi.

Bạn cần chọn phòng bắt đầu, nhân vật của bạn sẽ xuất hiện trong phòng đó với $0$ đơn vị kinh nghiệm. Với mỗi phòng, hãy tính số lượng đồng xu tối thiểu cần thiết để thoát khỏi ngôi nhà khi bắt đầu trò chơi tại phòng đó.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 10^6$).

Dòng thứ hai chứa $n$ số nguyên cách nhau bởi dấu cách $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$).

Dòng thứ ba chứa $n+1$ số nguyên cách nhau bởi dấu cách $b_1, \dots, b_{n+1}$ ($0 \le b_i \le 10^9$).

Dữ liệu ra

In ra $n$ số nguyên cách nhau bởi dấu cách $ans_1, \dots, ans_n$, trong đó $ans_i$ là số lượng đồng xu tối thiểu cần thiết để hoàn thành trò chơi khi bắt đầu tại phòng $i$.

Nhiệm vụ con

Bài toán này bao gồm $8$ nhiệm vụ con, đáp ứng các yêu cầu sau:

1. $n \le 500$. Trị giá $12$ điểm.
2. $n \le 5000$. Trị giá $8$ điểm.
3. $n \le 2 \cdot 10^5$, $a_i = 0$. Trị giá $10$ điểm.
4. $n \le 2 \cdot 10^5$, $b_1 \le b_2 \le \dots \le b_{n+1}$. Trị giá $10$ điểm.
5. $n \le 2 \cdot 10^5$, $b_i \le 100$. Trị giá $19$ điểm.
6. $n \le 2 \cdot 10^5$. Trị giá $21$ điểm.
7. Các ràng buộc gốc của bài toán. Trị giá $20$ điểm.

Ví dụ

Ví dụ 1

3
2 1 3
9 8 5 7

6 4 3

Ví dụ 2

3
1 3 3
10 2 5 6

1 1 2

Ghi chú

Hãy xem xét ví dụ đầu tiên. Chiến lược tối ưu cho phòng đầu tiên như sau:

1. Nhận $2$ đơn vị kinh nghiệm trong phòng $1$.
2. Mua $6$ đơn vị kinh nghiệm với $6$ đồng xu.
3. Đi đến phòng $2$ qua cánh cửa thứ $2$.
4. Nhận $1$ đơn vị kinh nghiệm trong phòng $2$.
5. Đi đến phòng $1$ qua cánh cửa thứ $2$.
6. Thoát qua cánh cửa thứ $1$.

Tổng cộng chỉ cần $6$ đồng xu.

Đối với phòng thứ hai:

1. Nhận $1$ đơn vị kinh nghiệm trong phòng $2$.
2. Mua $4$ đơn vị kinh nghiệm với $4$ đồng xu.
3. Đi đến phòng $3$ qua cánh cửa thứ $3$.
4. Nhận $3$ đơn vị kinh nghiệm trong phòng $3$.
5. Thoát qua cánh cửa thứ $4$.

Chỉ cần $4$ đồng xu.

Đối với phòng thứ ba:

1. Nhận $3$ đơn vị kinh nghiệm trong phòng $3$.
2. Mua $2$ đơn vị kinh nghiệm với $2$ đồng xu.
3. Đi đến phòng $2$ qua cánh cửa thứ $3$.
4. Nhận $1$ đơn vị kinh nghiệm trong phòng $2$.
5. Đi đến phòng $3$ qua cánh cửa thứ $3$.
6. Mua $1$ đơn vị kinh nghiệm với $1$ đồng xu.
7. Thoát qua cánh cửa thứ $4$.

Chỉ cần $3$ đồng xu.