Một khu hội chợ có dạng là một hình đa giác đều gồm \(n\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(n\) theo chiều kim đồng hồ. Ban tổ chức chia khu hội chợ bằng \(n-3\) đường ngắn để nhận được \(N-2\) gian hàng đều có hình tam giác, các đường ngăn không giao nhau bên trong đa giác, đường ngăn thứ \(k\) đi qua hai đỉnh phân biệt \(i_k,j_k\) (\(1 \le k \le n-3\)). Như vậy, một gian hàng sẽ có ba mặt, mỗi mặt là cạnh đa giác hoặc là đường ngăn. Để khuyến khích khách tham gia các gian hàng, Ban tổ chức sẽ có các phần thưởng giá trị \(t_k\) cho khách đi qua đường ngăn thứ \(k\).

Alice dự định đi vào khu hội chợ từ một gian hàng có mặt là cạnh nối đỉnh \(u\) và đỉnh (\(u\) \(\%\) \(n+1\)) và đi ra khỏi khu hội chợ từ một gian hàng có mặt là cạnh nối đỉnh \(v\) và đỉnh (\(v\) \(\%\) \(n+1\)). Alice mong muốn mỗi gian hàng sẽ đi qua không quá một lần và tổng giá trị các phần thưởng nhận được là lớn nhất. Chú ý rằng \(u \neq v\) và phép toán \(\%\) là phép toán chia lấy dư.

Yêu cầu: Alice có \(q\) giả định, mỗi giả định mô tả bằng hai số nguyên \(u,v\) có nghĩa là Alice đi vào từ cạnh nối đỉnh \(u\) và đỉnh (\(u\) \(\%\) \(n+1\)), với mỗi giả định hãy giúp Alice tính tổng giá trị các phần thưởng nhận được là lớn nhất có thể đạt được.

Input

• Dòng đầu chứa hai số nguyên dương \(n,q\) (\(q \le n\)).
• Dòng thứ \(k\) (\(1 \le k \le n-3\)) chứa ba số nguyên dương \(i_k,j_k,t_k\) mô tả đường ngăn thứ \(k\) (\(1 \le i_k,j_k \le n\) và \(i_k \neq j_k, t_k \le 10^9\)).
• Dòng thứ \(s\) (\(1 \le s \le q\)) gồm hai số nguyên dương \(u,v\) mô tả một giả định.

Output

• Ghi ra \(q\) dòng, mỗi dòng chứa một số nguyên là tổng gia trị các phần thưởng nhận được là lớn nhất có thể đạt được.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 100\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 10^5\).

Example

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

3
6