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.

Cho một bộ sưu tập gồm ~4 \times n~ viên sỏi. Viên sỏi thứ ~i~ (~1 \le i \le 4n~) có trọng lượng là ~m_i~ và được sơn màu ~c_i~. Biết rằng có tất cả ~n~ loại màu khác nhau (được đánh số từ ~1~ đến ~n~), và cấu trúc bộ sưu tập đảm bảo rằng mỗi loại màu đều có chính xác ~4~ viên sỏi.

Yêu cầu: Hãy phân chia toàn bộ ~4 \times n~ viên sỏi này thành hai tập hợp riêng biệt sao cho thỏa mãn đồng thời hai điều kiện sau:

1. Mỗi tập hợp phải chứa đúng ~2~ viên sỏi của từng loại màu.
2. Độ chênh lệch (giá trị tuyệt đối của hiệu số) giữa tổng trọng lượng của các viên sỏi trong tập hợp thứ nhất và tổng trọng lượng của các viên sỏi trong tập hợp thứ hai là nhỏ nhất có thể.

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

• Dòng đầu tiên chứa một số nguyên dương ~n~.
• ~4 \times n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~m_i~ và ~c_i~ thể hiện trọng lượng và mã màu của viên sỏi thứ ~i~ (~m_i \le 4n~; ~1 \le c_i \le n~).

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

• In ra trên một dòng duy nhất gồm ~2 \times n~ số nguyên là số thứ tự (chỉ số) của các viên sỏi được xếp vào tập hợp thứ nhất, các số cách nhau bởi một khoảng trắng. (Lưu ý: Nếu có nhiều phương án chia mang lại cùng một độ chênh lệch nhỏ nhất, bạn có thể in ra bất kỳ phương án nào hợp lệ).

Ví dụ

Input

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

Output

1 4 5 6

Giải thích: Có tổng cộng ~8~ viên sỏi (~n = 2~). Cần chia làm 2 tập hợp, mỗi tập hợp có đúng ~2~ viên sỏi màu ~1~ và ~2~ viên sỏi màu ~2~. Nếu chọn tập hợp thứ nhất gồm các viên sỏi ở vị trí ~1, 4, 5, 6~:

• Về màu sắc: viên số ~1, 4~ có màu ~1~; viên số ~5, 6~ có màu ~2~ (thỏa mãn mỗi màu có ~2~ viên).
• Tổng trọng lượng tập hợp 1: ~m_1 + m_4 + m_5 + m_6 = 1 + 4 + 1 + 8 = 14~.
• Tập hợp thứ hai sẽ chứa các viên sỏi còn lại là ~2, 3, 7, 8~.
• Tổng trọng lượng tập hợp 2: ~m_2 + m_3 + m_7 + m_8 = 2 + 3 + 4 + 5 = 14~. Độ chênh lệch giữa hai tập hợp là ~|14 - 14| = 0~. Đây là mức chênh lệch nhỏ nhất.

Ràng buộc:

• Có 50% số test ứng với 50% số điểm: ~n \le 30~.
• 50% số test còn lại ứng với 50% số điểm: ~n \le 30000~ và có đặc tính ~m_i = i~ với mọi viên sỏi thứ ~i~.