Bài tập

Khai báo một mảng một chiều có 6 phần tử kiểu số nguyên, đặt tên là dataArray. Khởi tạo mảng này với các giá trị: 15, 8, 22, 10, 30, 5.
Tìm phần tử có giá trị lớn nhất trong dataArray và lưu giá trị đó vào một biến số nguyên, đặt tên là maxValue.

Input

Không có dữ liệu đầu vào.

Output

Giá trị cuối cùng của biến maxValue sau khi tìm kiếm.

Example

Nothing

30

Trong một hệ thống mạng máy tính hiện đại, các máy chủ và thiết bị được kết nối với nhau theo một cấu trúc đặc biệt, tạo thành một mạng lưới dạng cây. Có tổng cộng \(n\) thiết bị, được nối với nhau bằng \(n-1\) sợi cáp. Một nhà quản lý mạng tên là Dũng có nhiệm vụ gán cho mỗi thiết bị một mức ưu tiên.

Mức ưu tiên này được biểu thị bằng một chữ cái từ 'A' đến 'Z', với 'A' là mức ưu tiên cao nhất và 'Z' là thấp nhất. Dũng có thể sử dụng bất kỳ số lượng chữ cái nào cho mỗi mức ưu tiên.

Tuy nhiên, có một quy tắc quan trọng phải tuân thủ để đảm bảo tính ổn định của mạng: Nếu hai thiết bị khác nhau, \(x\) và \(y\), có cùng mức ưu tiên, thì trên đường truyền đơn giản (đường đi ngắn nhất) giữa chúng phải có một thiết bị \(z\) với mức ưu tiên cao hơn. Điều này giúp đảm bảo rằng mọi giao tiếp giữa các thiết bị cùng cấp đều được một thiết bị quan trọng hơn giám sát.

Nhiệm vụ của bạn là giúp Dũng lập một kế hoạch gán mức ưu tiên hợp lệ. Nếu có thể, hãy chỉ ra mức ưu tiên của từng thiết bị. Nếu không, hãy thông báo rằng không có cách nào để thực hiện.

Input

Dữ liệu vào được cung cấp từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa một số nguyên \(n\) (\(2 \le n \le 2 \times 10^5\)), là số thiết bị.
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) (\(1 \le a, b \le n, a \ne b\)), mô tả một sợi cáp nối giữa thiết bị \(a\) và thiết bị \(b\).

Output

In ra kết quả trên đầu ra chuẩn theo định dạng sau:

• Nếu có một kế hoạch hợp lệ, xuất ra \(n\) ký tự trên một dòng. Ký tự thứ \(i\) là mức ưu tiên của thiết bị \(i\).
• Nếu không thì xuất ra "Impossible!".

Example

5
1 2
1 3
1 4
1 5

ABBBB

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\).

Cho một dãy \(n\) số nguyên dương \(a_0, a_1, \ldots, a_{n-1}\).

Với mọi \(U\) thỏa mãn \(0 \leq U < n\): Tính tổng \(a_i \cdot a_j\) với mọi \(0\leq i,j < n, (i\text{ or }j) \leq U\).

Toán tử or ở đây biểu thị cho toán tử nhị phân OR.

Input

• Dòng đầu chứa số nguyên duy nhất là \(n\) \((1 \leq n \leq 2 \cdot 10^5)\), độ dài mảng \(a\).

• Dòng thứ hai chứa \(n\) số nguyên dương \(a_0, a_1, \ldots, a_{n-1}\) \((0 < a_{i} \leq 10^7)\).

Output

• In ra \(n\) số nguyên dương trên cùng một dòng duy nhất. Số thứ \(i\) là đáp án cho \(U = i - 1\) khi chia dư cho \(10^9 + 7\).

Example

3
1 2 8

1 9 89 

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 500\).

• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10^4\).

• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.