Mặt đồng hồ kim là một hình tròn chia thành 60 vạch và được đánh số từ 0 đến 59. Hiện tại, kim phút chỉ vào vạch có chỉ số là \(m\) \((0 \le m < 60)\) và cứ một phút, kim phút sẽ di chuyển sang vạch bên cạnh theo chiều kim đồng hồ.

Yêu cầu: Hãy cho biết sau \(n\) phút thì kim phút chỉ vào vạch số mấy?

Input

Vào tệp CLOCK.INP gồm hai số nguyên dương \(m, n\) (\(n \le 10^{18}\)), cách nhau một khoảng trắng.

Output

Ghi ra tệp CLOCK.OUT một dòng chứa một số nguyên là chỉ số vạch mà kim phút chỉ vào sau \(n\) phút.

Giới hạn

• \(0 \le m < 60\).
• \(0 \le n \le 10^{18}\).

5 19

24

Tý rất thích chơi bi nhưng chỉ thích những viên bi màu đỏ và màu xanh. Hôm nay, Tý cần mua bi bỏ vào \(n\) cái hộp, mỗi hộp chỉ chứa được một hoặc hai viên bi. Nếu hộp chứa hai viên bi thì phải bỏ vào đó hai viên bi khác màu, còn hộp chỉ chứa một viên bi thì bỏ vào đó viên bi có màu tuỳ ý.

Cho biết giá của một viên bi màu xanh là \(a\) đồng, viên bi màu đỏ là \(b\) đồng.

Yêu cầu: Tính số tiền ít nhất mà Tý cần có để mua bi bỏ đầy vào \(n\) hộp.

Input

Vào tệp COST.INP gồm:

• Dòng đầu tiên chứa ba số nguyên dương \(n, a, b\) \((1 \le n \le 10^6,\;1 \le a, b \le 100)\).
• Dòng thứ hai chứa \(n\) số nguyên, mỗi số là 1 hoặc 2, tương ứng với số lượng bi mà các hộp có thể chứa được.

Output

Ghi ra tệp COST.OUT một số nguyên duy nhất là số tiền tối thiểu Tý cần có để mua bi và bỏ đầy vào tất cả \(n\) hộp.

5 3 9
2 1 1 2 1

33

Hàng năm, công ty Alpha dựa vào thành tích lao động của các công nhân để chấm điểm tích lũy cho từng người và điểm số này dùng để xác định giá trị phần thưởng cho họ vào những dịp nghỉ lễ. Công ty hiện có \(m\) công nhân được đánh số từ 1 đến \(m\), công nhân thứ \(i\) có điểm tích lũy là \(p_i\). Năm nay, ban giám đốc sẽ chuẩn bị \(n\) phần thưởng có giá trị như nhau và sẽ tặng thưởng cho toàn bộ công nhân hoặc chỉ tặng thưởng cho công nhân có điểm số cao. Giá trị của mỗi phần thưởng bằng điểm số của người thấp nhất trong số những người được tặng thưởng.

Yêu cầu: Hãy tính tổng giá trị lớn nhất của các phần thưởng được tặng.

Input

Vào tệp PRIZE.INP gồm:

• Dòng đầu tiên chứa hai số nguyên dương \(m, n\) \((m,n \le 10^5)\).
• Dòng thứ hai chứa \(m\) số nguyên dương \(p_1, p_2, \dots, p_m\) (\(p_i \le 1000\)).

Output

Ghi ra tệp PRIZE.OUT một số nguyên duy nhất là tổng giá trị phần thưởng lớn nhất có thể tặng.

Giới hạn

• Subtask 1 (60%): \(1 \le m,n \le 10^3\).
• Subtask 2 (40%): \(1 \le m,n \le 10^5\).

6 4
2 12 9 8 10 7

32

4 5
9 3 1 6

12

Với một số nguyên dương \(P\) \((P \ge 2)\), ta có thể phân tích \(P\) thành tích các thừa số nguyên tố, trong đó có một thừa số nguyên tố nhỏ nhất.
Ví dụ:

• \(100 = 2 \times 2 \times 5 \times 5\) thì 2 là thừa số nguyên tố nhỏ nhất của 100;
• \(15 = 3 \times 5\) thì 3 là thừa số nguyên tố nhỏ nhất của 15;
• \(17 = 17\) thì 17 là thừa số nguyên tố nhỏ nhất của 17.

Cho trước một dãy gồm \(n\) số nguyên tố \(a_1, a_2, \dots, a_n\) và một số nguyên dương \(k\).

Yêu cầu: Đếm xem trong đoạn \([2, k]\) có bao nhiêu số nguyên có thừa số nguyên tố nhỏ nhất là \(a_i\) \((1 \le i \le n)\).

Input

Vào tệp ZFACTOR.INP gồm:

• Dòng 1: hai số nguyên dương \(n\) và \(k\) \((1 \le n \le 10^5,\;2 \le k \le 10^6)\).
• Dòng 2: \(n\) số nguyên tố \(a_1, a_2, \dots, a_n\) \((2 \le a_i \le k)\).

Output

Ghi ra tệp ZFACTOR.OUT gồm \(n\) dòng, dòng thứ \(i\) là số lượng số nguyên trong đoạn \([2, k]\) có thừa số nguyên tố nhỏ nhất bằng \(a_i\).

Giới hạn

• Subtask 1 (50%): \(n, k \le 10^3\).
• Subtask 2 (50%): \(10^3 < n \le 10^5,\;10^3 < k \le 10^6\).

2 10
2 3

5
2