Bài tập

Viết chương trình nhập từ bàn phím một dãy \(a\) gồm \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) và một số nguyên \(X\). Hãy tìm giá trị \(X\) trong mảng và in ra tổng của tất cả các phần tử nằm trước vị trí đầu tiên của \(X\). Nếu \(X\) không tồn tại, in ra 0.

Input

• Dòng đầu tiên là số nguyên dương \(n\) - độ dài của dãy \(a\). \((1 \leq n \leq 100)\).
• Dòng thứ hai là \(n\) số nguyên \(a_1, a_2, a_3, \dots, a_n\) - mỗi số cách nhau một dấu cách \((|a_i| \leq 100)\).
• Dòng thứ ba là số nguyên \(X\) cần tìm.

Output

Một dòng duy nhất chứa tổng của các phần tử trước \(X\).

Example

5
1 2 3 4 5
3

3

Trường THPT Sáng Tạo muốn sửa lại hệ thống hàng rào sắt của trường thành hàng rào gỗ. Hàng rào gỗ được tạo nên bằng cách ghép \(M\) thanh gỗ có dạng hình vuông kích thước \(N \times N\) liên tục, sát vào nhau.

Để thể hiện tính "sáng tạo" của trường, nhà trường yêu cầu đội thi công phải tạo hàng rào gỗ mới có chiều dài là một số chính phương và đội thi công chỉ được sử dụng không quá \(K\) thanh gỗ.

Biết rằng: Số chính phương là bình phương của một số nguyên khác (ví dụ: \(4, 9\) là các số chính phương vì \(4 = 2^2, 9 = 3^2\)).

Yêu cầu. Hãy đếm xem có bao nhiêu giá trị của \(M\) mà đội thi công có thể sử dụng.

\InputFile

• Dòng đầu tiên chứa số nguyên dương \(K\) là số thanh gỗ tối đa \((1 \le K \le 10^{18})\).
• Dòng thứ hai chứa số nguyên dương \(N\) là chiều dài thanh gỗ \((1 \le N \le 10^9)\).

\OutputFile

• In ra một số nguyên là số lượng các số \(M\) thỏa mãn yêu cầu đề bài.

\Examples
\beginexample
\exmp
10
2

2

\exmp
28
3

3

\endexample

\Note
Ở ví dụ thứ nhất, các giá trị \(M\) có thể chọn là \(2\) và \(8\) vì \(2 \times 2 = 2^2\) và \(2 \times 8 = 4^2\).

\Scoring

• (50%) \(K \le 10^6\), \(N \le 10^3\);
• (50%) Không có ràng buộc thêm.

\endproblem

Số nguyên tố mạnh là số nguyên tố lớn hơn trung bình cộng của số nguyên tố liền trước và số nguyên tố liền sau nó.

Cho hai số nguyên dương \(L\) và \(R\) \((L < R)\). Hãy cho biết tổng của số nguyên tố mạnh lớn nhất và nhỏ nhất có trong đoạn từ \(L\) đến \(R\).

Em hãy viết chương trình thực hiện yêu cầu trên. Nếu không có thì in ra \(-1\).

Input

Dữ liệu vào: Từ tệp NGUYENTOMANH.INP chứa hai số nguyên dương L, R.

Output

Kết quả: Ghi ra tệp NGUYENTOMANH.OUT số nguyên duy nhất là kết quả thực hiện yêu cầu bài toán trên.

Example

2 20

28

2 10

-1

Scoring

• Có 50% số test ứng với 50% số điểm của bài có \(R \le 10^6\);
• Có 30% số test ứng với 30% số điểm của bài có \(R \le 10^9\);
• Có 20% số test ứng với 20% số điểm của bài có \(R \le 10^{16}\).

Cho hai số nguyên dương \(A\) và \(B\). Hãy tìm ước chung lớn nhất (Greatest Common Divisor - GCD) của chúng bằng cách áp dụng thuật toán Euclid dưới dạng đệ quy.

Input

Dòng đầu tiên chứa hai số nguyên \(A\) và \(B\) (\(1 \leq A, B \leq 10^18\)).

Output

Một số nguyên duy nhất là \(\text{GCD}(A, B)\).

Example

6 12

6