A fairground has the form of a regular polygon consisting of $n$ vertices, the vertices are numbered from $1$ to $n$ clockwise. The organizer divides the fair area by $n - 3$ dividing lines to obtain $n - 2$ triangular booths, the dividing lines do not intersect inside the polygon, the dividing line $k$ passes through two distinct vertices $i_k,j_k$ $(1 \le k \le n - 3)$. Thus, a booth will have three sides, each side is a polygonal edge or dividing line. To encourage visitors to visit the stalls, the organizer will give prizes worth $t_k$ to visitors when passing through the $k$th dividing line.
Alice plans to enter the fairground from a booth whose face is an edge connecting vertices $u$ and vertex $(u \\% n + 1)$ then exit the fairground from a booth whose face is an edge connecting vertices $v$ and vertex $(v \\% n + 1)$. Alice hopes that each booth will be visited no more than once and the total value of the rewards received will be the greatest. Note that $u \neq v$ and the operation $\\%$ is to divide and receive remainder.
Requirement: Alice has $q$ assumptions, each assumption described by two integers $u,v$ means that Alice enters from the edge connecting vertex $u$ and vertex $(u \\% n + 1) $ and comes out from the edge connecting vertex $v$ and vertex $(v \\% n + 1)$, for each assumption, help Alice compute the maximum possible total value of the rewards that can be achieved.
### Input
- The first line contains two positive integers $n,q$ $(q \le n);$
- The $k$-th line $(1 \le k \le n - 3)$ contains three positive integers $i_k,j_k,t_k$ describing the $k$-th dividing line $(1 \le i_k,j_k \le n$ and$i_k \neq j_k;t_k \le 10^9);$
- The second line $s$ $(1 \le s \le q)$ includes two positive integers $u,v$ describing an assumption.
### Output
- Write out $q$ lines, each line contains an integer that is the maximum total value of the rewards that can be achieved.
### Example
Input:
```
6 2
2 4 1
2 5 2
2 6 3
1 5
1 2
```
Output:
```
3
6
```
### Subtask
- Subtask 1 (40%) : $n \le 10$
- Subtask 2 (30%) : $n \le 100$
- Subtask 3 (30%) : $n \le 10^5$
