Phần lớn các quốc gia trên thế giới sử dụng thang nhiệt độ Celsius (ký hiệu ~°C~). Trong điều kiện áp suất bình thường, nước đóng băng ở ~0°C~ và sôi ở ~100°C~.

Tuy nhiên, ở một số quốc gia lại sử dụng thang nhiệt độ Fahrenheit (ký hiệu ~°F~). Theo thang Fahrenheit, trong điều kiện áp suất bình thường, nước đóng băng ở ~32°F~ và sôi ở ~212°F~.

Gọi ~t_c~ là nhiệt độ theo thang Celsius và ~t_f~ là nhiệt độ tương ứng theo thang Fahrenheit, ta có:

$$tc = \frac {5}{9} (t_f - 32)$$

$$tf = \frac {9}{5} t_c + 32$$

Cho nhiệt độ ở một thang nhiệt độ, hãy tính nhiệt độ tương ứng ở thang kia với độ chính xác đúng ~2~ chữ số sau dấu phẩy thập phân.

INPUT

Gồm một dòng chứa một số nguyên (nằm trong đoạn ~[-10^9, 10^9]~) và một ký tự chỉ thang nhiệt độ (viết liền nhau, không có dấu cách ở giữa).

Ký tự chỉ thang nhiệt độ là ~C~ hoặc ~F~ tương ứng cho biết đó là nhiệt độ Celsius hay Fahrenheit.

OUTPUT

Nhiệt độ tương ứng ở thang kia với độ chính xác đúng ~2~ chữ số sau dấu phẩy thập phân và ký tự ~C~ hoặc ~F~ chỉ thang nhiệt độ tương ứng (viết liền nhau, không có dấu cách ở giữa).

SAMPLE INPUT 1

0C

SAMPLE OUTPUT 1

32.00F

SAMPLE INPUT 2

212F

SAMPLE OUTPUT 2

100.00C

SAMPLE INPUT 3

-37C

SAMPLE OUTPUT 3

-34.60F

SAMPLE INPUT 4

10F

SAMPLE OUTPUT 4

-12.22C

Cho mảng ~a~ gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~. Bạn có thể thay thế một số phần tử ~a_i~ của mảng bằng ~-a_i~ sao cho mảng không giảm hoặc nói rằng điều này là không thể.

Mảng ~a_1, a_2, ..., a_n~ được gọi là mảng không giảm nếu ~a_1 \le a_2 \le ... \le a_n~

INPUT

Dòng đầu tiên chứa số nguyên ~n~ (~1 ≤ n ≤ 10^5~) là số phần tử của mảng ~a~.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~-10^9 ≤ a_i ≤ 10^9~) là các phần tử của mảng ~a~.

OUTPUT

Nếu không thể thay thế một số phần tử ~a_i~ bằng ~-a_i~ để làm cho mảng không giảm, thì hãy ghi ra No.

Ngược lại ghi ra hai dòng, dòng đầu tiên ghi Yes và dòng thứ hai ghi ~n~ số nguyên ~b_1, b_2, ..., b_n~ tạo thành một mảng không giảm và đối với mọi ~1 ≤ i ≤ n~, ta có ~b_i = a_i~ hoặc ~b_i = -a_i~. Nếu có nhiều câu trả lời thì ghi ra một câu trả lời bất kỳ trong chúng. Chú ý rằng số phép thay thế không cần thiết phải tối thiểu.

SAMPLE INPUT 1

5
1 -1 -2 3 6 

SAMPLE OUTPUT 1

Yes
-1 -1 2 3 6

SAMPLE INPUT 2

3
-3 8 5

SAMPLE OUTPUT 2

No

SAMPLE INPUT 3

4
1 2 3 4

SAMPLE OUTPUT 3

Yes

Gần đây An bắt đầu đăng ký một công ty cung cấp các phần mềm trí tuệ nhân tạo và đã nộp các hồ sơ cần thiết. Các người bạn thân đã nói với An rằng trong danh sách xét duyệt hồ sơ, các công ty được liệt kê theo thứ tự từ điển tăng dần của tên công ty. An không biết tên các công ty khác trong danh sách, nhưng anh ta quyết định xem xét các khuyến nghị và đổi tên công ty của mình để nó có thứ tự từ điển trong danh sách càng nhỏ càng tốt.

Vì An đã nộp hồ sơ nên anh ta không thể thay đổi hoàn toàn tên của công ty, nhưng anh ta có thể lấy lý do mắc lỗi soạn thảo là hoán đổi hai chữ cái bất kỳ trong tên. Bạn hãy giúp An chọn tên công ty mới bằng cách hoán đổi hai chữ cái bất kỳ trong tên hoặc giữ nguyên tên hiện tại, để cho tên công ty có thứ tự từ điển trong danh sách càng nhỏ càng tốt.

INPUT

Gồm một dòng chứa một xâu gồm các chữ cái tiếng Anh viết thường (từ a đến z) có độ dài ~n~ (~2 ≤ n ≤ 10^6~) là tên công ty của An.

OUTPUT

Một xâu là tên công ty mới. Nếu tên không thay đổi thì in tên gốc.

SAMPLE INPUT 1

aefbz

SAMPLE OUTPUT 1

abfez

Trong ví dụ đầu tiên, An có thể giữ nguyên tên công ty aefbz, hoặc hoán đổi các cặp ký tự ở các vị trí ~(1, 2)~, ~(1, 3)~, ~(1, 4)~, ~(1, 5)~, ~(2, 3)~, ~(2, 4)~, ~(2, 5)~, ~(3, 4)~, ~(3, 5)~, ~(4, 5)~ để được các tên công ty mới tương ứng là aefbz, afebz, ebafz, zefba, afebz, abfez, azfbe, aefbz, aezbf, aefzb. Trong các tên trên, việc hoán đổi cặp ký tự ở vị trí ~(2, 4)~ cho tên abfez có thứ tự từ điển nhỏ nhất.

SAMPLE INPUT 2

abc

SAMPLE OUTPUT 2

abc

Trong ví dụ thứ hai, An giữ nguyên tên công ty vì sẽ cho tên có thứ tự từ điển nhỏ nhất.

SUBTASKS

• Có ~20 \%~ số test thỏa mãn ~n \le 10~.
• Có ~20 \%~ số test thỏa mãn ~n \le 100~.
• Có ~20 \%~ số test thỏa mãn ~n \le 3000~.
• Có ~20 \%~ số test thỏa mãn ~n \le 5 \times 10^4~.
• Có ~20 \%~ số test không có ràng buộc gì thêm.

An đang chơi trò chơi Chiến tranh giữa các vì sao. Trong trò chơi, nhân vật của An cần phải thu được càng nhiều sức mạnh càng tốt từ các vì sao trong vũ trụ.

Có ~n~ vì sao được đánh số từ ~1~ đến ~n~ mà nhân vật của An có thể sẽ đi qua. Để không làm tổn hại đến sự toàn vẹn của vũ sao, nhân vật không thể quay ngược, nghĩa là nếu nhân vật đã đi từ vì sao thứ nhất đến vì sao thứ tư, thì nhân vật không thể đi đến vì sao thứ hai hoặc thứ ba, nhân vật phải tiếp tục đi về phía trước. Tổng quát, nếu nhân vật đang ở vì sao ~i~ thì nhân vật chỉ có thể đi đến vì sao ~j~ với ~j ≥ i~.

Với mỗi hành tinh ~i~ có một tham số ~a_i~. Khi nhân vật của An đi từ hành tinh ~i~ đến hành tinh ~j~, nó sẽ nhận thêm một sức mạnh ~gcd (a_i, a_j)~, trong đó ~gcd (a_i, a_j)~ là ước chung lớn nhất của ~a_i~ và ~a_j~. Lúc bắt đầu, sức mạnh của An có ~1~ đơn vị sức mạnh và xuất phát từ vì sao ~1~. Mục tiêu của An là đưa nhân vật đến vì sao ~n~ với tổng sức mạnh lớn nhất. Cụ thể là tìm một dãy các chỉ số ~i_1 = 1, i_2 < ... < i_k = n~, sao cho tổng sau lớn nhất:

$$1 + gcd(a_{i_1}, a_{i_2}) + gcd(a_{i_2}, a_{i_3}) + ... + gcd(a_{i_{k-1}}, a_{i_k})$$

Bạn hãy giúp An tính tổng sức mạnh lớn nhất mà nhân vật của anh ta có thể nhận được.

INPUT

Dòng đầu tiên chứa số nguyên ~n~ (~1 ≤ n ≤ 2 \times 10^5~) là số vì sao.

Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 ≤ a_i ≤ 2 \times 10^5 + 3~) là các tham số của các vì sao.

OUTPUT

Một số nguyên là tổng sức mạnh lớn nhất mà nhân vật của An có thể nhận được.

SAMPLE INPUT 1

4
5 1 1 5

SAMPLE OUTPUT 1

6

Trong ví dụ đầu tiên, An sẽ di chuyển nhân vật từ vì sao ~1~ đến vì sao ~4~. Chú ý rằng, ban đầu nhân vật có ~1~ đơn vị sức mạnh. Tổng sức mạnh của nhân vật sẽ là: ~1 + gcd (5, 5) = 6~.

SAMPLE INPUT 2

5
6 4 15 9 10

SAMPLE OUTPUT 2

9

Trong ví dụ thứ hai, An sẽ di chuyển nhân vật từ vì sao ~1~ đến vì sao ~3~, rồi đến vì sao ~5~. Tổng sức mạnh của nhân vật sẽ là: ~1 + gcd (6,15) + gcd (15,10) = 9~.

SUBTASKS

• Có ~20 \%~ số test thỏa mãn ~n \le 20~.
• Có ~20 \%~ số test thỏa mãn ~n \le 1000~.
• Có ~20 \%~ số test thỏa mãn ~a_i~ là các số nguyên tố.
• Có ~20 \%~ số test thỏa mãn ~n \le 2 \times 10^4~ và ~a_i \le 100~.
• Có ~20 \%~ số test không có ràng buộc gì thêm.