Bài tập

Cho danh sách điểm môn Tin học của một lớp. Mỗi điểm là số thực từ \(0.0\) đến \(10.0\) và được viết với đúng một chữ số thập phân. Hãy liệt kê ba điểm cao nhất theo thứ tự giảm dần. Nếu có nhiều bạn cùng điểm thì mỗi bạn được tính riêng (ví dụ danh sách \(10.0\ 10.0\ 9.9\) cho ra ba điểm \(10.0\ 10.0\ 9.9\)).

Input

Một dòng duy nhất chứa danh sách điểm, các điểm cách nhau bởi một hoặc nhiều dấu cách. Danh sách có ít nhất \(3\) điểm.

Output

In ra ba điểm cao nhất theo thứ tự giảm dần, cách nhau một dấu cách, mỗi điểm có đúng một chữ số thập phân.

Constraints

• Danh sách có từ \(3\) đến \(1000\) điểm.

Sample Input

7.5 9.5 6.0 8.5 9.0 5.5

Sample Output

9.5 9.0 8.5

Một cái hồ có mặt hồ hình chữ nhật kích thước \(a \times b\) (mét), ban đầu hồ cạn. Máy bơm có công suất cố định \(3\ m^3\) mỗi giờ và được bật liên tục trong \(t\) giờ (không có nước chảy đi nơi khác). Một em bé rơi xuống hồ có chiều cao tính đến cổ là \(k\) (cm). Em bé được coi là an toàn nếu mực nước trong hồ không vượt quá \(k\) cm.

Hãy cho biết em bé có an toàn hay không.

Input

• Một dòng gồm bốn số nguyên dương \(a, b, k, t\), cách nhau bởi dấu cách.

Output

• In YES nếu em bé an toàn, ngược lại in WARNING.

Constraints

• \(1 \le a, b, k, t \le 9999\)

Sample Input 1

5 4 60 2

Sample Output 1

YES

Sample Input 2

6 5 20 4

Sample Output 2

WARNING

Explanation

Ở ví dụ 1, lượng nước là \(6\ m^3\) trên diện tích \(20\ m^2\), mực nước \(0.3\ m = 30\) cm \(\le 60\) cm nên an toàn. Ở ví dụ 2, lượng nước \(12\ m^3\) trên diện tích \(30\ m^2\), mực nước \(40\) cm \(> 20\) cm nên nguy hiểm.

Một nhà thám hiểm muốn ghé thăm đủ \(N\) thành phố, được đánh số từ \(1\) đến \(N\), bằng đường hàng không. Anh ta được tự do chọn thành phố xuất phát, sau đó bay lần lượt qua các thành phố còn lại sao cho mỗi thành phố được ghé đúng một lần (không cần quay về điểm đầu).

Giá vé bay thẳng từ thành phố \(i\) đến thành phố \(j\) là \(c_{i,j}\) (giá vé chiều đi và chiều về có thể khác nhau). Trong bài này, hãy chỉ ra một hành trình có tổng tiền vé nhỏ nhất.

Nếu có nhiều hành trình cùng có tổng tiền vé nhỏ nhất, hãy in hành trình có thứ tự từ điển nhỏ nhất (so sánh dãy các thành phố theo thứ tự ghé thăm, tại vị trí đầu tiên khác nhau, dãy có số nhỏ hơn được coi là nhỏ hơn).

Input

• Dòng đầu chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm \(N\) số nguyên \(c_{i,1}, c_{i,2}, \dots, c_{i,N}\).

Output

In ra \(N\) số nguyên trên một dòng, cách nhau một dấu cách: các thành phố theo thứ tự được ghé thăm.

Constraints

• \(1 \le N \le 16\).
• \(c_{i,i} = 0\); với \(i \ne j\) thì \(1 \le c_{i,j} \le 10^9\).

Sample Input

5
0 2 9 4 6
3 0 1 7 2
8 5 0 3 1
2 6 4 0 5
7 1 3 2 0

Sample Output

1 2 3 5 4

Explanation

Hành trình \(1 \to 2 \to 3 \to 5 \to 4\) có tổng chi phí \(2 + 1 + 1 + 2 = 6\), đây là mức nhỏ nhất và là hành trình nhỏ nhất theo thứ tự từ điển trong các hành trình tối ưu.

Cho ba số nguyên dương \(A\), \(B\) và \(N\). Hãy tính ước chung lớn nhất của hai số \(A^N\) (tức là \(A\) nhân với chính nó \(N\) lần) và \(B\), ký hiệu \(\gcd(A^N, B)\).

Lưu ý rằng \(A^N\) có thể lớn hơn rất nhiều so với phạm vi biểu diễn của các kiểu số nguyên thông thường.

Input

Một dòng duy nhất chứa ba số nguyên \(A\), \(B\), \(N\) cách nhau bởi dấu cách.

Output

In ra một số nguyên duy nhất là giá trị \(\gcd(A^N, B)\).

Constraints

• \(1 \le A, B \le 10^9\)
• \(1 \le N \le 10^{15}\)

Sample Input 1

12 90 1

Sample Output 1

6

Sample Input 2

6 72 2

Sample Output 2

36

Explanation

• Ví dụ 1: \(12^1 = 12\) và \(\gcd(12, 90) = 6\).
• Ví dụ 2: \(6^2 = 36\) và \(\gcd(36, 72) = 36\).