Ẩn nấp

Một tập đoàn tội phạm lớn vừa bị cảnh sát phát hiện và bao vây. Để thoát khỏi sự truy đuổi, các thành viên trong tổ chức cần tìm nơi ẩn náu. Có \(N\) căn nhà, được đánh số từ \(1\) đến \(N\), có thể sử dụng làm nơi trốn. \vspace0.3cm

Mỗi căn nhà thứ \(i\) có thể chứa tối đa \(B_i\) người. \vspace0.3cm

Giữa mỗi cặp căn nhà \(i\) và \(i+1\) \((i \in \{1, 2, \dots, N-1\})\), có một con đường nối liền với một khu vực trung chuyển. Khu vực trung chuyển thứ \(i\) hiện đang có \(P_i\) thành viên của tổ chức và \(U_i\) chiếc áo choàng tàng hình được tổ chức chuẩn bị sẵn.\vspace0.3cm

Khi cảnh sát ập đến, mỗi thành viên tại khu vực trung chuyển thứ \(i\) phải chọn một trong ba hành động sau:

• Di chuyển vào căn nhà \(i\);
• Di chuyển vào căn nhà \(i+1\);
• Mua áo choàng tàng hình và tiếp tục ẩn mình tại khu vực trung chuyển.

\vspace0.3cm

Nếu một thành viên không thể tìm được nơi ẩn náu tại một căn nhà hoặc không được trang bị áo choàng tàng hình, anh ta sẽ bị bắt. Là một tập đoàn tội phạm lớn, họ không muốn thành viên của mình rơi vào tình cảnh đó, nhưng các áo choàng tàng hình là siêu hiếm, cho nên tập đoàn muốn tối thiểu hóa số áo choàng được dùng. Hãy giúp những tên trộm đạt được mục đích của mình.

Nếu không có cách nào để các thành viên không bị bắt thì in ra "NO". Ngược lại in ra "YES" và in ra số áo choàng cần trang bị tối thiểu và một cách di chuyển tối ưu của các tên trộm.

Input

• Dòng đầu tiên chứa một số nguyên \(N\) \((1 \leq N \leq 10^6)\) -- số lượng căn nhà.
• Dòng thứ hai chứa \(N\) số nguyên \(B_1, B_2, \dots, B_N\) \((1 \leq i \leq N)\) -- sức chứa của từng căn nhà.
• Dòng thứ ba chứa \(N-1\) số nguyên \(P_1, P_2, \dots, P_{N-1}\) \((1 \leq i \leq N - 1)\) -- số lượng thành viên tại từng khu vực trung chuyển.
• Dòng thứ tư chứa \(N-1\) số nguyên \(U_1, U_2, \dots, U_{N-1}\) \((1 \leq i \leq N - 1)\) -- số lượng áo choàng tàng hình tại từng khu vực trung chuyển.

Output

• In NO nếu không thể giúp tất cả thành viên thoát.

Ngược lại:

• Dòng đầu tiên in YES.
• Dòng thứ \(2\) in ra số lượng áo choàng cần dùng.
• \(N-1\) hàng tiếp theo, mỗi hàng in ra ba số nguyên \(L_i\), \(M_i\), và \(R_i\). \(L_i\) biểu diễn số lượng tên trộm di chuyển qua ngôi nhà bên trái, \(R_i\) biểu diễn số lượng di chuyển qua phải, và \(M_i\) biểu diễn số lượng áo choàng được dùng giữa tòa nhà (i, i+1).
• Bạn có thể in ra bất kì cấu hình tối ưu nào.

Example

3
10 15 10
20 20
0 0

NO

3
10 15 10
20 20
0 11

YES
5
10 0 10
5 5 10

Scoring

• Có \(15\%\) số điểm: \(2 \leq N \leq 10^6\), \(0 \leq B_i \leq 2 \cdot 10^9\), \(0 \leq P_i \leq 10^9\), \(U_i = 0\).
• Có \(20\%\) số điểm: \(2 \leq N \leq 2000\), \(0 \leq B_i \leq 400\), \(0 \leq P_i \leq 200\), \(0 \leq U_i \leq 200\).
• Có \(30\%\) số điểm: \(2 \leq N \leq 4000\), \(0 \leq B_i \leq 4000\), \(0 \leq P_i \leq 2000\), \(0 \leq U_i \leq 2000\).
• \(35\%\) số điểm còn lại: \(2 \leq N \leq 10^6\), \(0 \leq B_i \leq 2 \cdot 10^9\), \(0 \leq P_i \leq 10^9\), \(0 \leq U_i \leq 10^9\).