Given a directed graph with $n$ vertices, labeled $1$ to $n$, there is an edge from $i$ to $j$ for any two distinct vertices $i \neq j$, with a weight of $a_{i,j}$.

Over the next $q$ days, one node $p_i$ will be closed each day. For each day, you need to find the shortest path length from $s_i$ to $t_i$ without passing through $p_i$.

Input

The first line contains two positive integers $n$ and $q$ ($3 \leq n \leq 300, 1 \leq q \leq 5\times 10^5$), representing the number of vertices in the directed graph and the number of queries, respectively.

The next $n$ lines each contain $n$ integers, where the $j$-th integer in the $i$-th line represents $a_{i, j}$ ($0 \leq a_{i, j} \leq 10^{14}, a_{i, i}=0$).

The following $q$ lines each contain three integers $s_i, t_i, p_i$ ($1 \leq s_i, t_i, p_i \leq n$, where $s_i, t_i, p_i$ are distinct), representing the query for the shortest path length from $s_i$ to $t_i$ without passing through $p_i$.

Output

Output $q$ lines, each containing an integer representing the answer.

Examples

Input 1

3 3
0 7 8
14 0 5
8 16 0
3 2 1
1 3 2
2 1 3

Output 1

16
8
14

Input 2

5 8
0 15 8 7 8
8 0 8 6 8
8 7 0 14 7
5 7 6 0 14
12 8 7 6 0
4 3 5
4 5 1
5 1 4
4 5 3
1 2 4
2 3 5
3 4 2
3 4 5

Output 2

6
13
12
13
15
8
13
13

Note

For $30\%$ of the test cases: $n, q \leq 100$.

For $50\%$ of the test cases: $q \leq 1000$.

For all test cases: $1 \leq s_i, t_i, p_i \leq n \leq 300, 1 \leq q \leq 5\times 10^5, 0 \leq a_{i, j} \leq 10^{14}, \forall 1 \leq i \leq n: a_{i,i}=0$.