Để cài đặt tọa độ cho cổng dịch chuyển không gian, máy tính lượng tử cần thực hiện phép tính lũy thừa siêu lớn. Tọa độ chính là kết quả của phép tính A mũ B. Do hệ thống hiển thị bị giới hạn, bạn chỉ cần báo cáo phần dư của kết quả này khi chia cho M. Vì A và B cực kỳ lớn, vòng lặp thông thường sẽ mất hàng trăm năm để chạy xong. Hãy dùng thuật toán tối ưu để đưa ra đáp án trong chưa tới 1 giây.

Input: Một dòng chứa ba số nguyên dương A, B, M (1 <= A, B, M <= 10^18).

Output: Kết quả của A^B modulo M.

Ví dụ:

Input:

2 10 1000

Output:

24

Vệ tinh vừa gửi về một bức ảnh độ phân giải cao dưới dạng ma trận điểm ảnh kích thước N x N. Do vệ tinh bay ngược chiều, bức ảnh đang bị nghiêng. Bạn hãy viết một script xử lý ảnh để xoay toàn bộ ma trận này 90 độ theo chiều kim đồng hồ. Yêu cầu bộ nhớ phải được tối ưu, nếu có thể hãy xoay trực tiếp trên ma trận ban đầu (in-place).

Input:

Dòng 1: Số nguyên N (1 <= N <= 1000).

N dòng tiếp theo: Mỗi dòng chứa N số nguyên đại diện cho mã màu của điểm ảnh.

Output: Ma trận N x N sau khi xoay 90 độ chiều kim đồng hồ.

Ví dụ:

Input:

3
1 2 3
4 5 6
7 8 9

Output:

7 4 1
8 5 2
9 6 3

Tổng bộ tình báo có một bản đồ đánh giá mức độ nguy hiểm của N x N khu vực, được biểu diễn bằng một ma trận. Đặc điểm của bản đồ này là mức độ nguy hiểm tăng dần từ trái sang phải trên mỗi hàng, và cũng tăng dần từ trên xuống dưới trên mỗi cột. Đội đặc nhiệm cần chọn ra khu vực có mức độ nguy hiểm nhỏ thứ K trên toàn bản đồ để xâm nhập. Hãy tìm mức độ nguy hiểm đó.

Input:

Dòng 1: Hai số nguyên N, K (1 <= N <= 300, 1 <= K <= N*N).

N dòng tiếp theo: Mỗi dòng N số nguyên (các giá trị <= 10^9).

Output: Mức độ nguy hiểm nhỏ thứ K.

Ví dụ:

Input:

3 8
1 5 9
10 11 13
12 13 15

Output:

13

Sơ đồ nhân sự của công ty là một cấu trúc cây gồm N nhân viên (nhân viên 1 là giám đốc). Mỗi người có một chỉ số năng lực làm việc P_i. Công ty cần lập một đội đặc nhiệm từ N người này. Tuy nhiên, để tránh mâu thuẫn chỉ đạo, quy tắc bất thành văn là: Không được phép chọn cả nhân viên và người quản lý trực tiếp của nhân viên đó vào đội. Hãy chọn người sao cho tổng năng lực của đội là lớn nhất.

Input:

Dòng 1: Số nguyên N (1 <= N <= 10^5).

Dòng 2: N số nguyên Pi (1 <= Pi <= 10^4).

N - 1 dòng tiếp theo: Mỗi dòng chứa hai số u, v mô tả mối quan hệ quản lý trực tiếp giữa u và v.

Output: Tổng năng lực lớn nhất có thể.

Ví dụ:

Input:

5
10 1 1 10 10
1 2
1 3
2 4
2 5

Output:

30

(Giải thích: Chọn nhân viên 1, 4, 5. Tổng năng lực = 10 + 10 + 10 = 30. Không vi phạm vì quản lý của 4, 5 là nhân viên 2 (không được chọn)).