Bài tập

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

Nhật Trần là một cậu bé có niềm đam mê đặc biệt với những con số. Một ngày nọ, cậu được Chần
Huàng kể về những con số kỳ diệu. Theo lời kể, đó là những số:

• lớn hơn \(A\),
• nhỏ hơn \(B\),
• chia hết cho \(2\),
• nhưng không chia hết cho \(3\).

Những con số này khiến Nhật Trần vô cùng tò mò. Cậu tự hỏi: Tổng của tất cả các số kỳ diệu
đó là bao nhiêu?

Input

Dữ liệu vào MAGIC.INP:

• Gồm một dòng chứa hai số nguyên dương \(A\) và \(B\) \((1 \leq A \leq B \leq 10^9)\).

Output

Dữ liệu ra MAGIC.OUT:

• In ra một số nguyên duy nhất là kết quả bài toán.

Example

1 10

14

Scoring

Ràng buộc:

• Subtask \(1\) (\(60\%\)): \(A \leq B \leq 10^6\).
• Subtask \(2\) (\(40\%\)): Không có ràng buộc thêm.

Cho số nguyên dương \(N\). Hãy tính giá trị của biểu thức \(S(N)\) được định nghĩa như sau:

Hãy viết hàm đệ quy để tính giá trị của \(S(N)\).

Input

Một số nguyên dương \(N\) (\(1 \leq N \leq 100\)).

Output

Một số thực là giá trị của \(S(N)\), làm tròn đến 4 chữ số thập phân.

Example

1

1.0000

2

1.7321

3

2.1753

Cho số nguyên dương \(N\). Hãy tính tổng \(S(N) = 1 + 2 + 3 + \dots + N\) bằng phương pháp đệ quy.

Input

Một số nguyên dương \(N\) (\(1 \leq N \leq 1000\)).

Output

Một số nguyên duy nhất là giá trị của \(S(N)\).

Example

5

15