Cho một dãy gồm năm số tự nhiên tăng dần. Biết rằng dãy số này ban đầu là một cấp số cộng gồm năm phần tử, nhưng trong quá trình ghi chép đã bị bỏ sót mất một phần tử ở giữa (chắc chắn phần tử bị thiếu không phải là phần tử đầu tiên và cũng không phải là phần tử cuối cùng).

(Nhắc lại kiến thức: Cấp số cộng là một dãy số thỏa mãn điều kiện kể từ số hạng thứ hai, mỗi số hạng đều bằng số hạng đứng ngay trước nó cộng với một số không đổi gọi là công sai).

Yêu cầu: Dựa vào bốn số tự nhiên còn lại, hãy tìm và khôi phục lại giá trị của số bị viết thiếu.

Dữ liệu nhập vào từ bàn phím

• Gồm bốn số tự nhiên ~a, b, c, d~ theo đúng thứ tự xuất hiện của dãy hiện tại. Mỗi số trên một dòng.

Các số có giá trị không quá ~1000~.

Kết quả ghi ra màn hình

• In ra một số tự nhiên duy nhất là giá trị của phần tử bị viết thiếu.

Ví dụ

Ví dụ 1:

Input

2 
4 
8 
10

Output

6

Giải thích: Dãy ban đầu là cấp số cộng có công sai là 2. Dãy hoàn chỉnh gồm 5 phần tử là: 2, 4, 6, 8, 10. Số bị thiếu ở giữa là 6.

Ví dụ 2:

Input

10 
20 
30 
50

Output

40

Giải thích: Dãy ban đầu là cấp số cộng có công sai là 10. Dãy hoàn chỉnh gồm 5 phần tử là 10, 20, 30, 40, 50. Số bị thiếu ở giứa là 40.

Cho số nguyên dương ~N~.

Yêu cầu: Hãy đếm xem có bao nhiêu bộ số nguyên ~(a, b)~ thỏa mãn đồng thời các điều kiện sau:

• ~1 \le a, b \le N~.
• Tích ~a \times b~ chia hết cho ~6~.
• Hai bộ ~(a, b)~ và ~(b, a)~ được tính là khác nhau nếu ~a \neq b~.

Dữ liệu nhập vào từ bàn phím

• Gồm một số nguyên dương ~N~ (~1 \le N \le 10^9~).

Kết quả ghi ra màn hình

• Gồm một số nguyên là kết quả của bài toán. Vì kết quả có thể rất lớn nên in ra phần dư của kết quả khi chia cho 2026.

Ví dụ

Input

6

Output

15

Giải thích: Có ~15~ cặp ~(a, b)~ thỏa mãn tích ~a \times b~ chia hết cho ~6~ là: ~(1, 6), (2, 3), (2, 6), (3, 2), (3, 4), (3, 6), (4, 3), (4, 6), (5, 6), (6, 1), (6, 2), (6, 3), (6, 4), (6, 5), (6, 6)~.

Ràng buộc:

• Có 70% số test ứng với 70% số điểm: ~N \le 10^3~;
• 30% số test còn lại ứng với 30% số điểm không có ràng buộc gì thêm.

Cho một mảng gồm ~n~ phần tử, phần tử ở vị trí thứ ~i~ có giá trị là ~a_i~.

Yêu cầu: Hãy tìm hai vị trí ~L~ và ~R~ thỏa mãn điều kiện ~1 \le L < R \le n~ sao cho độ chênh lệch (giá trị tuyệt đối) giữa tổng các phần tử từ vị trí đầu tiên đến vị trí ~L~ và tổng các phần tử từ vị trí ~R~ đến vị trí cuối cùng trong mảng là bé nhất. Nói cách khác, cần tìm ~L~,~R~ để biểu thức sau đạt giá trị nhỏ nhất: ~|\sum_{i=1}^{L}a_{i} - \sum_{j=R}^{n}a_{j}|~.

Dữ liệu nhập vào từ bàn phím

• Dòng thứ nhất ghi một số nguyên dương ~n~ thể hiện số lượng phần tử của mảng.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~, các số được ghi cách nhau bởi ít nhất một khoảng trắng.

Kết quả ghi ra màn hình

• In ra trên một dòng duy nhất một số không âm là độ chênh lệch tuyệt đối nhỏ nhất tìm được.

Ví dụ

Input

5
1 2 3 4 5

Output

1

Giải thích: Ta có mảng gồm ~5~ phần tử. Nếu chọn vị trí ~L = 3~ và ~R = 5~ (thỏa mãn ~L < R~), ta có:

• Tổng phần đầu (từ ~1~ đến ~L~): ~a_1 + a_2 + a_3 = 1 + 2 + 3 = 6~.
• Tổng phần cuối (từ ~R~ đến ~n~): ~a_5 = 5~.
• Độ chênh lệch tuyệt đối: ~|6 - 5| = 1~. Đây là mức chênh lệch nhỏ nhất có thể đạt được trong tất cả các cách chọn ~L~ và ~R~.

Ràng buộc:

• Có 60% số test ứng với 60% số điểm: ~n \le 2000~; ~|a_i| \le 10^9~.
• 40% số test còn lại ứng với 40% số điểm: ~n \le 10^6~; ~|a_i| \le 10^9~.

Cho một hàng ngang gồm ~n~ chiến binh. Ban đầu, chiến binh thứ ~i~ có mức sinh lực là ~a_i~.

Bạn được phép tung ra các đợt kỹ năng (hoặc không dùng lần nào). Mỗi đợt, bạn chọn một khoảng liên tiếp từ vị trí ~l~ đến ~r~ (~1 \le l \le r \le n~) và làm giảm đi ~1~ điểm sinh lực của tất cả chiến binh nằm trong khoảng này. Lượng tài nguyên tiêu tốn cho mỗi đợt kỹ năng là ~m~.

Sau khi mọi đợt kỹ năng kết thúc, nếu sinh lực của chiến binh thứ ~i~ giảm xuống ~0~ hoặc thấp hơn, bạn sẽ thu về một lượng phần thưởng là ~b_i~ (chú ý rằng ~b_i~ có thể mang giá trị âm). Phần thưởng từ mỗi chiến binh chỉ được cộng đúng một lần duy nhất.

Yêu cầu: Tìm phương án sử dụng kỹ năng sao cho: (Tổng phần thưởng thu được) - (Tổng tài nguyên tiêu tốn) đạt mức cực đại.

Dữ liệu nhập vào từ bàn phím

Gồm nhiều bộ dữ liệu (test cases).

• Dòng đầu tiên ghi số lượng test case ~T~.
• Với mỗi test case:
  • Dòng thứ nhất chứa hai số nguyên dương ~n~ và ~m~.
  • ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i~ và ~b_i~.

Kết quả ghi ra màn hình

• Với mỗi test case, in ra một số nguyên duy nhất là giá trị lớn nhất của (tổng phần thưởng - tổng tài nguyên) trên một dòng.

Ví dụ

Input

1
5 1
1 3
2 5
1 4
3 3
5 1

Output

12

Giới hạn

Gọi ~\sum n~ là tổng các giá trị ~n~ của tất cả các bộ dữ liệu trong file.

• ~1 \le T \le 5 \times 10^5~.
• ~1 \le n~; ~\sum n \le 5 \times 10^5~.
• ~1 \le m \le 10^9~.
• ~1 \le a_i \le 10^9~; ~-10^9 \le b_i \le 10^9~.

Ràng buộc

• Có 20% số test ứng với 20% số điểm: ~\sum n \le 20~, ~a_i = 1~ với mọi ~i~.
• Có 20% số test ứng với 20% số điểm: ~b_i \ge 0~ với mọi ~i~.
• Có 20% số test ứng với 20% số điểm: ~\sum n \le 300~.
• Có 20% số test ứng với 20% số điểm: ~\sum n \le 3000~.
• 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.