Cho 3 số nguyên dương ~n~, ~m~ và ~p~, có giá trị không vượt quá ~10^9~

Yêu cầu: Hãy tìm số nguyên ~x~ lớn nhất thoả mãn các điều kiện sau:

• ~x \le n~
• ~x = k * m + p~, với ~k~ là số nguyên

INPUT

Gồm 3 số nguyên dương ~n~, ~m~ và ~p~

OUTPUT

Số ~x~ thoả mãn đề bài

SAMPLE INPUT

60 5 9

SAMPLE OUTPUT

59

Giải thích: ~59 = 10 * 5 + 9~

Cho hai số nguyên dương ~a~ và ~b~, có giá trị không vượt quá ~10^9~

Yêu cầu: Tìm số cặp số nguyên dương ~(x, y)~ thoả mãn ~gcd(a, b) = gcd(x, y)~ và ~lcm(a, b) = lcm(x, y)~.

INPUT

Hai số nguyên dương ~a~ và ~b~

OUTPUT

Số cặp số nguyên dương ~(x, y)~ thoả mãn đề bài

SAMPLE INPUT

6 8

SAMPLE OUTPUT

4

Giải thích: Có ~4~ cặp ~(x, y)~ thoả mãn đề bài là các cặp: ~(6, 8)~, ~(8, 6)~, ~(2, 24)~, ~(24, 2)~

Cho số nguyên dương ~n~ và ~n~ số nguyên dương ~a_1, a_2, ..., a_n~.

Tìm vị trí ~k~ sao cho chênh lệnh giữa tổng từ ~a_1~ đến ~a_k~ và tổng từ ~a_{k+1}~ đến ~a_n~ là nhỏ nhất ~(1 \le k < n)~.

Input

Dòng 1: Số nguyên dương ~n~ ~(n \le 10^5)~

Dòng 2: ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i<=10^9~)

Output

Ghi ra 2 số nguyên là chênh lệnh nhỏ nhất và vị trí ~k~. Nếu có nhiều vị trí ~k~ thỏa mãn thì chọn ~k~ nhỏ nhất.

Sample

Input

4
1 2 3 5

Output

1 3