Alice and Bob know that a sequence consisting of spaces, left parentheses, and right parentheses is called a bracket sequence. There is a special class of bracket sequences called "valid bracket sequences." It is known that:

(1) "()" is a valid bracket sequence, and the empty string is a valid bracket sequence. (2) If $S_1$ is a valid bracket sequence and $S_2$ is a valid bracket sequence, then the sequence $S_1 + S_2$ formed by concatenating $S_1$ and $S_2$ is also a valid bracket sequence. (3) If $S$ is a valid bracket sequence, then the string "(" + $S$ + ")" formed by inserting a left parenthesis at the beginning and a right parenthesis at the end of $S$ is also a valid bracket sequence. (4) If $S$ is a valid bracket sequence, then inserting a space at any position (including the beginning and the end) of $S$ results in a sequence that is also a valid bracket sequence.

Now, Alice wants to know: for given states $s$ and $t$ in a known finite automaton, how many valid bracket sequences of length $k$ exist that start at $s$ and end at $t$?

A finite automaton can be considered as a directed graph $G$ consisting of $n$ nodes, where each node represents a state. There are three types of directed edges originating from each node, and for every state (or node), all outgoing edges of the same type point to the same state (or node). The three types of edges represent three symbols: left parenthesis "(", right parenthesis ")", and space.

Here, we number the states (or nodes) starting from 0. For the $i$-th state, let dfa[i][0], dfa[i][1], and dfa[i][2] represent the state (or node) pointed to by the edges representing a left parenthesis, a right parenthesis, and a space, respectively, starting from $i$. Furthermore, let dfa2[i][0], dfa2[i][1], and dfa2[i][2] represent the number of edges of each type.

A path from $s$ to $t$ is called a "valid bracket sequence satisfying $[G, s, t, k]$" if it has length $k$ and the sequence of symbols corresponding to the edges traversed forms a valid bracket matching.

Alice provides the automaton $G$ to Bob and poses $Q$ queries. For each query, Alice provides $s$, $t$, and $k$, and she wants Bob to tell her how many valid bracket sequences satisfy $[G, s, t, k]$. She only needs the answer modulo 47.

Input

The first line contains an integer $n$, representing the number of states (or nodes). The following $n$ lines each contain 6 32-bit integers, which are dfa[i-1][0], dfa2[i-1][0], dfa[i-1][1], dfa2[i-1][1], dfa[i-1][2], and dfa2[i-1][2] for the $i$-th state. The next line contains an integer $Q$, representing the number of queries Alice makes. The following $Q$ lines each contain 3 32-bit integers, which are $s$, $t$, and $k$.

Output

The output contains $Q$ lines. The $i$-th line corresponds to the $i$-th query and contains a single integer representing the number of valid bracket sequences satisfying $[G, s, t, k]$, modulo 47.

Examples

Input 1

1
0 1 0 2 0 3
6
0 0 3
0 0 4
0 0 5
0 0 6
0 0 7
0 0 8

Output 1

45
9
10
2
19
25

Note

For the first query, the valid bracket sequences of length 3 are: (1) Three spaces " ", then the number of valid schemes in the automaton is: $3 \times 3 \times 3 = 27$. (2) For "( )", "( ) ", and " ()", the number of valid schemes in the automaton is: $1 \times 3 \times 2 = 6$. Therefore, the total number of feasible schemes is: $27 + 3 \times 6 = 27 + 18 = 45$.

Constraints

10% of the data: $k \le 1000$. Time limit 1 second. Another 10% of the data: $n=1$, dfa[0][0] = dfa[0][1] = dfa[0][2] = dfa2[0][2]=0, dfa2[0][0] = dfa2[0][1] = 1. Time limit 5 seconds. Another 20% of the data: $n=1$, dfa[0][0] = dfa[0][1] = dfa[0][2] = 0. Time limit 5 seconds. Another 30% of the data: $k \le 30000$. Time limit 15 seconds. Another 30% of the data: $k \le 100000$. Time limit 20 seconds. For 100% of the data: $n \le 2$, $k \le 100000$, $Q \le 10$.