Cho N tấm vé, trong đó tấm vé thứ i ghi số nguyên a_i. Hai tấm vé ở vị trí i và j tạo thành một cặp hợp lệ nếu i < j và tổng a_i + a_j chia hết cho K.

Hãy đếm số cặp hợp lệ.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên N và K.
• Dòng thứ hai chứa N số nguyên a_1, a_2, ..., a_N.

Dữ liệu ra

In ra một số nguyên là số cặp hợp lệ.

Giới hạn

• 1 ≤ N ≤ 2·10^5
• 1 ≤ K ≤ 2·10^5
• 1 ≤ a_i ≤ 10^9

Ví dụ

Input

5 4
1 3 5 2 6

Output

3

Giải thích

Các cặp vị trí hợp lệ là (1, 2), (2, 3) và (4, 5).

Phân nhóm điểm

1. (10 điểm) N ≤ 100.
2. (20 điểm) N ≤ 5·10^3.
3. (30 điểm) N ≤ 2·10^5, K ≤ 200.
4. (40 điểm) Không có giới hạn bổ sung.

Các test được chấm độc lập; điểm bài là tổng điểm của các test đúng.

Có N trạm, đánh số từ 1 đến N. Ban đầu, tải bảo trì tại mỗi trạm bằng 0.

Có Q lịch bảo trì. Lịch thứ i tăng tải tại mọi trạm trong đoạn [l_i, r_i] thêm x_i đơn vị.

Sau khi thực hiện tất cả lịch, hãy tìm tải lớn nhất và chỉ số nhỏ nhất của một trạm đạt tải đó.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên N và Q.
• Mỗi dòng trong Q dòng tiếp theo gồm ba số nguyên l_i, r_i, x_i, mô tả một lịch bảo trì.

Dữ liệu ra

In hai số nguyên: tải lớn nhất và chỉ số nhỏ nhất của trạm đạt tải lớn nhất.

Ràng buộc

• 1 ≤ N ≤ 200000.
• 0 ≤ Q ≤ 200000.
• 1 ≤ l_i ≤ r_i ≤ N.
• 1 ≤ x_i ≤ 10^9.

Phân nhóm điểm

1. (10 điểm) N, Q ≤ 2000.
2. (20 điểm) Mọi lịch đều tác động lên đúng một trạm (l_i = r_i).
3. (30 điểm) Với mọi lịch, l_i = 1 hoặc r_i = N.
4. (40 điểm) Không có ràng buộc nào khác.

Ví dụ

Input

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

Output

5 1

Sau khi áp dụng các lịch, tải tại các trạm lần lượt là 5, 5, 5, 5, 3. Tải lớn nhất là 5, đạt ở nhiều trạm; trạm có chỉ số nhỏ nhất là trạm 1.

Có ~N~ vị trí được xếp theo thứ tự trên một đường tròn. Vị trí thứ ~i~ mang giá trị ~a_i~. Trong dãy có đúng ~N/2~ giá trị khác nhau, mỗi giá trị xuất hiện đúng hai lần.

Với mỗi giá trị, nối hai vị trí mang giá trị đó bằng một đoạn thẳng. Hãy tính số cặp đoạn thẳng giao nhau bên trong đường tròn. Mỗi cặp đoạn giao nhau chỉ được tính một lần.

Cấu hình Input

• Dòng đầu tiên chứa số nguyên chẵn ~N~ ~(2 ≤ N ≤ 2 · 10^6)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, ..., a_N~ ~(1 ≤ a_i ≤ N/2)~.
• Mỗi giá trị từ ~1~ đến ~N/2~ xuất hiện đúng hai lần.

Cấu hình Output

In ra một số nguyên duy nhất là số cặp đoạn thẳng giao nhau. Kết quả có thể vượt quá phạm vi 32-bit; hãy dùng số nguyên 64-bit.

Ví dụ

Input

8
1 2 1 3 2 4 3 4

Output

3

Giải thích

Các cặp giá trị ~(1, 2)~, ~(2, 3)~ và ~(3, 4)~ tạo thành những đoạn thẳng giao nhau. Các cặp giá trị còn lại không giao nhau.

Subtasks

• Subtask 1 (10 điểm): ~N ≤ 2 · 10^3~.
• Subtask 2 (20 điểm): ~N ≤ 2 · 10^5~.
• Subtask 3 (30 điểm): ~N ≤ 10^6~.
• Subtask 4 (40 điểm): ~N ≤ 2 · 10^6~.

Cho một bảng gồm H hàng và W cột ô lục giác đều. Các ô được đánh số bằng cặp tọa độ (r, c), với 1 ≤ r ≤ H và 1 ≤ c ≤ W. Hai ô được xem là kề cạnh nếu tọa độ của chúng là một trong các cặp sau (và cả hai ô đều thuộc bảng):

• (r, c) và (r, c + 1);
• Nếu r lẻ: (r, c) và (r + 1, c), hoặc (r + 1, c - 1);
• Nếu r chẵn: (r, c) và (r + 1, c), hoặc (r + 1, c + 1).

Có hai loại mảnh ghép:

• Mảnh loại 2 phủ đúng hai ô kề cạnh.
• Mảnh loại 3 phủ đúng ba ô, trong đó từng cặp ô đều kề cạnh (tạo thành một tam giác nhỏ).

Các mảnh có thể xoay tùy ý. Hãy đếm số cách lát kín bảng sao cho mỗi ô được phủ đúng một lần. Hai cách lát được xem là khác nhau nếu có ít nhất một ô thuộc các mảnh khác nhau.

Vì kết quả có thể rất lớn, hãy in kết quả modulo 1 000 000 007.

Dữ liệu vào

Một dòng gồm hai số nguyên H và W.

Dữ liệu ra

In ra số cách lát kín bảng modulo 1 000 000 007.

Ràng buộc

• 1 ≤ H ≤ 6
• 1 ≤ W ≤ 10^18

Phân nhóm điểm

1. (10 điểm) H = 1, W ≤ 10^5.
2. (20 điểm) H ≤ 2, W ≤ 10^5.
3. (30 điểm) H ≤ 4, W ≤ 10^18.
4. (40 điểm) H ≤ 6, W ≤ 10^18.

Ví dụ

Input

2 3

Output

4

Trong một khu vực có lưới ô vuông, mỗi ô có một độ cao. Xe chỉ được đi sang một ô kề cạnh (trên, dưới, trái hoặc phải). Nếu xe đi từ ô có độ cao a sang ô có độ cao b, thời gian di chuyển là |a - b|.

Xe tuần tra bắt đầu ở ô (x_1, y_1), có T đơn vị nhiên liệu. Xe tiếp nhiên liệu bắt đầu ở ô (x_2, y_2) và không bị giới hạn nhiên liệu. Quán mì Udon nằm ở ô (x_3, y_3).

Hai xe bắt đầu di chuyển tại thời điểm 0; trong mỗi tọa độ (x, y), x là hàng và y là cột.

Cả hai xe có thể dừng chờ tại một ô. Thời gian chờ được tính vào thời gian đến quán nhưng không tiêu hao nhiên liệu. Xe tuần tra tiêu hao nhiên liệu bằng đúng thời gian di chuyển. Khi hai xe cùng dừng tại một ô, xe tiếp nhiên liệu có thể nạp thêm D đơn vị nhiên liệu cho xe tuần tra ngay lập tức. Việc nạp nhiên liệu được thực hiện nhiều nhất một lần; xe tuần tra có thể được nạp kể cả khi đã hết nhiên liệu.

Trong lúc di chuyển giữa hai ô, xe không được xem là đang đứng trên ô nào. Vì vậy, hai xe chỉ có thể tiếp nhiên liệu khi cùng đứng trên một ô, không thể tiếp nhiên liệu khi gặp nhau giữa đường. Hai xe không cản trở nhau.

Hãy tìm thời gian nhỏ nhất tính từ lúc bắt đầu để xe tuần tra đến quán. Nếu không thể đến quán, in -1.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên H, W — số hàng và số cột.
• H dòng tiếp theo, mỗi dòng gồm W số nguyên h[i][j] — độ cao của các ô.
• Dòng tiếp theo gồm sáu số nguyên x_1 y_1 x_2 y_2 x_3 y_3 — tọa độ xe tuần tra, xe tiếp nhiên liệu và quán Udon.
• Dòng cuối gồm hai số nguyên T, D — nhiên liệu ban đầu và lượng nhiên liệu được nạp thêm.

Các tọa độ được đánh số từ 1.

Dữ liệu ra

In thời gian nhỏ nhất để xe tuần tra đến quán; nếu không thể đến, in -1.

Ràng buộc

• 1 ≤ H, W ≤ 1000
• 0 ≤ h[i][j] ≤ 10^9
• 1 ≤ x_1, x_2, x_3 ≤ H
• 1 ≤ y_1, y_2, y_3 ≤ W
• 0 ≤ T, D ≤ 10^18

Phân nhóm điểm

1. (10 điểm) H, W ≤ 10.
2. (20 điểm) H, W ≤ 30.
3. (30 điểm) H, W ≤ 250.
4. (40 điểm) H, W ≤ 1000.

Ví dụ

Input

2 2
1 5
5 9
1 1 2 1 2 2
4 4

Output

8

Giải thích

Xe tuần tra đi từ (1, 1) đến (2, 1) mất 4 đơn vị thời gian. Xe tiếp nhiên liệu đã ở đó nên hai xe gặp nhau tại thời điểm 4; xe tuần tra được nạp thêm 4 đơn vị nhiên liệu. Sau đó, xe đi đến quán ở (2, 2), mất thêm 4 đơn vị. Tổng thời gian là 8.

Ví dụ 2

Input

8 8
0 1 2 3 4 5 6 7
10 11 12 13 14 15 16 17
20 21 22 23 24 25 26 27
30 31 32 33 34 35 36 37
40 41 42 43 44 45 46 47
50 51 52 53 54 55 56 57
60 61 62 63 64 65 66 67
70 71 72 73 74 75 76 77
1 1 8 1 8 8
43 34

Output

77

Một phương án tối ưu: xe tuần tra và xe tiếp nhiên liệu gặp nhau tại ô (5,4) vào thời điểm 43. Xe tiếp nhiên liệu đến đó sớm hơn và chờ. Sau khi nhận thêm 34 đơn vị nhiên liệu, xe tuần tra đi đến quán, đến nơi vào thời điểm 77.