khoi1503 đang nghiên cứu mực nước biển ở hành tinh Sao hoả. Sau nhiều ngày theo dõi, khoi1503 nhận thấy rằng quy luật của mực nước biển là: mực nước biển của một ngày bất kì bằng trung bình cộng mực nước biển của ngày hôm trước và ngày hôm sau. Dựa vào ghi chép mực nước biển hai ngày đầu của khoi1503, hãy tính toán mực nước biển ngày thứ N.

Input

• Dòng 1: chứa 2 số nguyên b,a là mực nước biển 2 ngày đầu ~(-100 \le a,b \le 100)~. Số a là mực nước ngày thứ nhất, số b là mực nước ngày thứ 2.
• Dòng 2: chứa số nguyên dương ~N (3 \le N \le 10^{12})~.

Output

• Mực nước biển ngày thứ N.

Input

1 2
3

Output

3

Input

3 1
3

Output

-1

Cho dãy số ~A~ gồm ~n~ phần tử nguyên dương ~A_1,A_2,…,A_n~. Mỗi phần tử có giá trị không vượt quá ~10^9~ và ~1<n≤5000~. Một bộ ba số được gọi là bộ số tam giác, nếu ba số này tạo thành ba cạnh của một tam giác nào đó.</p>

Yêu cầu: Hãy đếm xem trong dãy ~A~ có bao nhiêu bộ số tam giác ~(A_i,A_j,A_k~) với ~i~,~j~,~k~ đôi một khác nhau.

Dữ liệu vào

• Dòng đầu là số ~n~.
• Dòng tiếp theo là các phần tử của dãy ~A~, mỗi phần tử cách nhau một dấu cách.

Dữ liệu ra:

• Ghi ra số lượng bộ số tam giác.

Scoring

Subtask 1: (30% số điểm): ~n≤100~.

Subtask 2: (30% số điểm): ~100<n≤1000~.</p>

Subtask 3: (40% số điểm): ~1000<n≤5000~.</p>

Example

Input

5
4 3 1 5 7 

Output

3

Dữ liệu được nhập từ bàn phím

Htmaths2512 sống ở Sao Hoả, cậu có thể thọ tỷ Nam Sơn. Htmaths2512 có một người Bố thật tuyệt vời, cậu muốn lớn thật nhanh để có thể làm được những việc như bố.

Em hãy lập trình nhập vào 2 số nguyên dương a, b lần lượt là số tuổi của bố và Htmaths2512 hiện tại, tính và thông báo ra màn hình bao nhiêu năm nữa tuổi bố sẽ gấp đôi tuổi Htmaths2512.

Input:

• Ghi 2 số nguyên dương a, b.

Output:

• In ra số nguyên dương N là số năm để tuổi bố gấp đôi tuổi Ht_maths2512.

Input:

30 5

Input:

20

constraint:

%: ~1 \le a,b \le 10^{18}~

Vừa gà vừa chó

Bó lại cho tròn

Tổng n con

Và k chân chẵn

Yêu cầu: Tính số gà, số chó biết n, k là 2 số nguyên dương cho trước.

Input:

• Nhập vào 2 số nguyên dương n, k.

Output:

• Ghi 2 số nguyên x,y tương ứng là số gà số chó tìm được. Nếu không tìm được x,y thỏa mãn thì ghi -1.

Example:

Input:

36 100

Output:

22 14

Constraints:

~0 < n < k < 2*10^9~