Cho mảng ~A~ gồm ~N~ số nguyên dương. Đếm số lượng phần tử khác nhau của mảng đó và in ra các phần tử khác nhau đó theo thứ tự tăng dần.

Input

Dòng đầu tiên chứa duy nhất số nguyên ~N~ (~1 \leq N \leq 5000~).

Dòng tiếp theo chứa ~N~ số nguyên dương ~A_i~ (~A_i \leq 10^9~).

Output

Dòng đầu in ra số ~M~ là số phần tử khác nhau trong mảng ~A~.

Dòng sau in ra ~M~ số nguyên đó theo thứ tự tăng dần.

Test mẫu

Input

5
1 3 3 2 1

Output

3
1 2 3

Trên quốc lộ ~1A~ có ~N + 1~ trạm xăng từ đầu đến cuối con đường, đánh số từ ~0~ đến ~N~. Biết trạm xăng số ~i~ cách trạm xăng số ~i - 1~ một khoảng ~a_i~ km và trạm xăng số ~i~ bán ~1~ lít xăng với giá ~p_i~ đồng. Để đi được ~1~ km ta cần tiêu tốn ~1~ lít xăng.

TDZ đang bắt đầu đi trên quốc lộ ~1A~ thì hết xăng nên phải dừng tại trạm xăng số ~0~. Tính số tiền mua xăng nhỏ nhất mà TDZ phải mua để đến được trạm xăng số ~N~.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~N \leq 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~ (~a_i \leq 10^9~).
• Dòng thứ ba chứa ~N~ số nguyên dương ~p_0, p_1, \ldots, p_{N - 1}~ (~p_i \leq 10^9~).

Output

• In ra tổng số tiền nhỏ nhất dùng mua xăng để TDZ đến được trạm xăng số ~N~.

Sample Test

Input:

3
1 2 4
3 1 2

Output:

9

Note:

• TDZ mua ~1~ lít xăng ở trạm xăng thứ ~0~ (giá ~3~ đồng) để đi đến trạm xăng số ~1~.
• TDZ mua ~6~ lít xăng ở trạm xăng thứ ~1~ (giá ~6~ đồng) để đi đến trạm xăng cuối cùng.

Nhập vào hai số tự nhiên ~a~, ~b~ không đồng thời bằng ~0~. Hãy cho biết ước số chung lớn nhất của ~a~ và ~b~.

Input

• Hai số nguyên không âm ~a,b\leq 10^{18}~ cách nhau bởi dấu cách, (~a~, ~b~ không đồng thời bằng ~0~).

Output

• Ghi ra thiết bị xuất chuẩn một số nguyên duy nhất ước số chung lớn nhất của ~a~ và ~b~.

Sample Tests

Input

100 128

Output

4

Cho số nguyên dương ~n~, hãy phân tích ~n~ dưới dạng thừa số nguyên tố.

Input

• Gồm số nguyên dương ~n~.

Output

• In ra theo ví dụ.

Constraints

• ~1 \le n \le 10^{12}~.

Sample Input 1

12

Sample Output 1

2 2
3 1

Giải thích

~12 = 2^2 \times 3^1~

Cho dãy ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~ và ~q~ truy vấn, mỗi truy vấn gồm hai số ~l, r~.

Với mỗi truy vấn, hãy tính tổng các phần tử có vị trí từ ~l~ đến ~r~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, q \ (1\le n, q\le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n \ (|a_i| \le 10^5, 1\le i\le n)~.
• ~q~ dòng sau, mỗi dòng chứa hai số nguyên ~l_i, r_i \ (1\le l_i \le r_i \le n, 1\le i\le q)~.

Output

Kết quả gồm ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~ ~(1\le i\le q)~.

Ví dụ

Input

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

Output

-1
-3
3

Cho số nguyên dương ~n~, hãy tìm số Fibonacci thứ ~n~.

Số Fibonacci thứ ~i~ được định nghĩa như sau: ~ \begin{equation} f_i = \begin{cases} 1 & \text{nếu $i \leq 2$}\\ f_{i - 1} + f_{i - 2} & \text{nếu $i > 2$} \end{cases} \end{equation} ~

Ví dụ dãy Fibonacci cho ~10~ số đầu tiên: ~1, 1, 2, 3, 5, 8, 13, 21, 34, 55~.

Input

Gồm một số nguyên dương ~n~ duy nhất. (~n \leq 75~)

Output

In ra số Fibonacci thứ ~n~.

Subtasks

Subtask ~1~ (~40\%~): ~n \leq 40~.

Subtask ~2~ (~60\%~): Không có điều kiện gì thêm.

Sample Test 1

Input:

4

Output:

3

Sample Test 2

Input:

10

Output:

55

Cho số nguyên dương ~n~ và dãy ~a~ chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~. Hãy tìm hai chỉ số ~i, j~ sao cho hiệu ~a_j - a_i~ là lớn nhất ~(1 \leq i < j \leq n)~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n\left(1 \leq n \leq 10^{5}\right)~;
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_{i}\left(\left|a_{i}\right| \leq 10^{9}\right)~.

Output

Ghi ra hiệu lớn nhất có thể.

Sample Test

Cho một hệ thống tiền gồm ~n~ loại xu trong đo mỗi loại xu có một giá trị nguyên dương. Nhiệm vụ của bạn là tạo ra tổng ~x~ sao cho số đồng xu sử dụng là ít nhất.

Ví dụ, nếu có các loại xu ~{1, 5, 7}~ và tổng cần tạo là ~11~ thì một giải pháp tối ưu là ~5 + 5 + 1~ sử dụng ~3~ đồng xu.

Input

• Dòng thứ nhất chứa hai số nguyên ~n~ và ~x~: số đồng xu và tổng cần tạo.
• Dòng thứ hai chứa ~n~ số nguyên đôi một khác nhau ~c_1, c_2, \ldots, c_n~: giá trị của mỗi loại xu.

Output

• In ra số đồng xu ít nhất cần sử dụng. Nếu không có cách nào in ra -1.

Constraints

• ~1\leq n \leq 100~
• ~1\leq x \leq 10^6~
• ~1\leq c_i \leq 10^6~

Sample Test