Cho mảng ~a~ chứa ~n~ số nguyên. Với mỗi phần tử ~a_i~ của mảng, bạn phải sắp xếp lại các chữ số của phần tử đó, sao cho giá trị ~a_i~ thu được sau khi sắp xếp các chữ số của nó là lớn nhất.Biết rằng chiều dài ~a_i~ trước và sau sắp xếp không thay đổi.

Sau đó in ra các phần tử của mảng theo chiều không tăng, mỗi phần tử cách nhau bởi một dấu cách.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ ( ~n \le 1000~ ).
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ là các phần tử của mảng a , các phần tử cách nhau bởi dấu cách ( ~|a_i| \le 10^4 ~).

Output

In ra các phần tử của mảng theo yêu cầu đề bài.

Sample

Input #1

10
61 947 6 96 534 2669 4 263 1449 77

Output #1

9662 9441 974 632 543 96 77 61 6 4

Problem source: CLB Lập Trình PTIT

• Cho số nguyên ~n~ phân tích ~n~ thành tích các thừa số nguyên tố.

Input

• Gồm duy nhất số nguyên dương ~n (2 \le n \le 10^{18})~.

Output

• Gồm nhiều dòng mỗi dòng gồm 2 số nguyên dương. Số đầu tiên là thừa số nguyên tố ~p~, số thứ hai là số mũ của ~p~ trong thừa số nguyên tố của ~n~.
• Chú ý: Cần sắp xếp các thừa số nguyên tố tăng dần theo thứ tự từ trên xuống.

Sample

Input #1

12

Output #1

2 2
3 1

Problem source: ducla0104

Cho một đồ thị vô hướng có ~n(1 \leq n \leq 2500)~ đỉnh và ~m(1 \leq m \leq 6200)~ cạnh, hãy tìm đường đi ngắn nhất từ ~s~ đến ~t~.

Input

• Dòng đầu tiên chứa bốn số nguyên ~n, m, s, t~ cách nhau bởi dấu cách.
• ~m~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương ~s_i, t_i, w_i (1 \leq w_i \leq 10^9)~ là cạnh từ ~s_i~ đến ~t_i~ có độ dài ~w_i~.

Output

Một số nguyên đại diện cho độ dài của con đường ngắn nhất từ ~s~ đến ~t~. Dữ liệu đảm bảo rằng tồn tại ít nhất một đường đi.

Sample

Input #1

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

Output #1

7

Sau khi có kết quả thi HSG Quốc gia 2017, thầy X quyết định ăn mừng bằng cách lát lại sàn phòng học Đội tuyển Tin. Để sàn nhà sau khi lát hợp mốt, thầy X quyết định lát sàn nhà bằng các viên gạch hình vuông kích cỡ ~1 × 1~, mỗi viên gạch có màu trắng hoặc đen. Ngoài ra, trong bốn viên gạch bất kì tạo thành một hình vuông ~2×2~ phải có ít nhất một viên gạch màu đen và một viên gạch màu trắng.

Giả sử phòng học Đội tuyển Tin của thầy X có kích cỡ ~3 × 3~, khi đó các cách lát sau là hợpmốt:

và các cách lát sau là không hợp mốt:

Khi đang lát gạch, thầy X tự dưng nghĩ ra bài toán sau: Biết kích cỡ phòng học Đội tuyển Tin là ~N ×M~, hãy tính phần dư khi chia số cách lát phòng học hợp mốt cho ~P~.

Input

• Gồm một dòng duy nhất chứa ba số nguyên ~N, M, P (1 ≤ N ≤ 10^{200}, 1 ≤ M ≤ 5, 1 ≤ P ≤ 10000)~.

Output

• Gồm một dòng duy nhất chứa một số nguyên là kết quả của bài toán do thầy X nghĩ ra.

Sample

Input #1

2 2 5

Output #1

1

Input #2

3 3 23

Output #2

0

Problem source: Kc97ble - Free Contest 37

Đề bài

Cho một chuỗi số La Mã hợp lệ, hãy đổi về dạng số thập phân của nó.

Được biết các ký hiệu trong số La Mã như sau:

• I: 1
• V: 5
• X: 10
• L: 50
• C: 100
• D: 500
• M: 1000

Trong đó sẽ có một số trường hợp đặc biệt:

• IV: 4
• IX: 9
• XL: 40
• XC: 90
• CD: 400
• CM: 900

Mẫu input & output

• Input: Gồm một chuỗi số La Mã hợp lệ.

XIII

• Output: Dạng số thập phân của chuỗi đã cho.

13