Thành phố vừa xây dựng tuyến tàu điện ngầm đầu tiên với tổng cộng \(N\) ga và giới thiệu một cách thanh toán phí đi lại mới. Thay vì chỉ trả tiền cho một vé và thực hiện một hành trình bất kỳ, giá tiền bạn phải trả giờ đây dựa trên thẻ vào ga (entry cards).

Khi vào tàu điện ngầm, mỗi hành khách nhận một thẻ vào ga, trên đó ghi rõ ga mà hành khách đã vào. Khi rời khỏi tàu điện ngầm, hành khách phải nộp lại thẻ vào ga và bị tính phí tùy thuộc vào khoảng cách (tính bằng số ga đã đi qua) giữa ga vào ghi trên thẻ và ga ra nơi thẻ được nộp lại.

Số tiền thanh toán phụ thuộc vào khoảng cách giữa các ga này như sau:

• Nếu chúng là cùng một ga, bạn không phải trả tiền;
• Nếu chúng là hai ga kề nhau, bạn trả \(N\) bảng;
• Nếu khoảng cách là hai ga, bạn trả \(2N - 1\): phí \(N\) cho chặng đầu tiên và \(N - 1\) cho chặng thứ hai;
• Ga thứ ba có phí là \(N - 2\) (vì vậy bạn trả \(3N - 3\) cho một chuyến đi dài ba ga), ga thứ tư là \(N - 3\), và ga thứ \(i\) là \(N + 1 - i\);
• Như vậy, nếu bạn đi từ đầu này đến đầu kia của tàu điện ngầm (khoảng cách \(N - 1\) ga), bạn trả 2 bảng cho ga cuối cùng đã đi qua, và tổng cộng là \((N^2 + N - 2) / 2\).

Sau khi áp dụng hệ thống này, thành phố nhận thấy lợi nhuận của họ không lớn như mong đợi. Họ nhận ra điều này có thể là do mọi người hoán đổi thẻ vào ga cho nhau — ví dụ, nếu một người vào ở ga \(A\), đi hai ga đến \(B\) và ra ngoài, trong khi một người khác vào ở ga \(B\), đi ba ga đến \(C\) và ra ngoài, thông thường họ sẽ trả tổng cộng là \((2N - 1) + (3N - 3) = 5N - 4\). Nhưng nếu hai người hoán đổi thẻ vào ga tại ga \(B\), thì người thứ nhất sẽ đi miễn phí (vì anh ta nộp lại thẻ ghi ga vào là \(B\) trong khi đang ra ở ga \(B\), do đó khoảng cách ghi nhận là 0); trong khi người thứ hai sẽ ra ở ga \(C\) và nộp lại thẻ ghi ga vào là \(A\), cách đó 5 ga, và trả \(5N - 10\). Thành phố bị thiệt hại ròng là 6 bảng!

Thành phố hiện muốn biết họ có thể mất bao nhiêu tiền nếu việc làm này trở nên phổ biến. Chúng ta sẽ chỉ xem xét một chiều (từ ga 1 đến ga \(N\), đi qua tất cả các ga theo thứ tự) của tàu điện ngầm và chỉ một đoàn tàu trên tuyến này. Chúng ta giả định một hành khách đi từ \(o\) đến \(e\) nhận được thẻ vào ga tại \(o\), có thể hoán đổi thẻ của mình bất kỳ số lần nào với bất kỳ hành khách nào khác ở bất kỳ đâu giữa \(o\) và \(e\), bao gồm cả việc hoán đổi với những người rời đi tại \(o\) hoặc những người vào tại \(e\), và sau đó rời tàu tại \(e\) với một thẻ vào ga nào đó (bắt buộc phải nộp lại một thẻ vào ga để ra khỏi tàu điện ngầm). Chúng ta cũng giả định hành khách sẽ không rời tàu giữa chừng (nghĩa là sẽ không nộp lại thẻ hiện có và lấy thẻ mới).

Bạn được cung cấp bản đồ lưu lượng giao thông (xác định có bao nhiêu hành khách đi chuyến tàu này từ ga nào đến ga nào), và bạn nên tính toán tổn thất tài chính của thành phố, giả định hành khách hoán đổi thẻ của họ để tối đa hóa tổn thất này.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ test chứa số \(N\) điểm dừng (các điểm dừng được đánh số từ 1 đến \(N\)) và số \(M\) cặp điểm đi - điểm đến được cung cấp. \(M\) dòng tiếp theo mỗi dòng chứa ba số: điểm dừng bắt đầu \(o_i\), điểm dừng kết thúc \(e_i\) và \(p_i\): số lượng hành khách thực hiện hành trình này.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là tổng tổn thất mà thành phố có thể quan sát được do hoán đổi vé, lấy modulo 1000002013.

Ràng buộc

• \(1 \le T \le 20\).
• \(1 \le o_i < e_i \le N\).

Phân nhóm

• Small dataset (Test set 1):
• \(2 \le N \le 100\).
• \(1 \le M \le 100\).
• \(1 \le p_i \le 100\).
• Large dataset (Test set 2):
• \(2 \le N \le 10^9\).
• \(1 \le M \le 1000\).
• \(1 \le p_i \le 10^9\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
6 2
1 3 1
3 6 1
6 2
1 3 2
4 6 1
10 2
1 7 2
6 9 1

Case #1: 6
Case #2: 0
Case #3: 10

Nguồn

Google Code Jam 2013, Vòng 2, bài Ticket Swapping.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.