Facebulk Inc. is a mining company whose Bulk Geological Processing (BGP) network has been disrupted lately. To ensure that buildings are more accessible in future outages, the company has hired emergency response agents for testing across each of its \(T\) ore-processing plants.

A given plant consists of \(3N\) rooms arranged in a grid of \(N\) rows and \(3\) columns. The room in the \(i\)th row from the top and the \(j\)th column from the left can be referred to as room \((i, j)\). Each room \((i, j)\) has an authorization level of \(A_{i,j}\), meaning that only agents with authorization levels \(A_{i,j}\) or greater may enter it.

\(M\) agents have been tasked to independently navigate the grid. The \(i\)th agent, who has an authorization level of \(L_i\), begins in room \((R1_i, C1_i)\) and would like to reach a different room \((R2_i, C2_i)\). It's guaranteed that they are authorized to be in both of those rooms (that is, \(L_i \ge A_{R1_i,C1_i}\) and \(L_i \ge A_{R2_i,C2_i}\)). The agent may make one or more moves, each consisting of moving to an adjacent room that they're also authorized to enter. Two rooms \((i_1, j_1)\) and \((i_2, j_2)\) are considered to be adjacent if they share a wall (that is, if \(|i_1 - i_2| + |j_1 - j_2| = 1\)).

Let \(D_i\) equal the minimum number of moves required for the \(i\)th agent to travel from room \((R1_i, C1_i)\) to room \((R2_i, C2_i)\), with \(D_i\) considered to equal \(1\) if the \(i\)th agent cannot complete their trip at all.

Please help Facebulk evaluate the emergency accessibility of its buildings by computing the product of \(D_{1..M}\). As this product may be very large, you should compute its value modulo \(1{,}000{,}000{,}007\).

# Constraints

\(1 \le T \le 70\)
\(1 \le N, M \le 1{,}000{,}000\)
\(1 \le A_{i,j} \le 10^9\)
\(1 \le R1_i, R2_i \le N\)
\(1 \le C1_i, C2_i \le 3\)
\(1 \le L_i \le 10^9\)

The sum of \(N+M\) across all plants is at most \(4{,}000{,}000\).

# Input

Input begins with an integer \(T\), the number of ore-processing plants. For each plant, there is first a line containing \(2\) space-separated integers, \(N\) and \(M\). Then, \(N\) lines follow, the \(i\)th of which contains \(3\) space-separated integers, \(A_{i,1..3}\). Then, \(M\) lines follow, the \(i\)th of which contains \(5\) space-separated integers, \(R1_i\), \(C1_i\), \(R2_i\), \(C2_i\), and \(L_i\).

# Output

For the \(i\)th plant, print a line containing *"Case #i: "* followed by a single integer, the product of \(D_{1..M}\) as defined above, modulo \(1{,}000{,}000{,}007\).

# Sample Explanation

In the first plant, the first agent cannot reach room \((1, 3)\) from room \((1, 1)\) as they're not authorized to enter room \((1, 2)\). On the other hand, the second agent can move into room \((1, 2)\) and then into room \((1, 3)\), taking a total of \(2\) moves. Therefore, \(D = [1 \mathrm{\;(impossible),\,} 2]\), and so the answer is \((1 \cdot 2) \mathrm{\;mod\;} 1{,}000{,}000{,}007 = 2\).

In the second plant, the first agent's shortest route is through rooms \((1, 3) \to (1, 2) \to (1, 1)\). Meanwhile, \((1, 3) \to (2, 3) \to (3, 3) \to (3, 2) \to (3, 1) \to (2, 1) \to (1, 1)\) is the second agent's shortest route. Overall, \(D = [2, 6, 3, 1 \mathrm{\;(impossible),\,} 2, 4]\), and so the answer is \((2 \cdot 6 \cdot 3 \cdot 1 \cdot 2 \cdot 4) \mathrm{\;mod\;} 1{,}000{,}000{,}007 = 288\).

In the third plant, \(D = [10]\).

In the fourth plant, \(D = [8, 5, 1 \mathrm{\;(impossible),\,} 11, 14, 10, 4, 3, 7, 8, 5, 7, 5, 7, 8]\).