Có một ông phú hộ rất giàu có, tài sản của ông ta là một dãy số nguyên liên tiếp bắt đầu là a và kết thúc là b . Khi đến tuổi già, trước khi qua đời ông muốn chia tài sản của mình cho 2 người con. Người con thứ 1 được nhận các tài sản có giá trị là các số chẵn. Người con thứ 2 được nhận các tài sản có giá trị là số lẻ. Nhưng ông phú hộ vẫn chưa biết trước được ai sẽ là gười nhận được nhiều hơn, và nhiều hơn bao nhiêu.

Yêu cầu

Hãy xác định trong 2 người con, ai sẽ là người nhận được nhiều tài sản hơn, và nhiều hơn người còn lại là bao nhiêu?

Input

Hai số nguyên dương a,b (a<b≤10^9)</p>

Output

Hai số nguyên trên 2 dòng:

• Số thứ nhất ghi số 1 nếu người con thứ nhất được nhiều tài sản hơn, ngược lại ghi số 2.

• Số thứ hai ghi độ chênh lệch tài sản giữa 2 người con.

Examples

Input

3 10

Output

1
4

Input

4 13

Output

2
5

Trong một cuộc thi vui để học, Nam là người đạt điểm cao nhất trong số các thí sinh. Phần thưởng của Nam là 2 món quà được chọn từ N món quà của BTC. Các món quà của BTC là dãy số nguyên dương a1,a2,...,aN , món quà thứ i có giá trị là ai . Nam được chọn ra 2 món quà tùy ý khác nhau sao cho tổng giá trị các món quà còn lại là một số chẵn.

Yêu cầu

Hãy cho biết Nam có bao nhiêu cách chọn khác nhau?

Input

• Dòng đầu tiên là số nguyên dương N (N≤10^9)

• N dòng tiếp theo, mỗi dòng là một số nguyên dương ai (ai≤10^9)

Output

Một số nguyên là số cách chọn 2 món quà thỏa mãn yêu cầu đề bài.

Example

Input

5
1
2
3
4
5

Output

6

Note

Các cách chọn là: (1,2) , (1,4) , (2,3) , (2,5) , (3,4) , (4,5) .

Sau khi được tham quan nhiều địa điểm, các bạn được vui chơi và thi đua cùng các bạn qua trò chơi đổ nước vào chai. Các điểm lấy nước được xếp trên cùng một hàng, được đánh số thứ tự lần lượt từ 1 đến N . Vị trí thứ i có lượng nước là ai (ai là một số nguyên dương, i=1,2,...,N ). Thể lệ trò chơi là người lấy nước lần lượt từ điểm số 1 đến điểm thứ N và không được lấy nước ở 2 điểm liền nhau. Đội chiến thắng là đội có số lượng nước nhiều nhất. Bạn hãy giúp đội mình lấy ra lượng nước nhiều nhất nhé.

Yêu cầu

Hãy cho biết tổng lượng nước nhiều nhất có thể lấy được?

Input

• Dòng đầu tiên là số nguyên dương N (N≤10^5)

• N dòng tiếp theo, dòng thứ i chứa số nguyên dương ai (ai≤10^9) .

Output

Tổng lượng nước nhiều nhất có thể lấy được.

Example

Input

5
1
5
2
4
6

Output

11