Bài tập

Viết chương trình nhập từ bàn phím một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\). Hãy tìm và in ra giá trị lớn nhất trong mảng.

Input

• Dòng đầu tiên là số nguyên dương \(n\) - độ dài của dãy \(a\). \((1 \leq n \leq 100)\).
• Dòng thứ hai là \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) - mỗi số cách nhau một dấu cách \((|a_i| \leq 100)\).

Output

Một dòng duy nhất chứa giá trị lớn nhất của mảng.

Example

5
3 2 1 5 2

5

Viết chương trình, nhập vào hai số nguyên \(a\) và \(b\). Nếu \(a = 5\) và \(b = 10\), thì in ra "Hop le". Ngược lại, in ra "Khong hop le".

Example

5 10

Hop le

5 9

Khong hop le

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

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.