测试数据来自 system/1871

描述

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

（1）“（）”是合法的括号序列，空串是合法的括号序列。

（2）如果S1 是合法的括号序列，S2 是合法的括号序列，则S1 与S2 拼接起来的序列S1＋S2 也是合法的括号序列。

（3）如果S 是合法的括号序列，在其左右分别插入一个左括号和一个右括号所得到的字符串“（”＋S1＋“）”也是合法的括号序列。

（4）如果S 是合法的括号序列，在S 的任何位置（包括头尾位置）插入一个空格，得到的序列也是合法的括号序列。

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

所谓有限状态自动机，又可以被认为是一个有向图G，由n 个结点组成，每一个结点表示一个状态，且存在三类以此为起点出去的有向边，对于每一个状态（或结点）来说其出去的同一类有向边将指向同样的状态（或结点）。三类有向边分别代表三种符号：左括号“（”，右括号“）”和空格。

这里，我们将状态（或结点）从0 开始编号。对于第i 个状态，用dfa[i][0]，dfa[i][1]，dfa[i][2]分别表示从i 出发，代表了左括号、右括号和空格的那一类边指向的状态（或结点），再用dfa2[i][0]，dfa2[i][1]，dfa2[i][2]表示每一类边的个数。

对于一条从s 出发到t 结束的路径，满足长度为k 且路径经过的边对应的符号组成了一组合法的括号匹配，则称作“满足[G,s,t,k]的合法括号序列”。

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

格式

输入格式

第一行一个整数n，表示状态数（或结点数）。

之后n 行，对于其中的第i 行，有6 个32 位整数，依次为dfa[i-1][0]，dfa2[i-1][0]，
dfa[i-1][1]，dfa2[i-1][1]，dfa[i-1][2]，dfa2[i-1][2]。

之后一行有一个整数Q，表示Alice 的询问次数。

之后Q 行，每一行有3 个32 位的整数，依次为s，t，k。

输出格式

输出文件有Q 行。

其中第i 行对应了第i 个询问，只有一个整数，表示满足[G,s,t,k]的合法括号序列的个数，答案只需要除以47 后的余数。

样例1

样例输入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

样例输出1

45
9
10
2
19
25

限制

存在10％的数据：k <= 1000。时间限制1 秒。

提示

样例说明：

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

（1）三个空格“ ”，则在自动机中的合法方案数为：3×3×3＝27。

（2）对于“（ ）”、“（） ”和“ （）”，则在自动机中的合法方案数为：1×3×2＝6。

所以总的可行方案数为：27＋3×6＝27＋18＝45。