Hiện tại bây giờ là 12 giờ 00 phút. Cho một số nguyên dương ~x~, hãy tính xem sau ~x~ phút thì kim giờ và kim phút hợp với nhau tạo thành góc bao nhiêu độ? (Lấy góc không vượt quá 180 độ).

Yêu cầu: Tính góc tạo bởi kim giờ và kim phút sau ~x~ phút.

Input

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

Output

• Một số thực duy nhất là kết quả tìm được, làm tròn đến 2 chữ số sau phần thập phân.

Sample Input 1

60

Sample Output 1

30.00

Sample Input 2

135

Sample Output 2

22.50

Trong kỳ thi HSG năm nay nhà trường có trao một phần thưởng vô cùng thú vị cho thí sinh giành giải nhất môn Tin học. Số tiền thưởng mà thí sinh nhận được chính là số điểm mà thí sinh đó lấy được trong trò chơi sau: Cho một dãy ~n~ số nguyên không âm ~a_1, a_2, \dots, a_n~. Ban đầu người chơi có 0 điểm. Tại mỗi lượt chơi, người chơi sẽ chọn một phần tử ~a_i~ bất kỳ trên dãy đã cho. Khi đó, số điểm của người chơi sẽ được tăng lên ~a_i~, đồng thời phần tử ~a_i~ sẽ bị loại bỏ ra khỏi dãy và tất cả phần tử khác 0 còn lại trong dãy giảm đi 1. Trò chơi kết thúc khi dãy số không còn phần tử nào hoặc gồm các số 0.

Yêu cầu: Hãy cho biết số tiền lớn nhất mà thí sinh giải nhất có thể nhận được.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~n \le 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, \dots, a_n~ (~0 \le a_i \le 10^9~).

Output

• Số tiền lớn nhất mà thí sinh giải nhất có thể nhận được.

Sample Input 1

4
1 1 4 3

Sample Output 1

6

Cho dãy ~n~ số nguyên, số thứ ~i~ có giá trị là ~a_i~. Một thao tác nghịch đảo ~[x, y]~ sẽ đảo dấu toàn bộ các giá trị của các phần tử từ vị trí thứ ~x~ đến vị trí thứ ~y~ (số âm thành số dương, số dương thành số âm).

Yêu cầu: Cho ~q~ thao tác, hãy tính số lượng số dương, số lượng số âm của dãy số sau khi thực hiện ~q~ thao tác.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, q~ (~1 \le n, q \le 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ mô tả giá trị của phần tử thứ ~i~ (~|a_i| \le 10^9~).
• ~q~ dòng sau, dòng thứ ~j~ chứa hai số nguyên ~x, y~ (~1 \le x \le y \le n~) mô tả thao tác.

Output

• Gồm một dòng duy nhất chứa hai số nguyên là số lượng số dương và số lượng số âm sau khi thực hiện ~q~ thao tác.

Sample Input 1

5 3
2 3 0 -1 4
1 4
2 5
1 5

Sample Output 1

3 1

Để thu hút khách hàng mua vé sổ số, công ty sổ số XYZ ngoài việc hàng ngày quay số và trao giải cho khách hàng công ty còn trao giải Độc đắc cho khách hàng sau mỗi chu kỳ ~n~ ngày. Để được giải Độc đắc thì khách hàng phải có đủ ~n~ vé số của ~n~ ngày, vé số thứ ~i~ phải có giá trị bằng ~a_i~.

Mới đây thầy NHM là người duy nhất nhận được giải Độc đắc và đã nhận được số tiền rất rất lớn. Thầy quyết định dùng tiền của mình mới nhận được để đầu tư mua nhà. Dọc theo tuyến phố mới là dãy nhà đang được giao bán, các ngôi nhà đánh số từ ~1, 2, \dots, n~. Thầy dự định dùng dãy số ~a~ may mắn ở trên để tạo ra tất cả các dãy con, nếu tổng của dãy con nào đó là một số nguyên tố thì thầy sẽ mua ngôi nhà được đánh số bằng tổng đó.

Tuy nhiên vợ của thầy lại không muốn đầu tư mua nhà. Cuối cùng họ đã thống nhất như sau: "Vợ của thầy được phép bỏ đi ~k~ phần tử nào đó trong dãy ~a~, khi đó thầy NMH chỉ được phép sử dụng ~n - k~ phần tử còn lại".

Yêu cầu: Hãy lập trình giúp vợ thầy NMH chọn ra ~k~ phần tử cần bỏ đi sao cho số ngôi nhà mà thầy NMH sẽ mua là ít nhất có thể.

Input

• Dòng đầu chứa hai số nguyên ~n, k~ (~1 \le n \le 100; 0 \le k \le 1~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^3~).

Output

• Một số nguyên duy nhất là số nhà ít nhất mà thầy NMH có thể mua.

Sample Input 1

3 0
2 6 3

Sample Output 1

4

Sample Input 2

3 1
2 6 5

Sample Output 2

1

Ở thành phố có ~N~ trạm xe bus. Hàng ngày, An sẽ xuất phát từ nhà lúc 6 giờ 00 phút ở trạm xe bus số 1 để tới trường ở trạm xe bus ~N~. Vì thành phố không có nhiều người, hàng ngày, chỉ có một chuyến xe bus xuất phát từ trạm xe số 1 lúc 6 giờ 00 phút và đi với lộ trình ~p_1, p_2, \dots, p_N~ để đi qua ~N~ trạm xe bus. Trong đó ~p_1, p_2, \dots, p_N~ là một hoán vị của dãy số từ 1 đến ~N~ và ~p_1~ luôn bằng 1. Thời gian di chuyển qua các trạm là 1 phút. Xe bus sẽ dừng lại khi đi qua hết ~N~ trạm. Người dân xây thêm ~M~ con đường một chiều nối giữa các trạm xe bus, con đường thứ ~j~ nối từ trạm ~a_j~ tới trạm ~b_j~. Thời gian di chuyển trên con đường này cũng là 1 phút.

Trong ~K~ ngày, mỗi ngày xe bus sẽ hoán đổi lộ trình giữa trạm thứ ~x~ và ~y~ trong lộ trình. Lưu ý xe bus luôn đảm bảo lộ trình xuất phát từ trạm số 1, và những thay đổi lộ trình này vẫn sẽ được giữ nguyên cho những ngày sau.

Yêu cầu: Trong ~K~ ngày này, bạn hãy giúp An kiểm tra xem thời gian ít nhất để tới được trường là bao nhiêu phút.

Input

• Dòng đầu tiên chứa ba số nguyên ~N, M, K~ (~1 \le N, M, K \le 2 \times 10^5~).
• Trong ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a_j, b_j~.
• Dòng tiếp theo chứa dãy ~N~ số ~p_1, p_2, \dots, p_N~.
• Trong ~K~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~.

Output

• Gồm ~K~ dòng, mỗi dòng chứa một số nguyên là thời gian ít nhất cần để An tới trường.

Sample Input 1

4 3 3
1 2
3 4
4 1
1 4 3 2
3 4
4 2
3 2

Sample Output 1

1
2
3