题目描述

Alice 和 Bob 知道，一个由空格、左括号、右括号组成的序列被称为括号序列。有一类特殊的括号序列被称为"合法括号序列"。已知：

• 空串是合法括号序列；
• 如果 $S_1$ 和 $S_2$ 均是合法括号序列，则 $S_1+S_2$ 是合法括号序列；
• 如果 $S$是合法括号序列，则 $(+S+)$ 是合法括号序列；
• 如果 $S$ 是合法括号序列，在 $S$ 的任何位置（包括头尾位置）插入一个空格得到的序列是合法括号序列。

现在 Alice 希望知道：对于某个已知的有限状态自动机中的状态 $s$ 与 $t$ ，存在多少以 $s$ 为起点、$t$ 为终点、长度为 $k$ 的合法括号序列。

有限状态自动机是一个有向图 $G$，由 $n$ 个结点组成，每一个结点表示一个状态，且存在三类以此为起点的有向边。对于每一个状态，其向外的同一类有向边指向同样的状态。三类有向边分别代表三种符号：左括号、右括号和空格。

我们将状态从 $0$ 开始编号。对于第 $i$ 个状态，用 $dfa_{i,0/1/2}$ 分别表示从 $i$ 出发，代表了左括号、右括号和空格的那一类边指向的状态，再用 $dfa2_{i,0/1/2}$ 表示每一类边的个数。对于一条从 $s$ 出发到 $t$ 结束的路径，满足长度为 $k$ 且路径经过的边对应的符号构成的序列组成了一组合法的括号匹配，则称作"满足 $[G,s,t,k]$ 的合法括号序列"。

现在，Alice 为 Bob 提供了自动机 $G$，并提出 $Q$ 组询问。对于每一组询问，Alice 会给出 $s,t,k$，她希望 Bob 可以告诉她满足 $[G,s,t,k]$ 的合法括号序列有多少组。她只需要知道答案除以 $47$ 后的余数。

输入格式

第一行一个整数 $n$ 表示状态数，第二到 $n+1$ 行，第 $i$ 行六个整数 $dfa_{i-1,0},dfa2_{i-1,0},dfa_{i-1,1},dfa2_{i-1,1},dfa_{i-1,2},dfa2_{i-1,2}$，描述第 $i-1$ 个状态的出边。

接下来一行一个整数 $q$ 表示询问数，接下来 $q$ 行每行三个整数 $s,t,k$ 描述一组询问。

输出格式

输出 $q$ 行，每行一个整数表示对应询问的答案 $\bmod\ 47$ 的结果。

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

45
9
10
2
19
25

提示

在样例解释中使用符号 _ 代表空格。

对于第一组询问长度为 $3$ 的合法括号序列有：

• ___，合法方案数为 $3^3 = 27$；
• _()、(_)、()_，合法方案数均为 $1\times2\times3=6$。

所以总方案数为 $27+6\times3=45$。

对于 $100 \%$ 的数据，$1 \leq n \leq 2$，$0 \leq dfa_{i,j} , s , t < n$，$0 \leq dfa2_{i,j} < 2^{31}$，$1 \leq k \leq 10^5$。