Cho ba số nguyên dương ~a, b, n~.

Yêu cầu: Tìm số nguyên dương ~d~ lớn nhất nhỏ hơn hoặc bằng ~n~ mà chia hết cho cả ~2~ số ~a~ và ~b~.

Input

Một dòng duy nhất chứa ~3~ số nguyên dương ~a, b, n~ ~(a, b \le 10^9 , n ≤ 10^{12})~. Các số ghi cách nhau bởi một dấu cách.

Output

Một số nguyên dương ~d~ thỏa mãn yêu cầu của bài toán, nếu không có số nguyên dương ở thỏa mãn thì ghi ra -1.

Subtask:

• Có ~50\%~ số test ứng với ~50\%~ số điểm của bải thỏa mãn điều kiện: ~n \le 10^6~;
• ~50\%~ số test còn lại ứng với ~50\%~ số điểm không có ràng buộc gì thêm.

Sample Input

2 7 30

Sample Output

28

Giải thích

Số nguyên dương lớn nhất nhỏ hơn hoặc bằng ~30~ mà chia hết cho ~2~ và ~7~ là ~28~

Cho ba số nguyên dương ~L, R, k~.

Yêu cầu: Hãy tỉnh tổng tất cả các số nguyên dương thuộc đoạn ~[L, R]~ mà không chia hết cho ~k~.

Input

Một dòng duy nhất chứa ~3~ số nguyên dương ~L,R,k~ ~(L \le R \le 10^9; k ≤ 10^9)~, các số ghi cách nhau bởi một dấu cách.

Output

Gồm một số nguyên duy nhất là kết quả của bài toán.

Subtask

• Có ~80\%~ số test ứng với ~80\%~ số điểm của bài thỏa mãn điều kiện: ~L ≤ R ≤ 10^6~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm không có ràng buộc gì thêm.

Sample Input

2 6 3

Sample Output

11

Giải thích

Từ ~2~ đến ~6~ có các số không chia hết cho ~3~ là: ~2, 4, 5~. Tổng là: ~2 + 4 + 5 = 11~

Cho dãy ~A~ gồm ~n~ số nguyên dương ~a_1, a_2,... a_n~

Cặp số ~(a_i, a_j)~ được gọi là cặp số chia hết cho nhau nếu thỏa mãn hai điều kiện sau:

• ~1 \le i < j < n~;

• ~a_i~ chia hết cho ~a_j~ hoặc ~a_j~ chia hết cho ~a_i~ .

Yêu cầu: Tìm số lượng cặp số chia hết cho nhau có trong dãy ~A~.

Input

Dòng thứ nhất chứa số nguyên dương ~n~ ~(2 \le n \le 10^6)~;

Dòng thứ hai chứa n số nguyên dương ~a_1, a_2,..., a_n~ ~( a_i \le 10^6,1 \le i \le n)~.Các số trên cùng một dòng ghi cách nhau một dấu cách.

Output

Một số nguyên duy nhất là số lượng cặp số chia hết cho nhau có trong dãy ~A~.

Subtask

• Có ~60\%~ số test ứng với ~60\%~ số điểm của bài thỏa mãn điều kiện: ~n \le 10^3~

• ~40\%~ số test còn lại ứng với ~40\%~ số điểm không có ràng buộc gì thêm.

Sample Input

4
4 3 2 6

Sample Output

3

Giải thích

Có ~3~ cặp số thỏa mãn: ~(4, 2)~, ~(3, 6)~, ~(2, 6)~.

Cho một dây ~A~ gồm n số nguyên ~a_1, a_2,..., a_n~.

Đoạn con ~a_i ,a_{i + 1} ,...,a_j~ ~(1 \le i \le j \le n)~ được gọi là đoạn con liên tiếp từ phần tử thứ ~i~ đến phần từ thứ ~j~ của dãy ~A~, có độ dài là ~j - i + 1~ và tổng là ~a_i +a_{i + 1} +...+a_j~ .

Yêu cầu: Hãy tìm tổng lớn nhất của đoạn con liên tiếp có độ dài từ ~p~ đến ~q~.

Input:

Dòng đầu tiên chứa số nguyên dương ~n~ ~(n \le 10 ^ 6)~

Dòng thứ ~2~ chứa ~2~ số nguyên ~p, q~ ~(1 \le p \le q \le n)~

Dòng thứ ~3~ chứa ~n~ số nguyên ~a_1, a_2,..., a_n~ ~( |a_i| \le 10^9,1 \le i \le n)~. Các số trên cùng một dòng ghỉ cách nhau một dấu cách.

Output

In ra một số nguyên duy nhất là tổng lớn nhất tìm được.

Subtask

• Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~n \le 10^2~
• Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: ~n \le 10 ^ 3~
• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thỏa mãn điều kiện: ~n \le 10 ^ 5~
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm củn bải thỏa mãn điều kiện: ~n > 10 ^ 5~ và ~p = q~

Sample Input

5
2 3
3 -2 5 -1 6

Sample Output

10

Giải thích

Các đoạn con liên tiếp có độ dài bằng ~2~:

• ~\{3, -2 \}~ có tổng bằng ~1~
• ~\{-2, 5 \}~ có tổng bằng ~3~
• ~\{5, -1 \}~ có tổng bằng ~4~
• ~\{-1, 6 \}~ có tổng bằng ~5~

Các đoạn con liên tiếp có độ dài bằng ~3~:

• ~\{3, -2, 5\}~ có tổng bằng ~6~
• ~\{-2, 5, -1\}~ có tổng bằng ~2~
• ~\{5, -1, 6\}~ có tổng bằng ~10~ (lớn nhất)