Counting Valid Parentheses Sequences in Finite Automata

A sequence consisting of spaces, left parentheses, and right parentheses is called a parentheses sequence. Among these, a special type of sequence is called a valid parentheses sequence. The valid parentheses sequences are defined recursively as follows:

• The empty string is valid.
• If \(S_1\) and \(S_2\) are valid, then their concatenation \(S_1+S_2\) is valid.
• If \(S\) is valid, then \((+S+)\) is valid.
• If \(S\) is valid, then inserting a space at any position (including the head and the tail) results in a valid sequence.

In other words, a sequence is valid if and only if, after removing all spaces, it forms a balanced parentheses sequence.

Alice and Bob are given a finite automaton \(G\) represented by a directed graph with \(n\) states numbered from \(0\) to \(n-1\). From every state \(i\), there are three types of outgoing edges corresponding to the symbols: left parenthesis \((\), right parenthesis \()\), and space. For each state \(i\) and for each symbol type \(j\) (with \(j = 0\) for \(()\), \(j = 1\) for \())\), and \(j = 2\) for space),

• \(dfa_{i,j}\) denotes the destination state of the edge of type \(j\).
• \(dfa2_{i,j}\) denotes the number of distinct edges of type \(j\) from state \(i\) (all these edges go to the same destination state \(dfa_{i,j}\)).

A valid parentheses sequence path in \(G\) is defined as a path from state \(s\) to state \(t\) consisting of exactly \(k\) transitions such that the sequence of symbols (each symbol chosen with multiplicity given by the corresponding \(dfa2\) value) forms a valid parentheses sequence (i.e. after removing spaces, the string is balanced and no prefix has a negative balance).

Your task is: given \(G\) and \(Q\) queries, each query containing three integers \(s\), \(t\), and \(k\), compute the number of valid parentheses sequence paths from state \(s\) to state \(t\) of length \(k\), modulo \(47\).

inputFormat

The input is given as follows:

1. The first line contains two integers \(n\) and \(Q\) separated by a space, where \(n\) is the number of states in the automaton and \(Q\) is the number of queries.
2. Then follow \(n\) lines. The \(i\)-th line (0-indexed) contains six integers: \(dfa_{i,0}\), \(dfa2_{i,0}\), \(dfa_{i,1}\), \(dfa2_{i,1}\), \(dfa_{i,2}\), \(dfa2_{i,2}\) separated by spaces. These represent the destination state and the multiplicity for the edge corresponding to '(' (when \(j=0\)), ')' (when \(j=1\)), and space (when \(j=2\)) respectively.
3. Then \(Q\) lines follow, each containing three integers \(s\), \(t\), and \(k\) separated by spaces, representing a query.

outputFormat

For each query, output a single integer on a new line: the number of valid parentheses sequence paths from state \(s\) to state \(t\) of length \(k\), modulo \(47\).

sample

2 3
1 1 0 1 0 1
1 1 0 1 0 1
0 0 0
0 0 2
0 0 3

1
2
4