Counting Pattern Occurrences in Flutter Sequences

You are given a reserve with N observation points and M directed connections between them. Each connection carries a flutter pattern (a string). For every query, given two observation points u and v and a pattern pat, you need to determine how many times pat appears as a contiguous substring in the flutter sequence along all possible simple paths from u to v.

The flutter sequence for a path is defined as the concatenation of the pattern strings along the edges of that path. The answer for each query is the sum of the number of occurrences of pat in the flutter sequence of every simple path from u to v.

Formally, if a path produces a flutter sequence S, the number of occurrences is given by \[ \text{count}(S, pat) = \sum_{i=0}^{|S|-|pat|} \mathbf{1}_{\{S[i:i+|pat|]=pat\}} \] where \(\mathbf{1}\) is the indicator function. Sum these counts for all paths from u to v.

Note: It is guaranteed that the reserve does not contain cycles, so all paths are simple.

inputFormat

The input is read from standard input (stdin) and has the following format:

N
M
u1 v1 p1
u2 v2 p2
... (M lines total)
Q
u1 v1 pat1
u2 v2 pat2
... (Q lines total)

Where:

• N is the number of observation points.
• M is the number of directed edges.
• Each edge is described by two integers u and v (the start and end observation points) followed by a string p representing the flutter pattern on that edge.
• Q is the number of queries.
• Each query contains two integers u and v and a string pat that you need to search for in the concatenated flutter sequences along every simple path from u to v.

outputFormat

For each query, output a single integer on a new line representing the total number of occurrences of the pattern pat as a contiguous substring in all flutter sequences for all possible simple paths from u to v.

## sample

7
6
1 2 a
2 3 b
3 4 c
4 5 d
5 6 e
6 7 f
5
1 7 abc
2 5 bcd
1 4 ab
3 6 cde
4 7 def

1
1
1
1
1

</p>