Tree Path Character Operations

Given a tree with each edge assigned a character and a constant \(X\). The tree has \(n\) nodes and \(n-1\) edges. You are to perform \(q\) operations. All operations involve a simple path between two nodes, and it is guaranteed that the path contains exactly \(X\) edges.

There are two types of operations:

• 1 x y S: For the simple directed path from node \(x\) to node \(y\), replace the character on the \(i\)th edge (according to the direction from \(x\) to \(y\)) with the \(i\)th character of string \(S\). Note that \(S\) is of length \(X\).
• 2 x y S: For the simple directed path from node \(x\) to node \(y\), count the number of occurrences of string \(S\) in the string formed by concatenating the characters on the path. Occurrences are counted with overlaps. For example, if \(S = 121\) and the path forms the string \(1212122\), then there are 2 matches (one from positions \(1\) to \(3\) and another from \(3\) to \(5\)).

All indices in string \(S\) are considered from 1. The operations will only be performed on paths that have exactly \(X\) edges.

inputFormat

The input is given as follows:

1. The first line contains three integers \(n\), \(q\), and \(X\): the number of nodes in the tree, the number of operations, and the constant \(X\), respectively.
2. The next \(n-1\) lines each contain two integers and a character: \(u\), \(v\), and \(c\). This represents an edge between nodes \(u\) and \(v\) with initial character \(c\).
3. The following \(q\) lines each describe an operation in the format: type x y S, where type is either 1 or 2. It is guaranteed that the unique simple path from \(x\) to \(y\) contains exactly \(X\) edges. Also, \(S\) is a string of length \(X\).

outputFormat

For each operation of type 2, output the number of occurrences of the string \(S\) (as a pattern) in the string formed by the path from \(x\) to \(y\). Each result should be printed on a new line.

sample

5 3 2
1 2 a
1 3 b
2 4 c
2 5 d
2 4 1 ca
1 4 1 xy
2 4 1 xy

1
1