Police Hypothesis

The public transport system of Nlogônia has an express network that connects the country's main tourist sites. $N-1$ bullet trains connect $N$ attractions so that starting from any one tourist site, you can reach every other site using only this express network.

Graffiti is common at train stations, as it is anywhere in the world. The police noticed that every station has exactly one letter painted in a specific style. They suspect criminals are changing the graffiti to communicate, so they decided to build a system that monitors the graffiti and its changes.

Given a pattern $P$, the connections between stations, and the suspicious letter at each station, write a program that handles the following operations.

• 1 u v: Print how many times the pattern $P$ occurs on the path from $u$ to $v$, reading the letters of consecutive vertices along the path.
• 2 u x: Change the suspicious letter at station $u$ to $x$.

The first line contains two integers $N$ and $Q$ ($1 \le N, Q \le 10^5$), the number of stations and the number of operations. The second line contains the monitored pattern $P$ ($1 \le |P| \le 100$). The third line contains a string $S$ of $N$ characters, the letters initially associated with each station. Each of the next $N-1$ lines contains two integers $u$ and $v$, meaning there is a bullet train between stations $u$ and $v$. The next $Q$ lines describe the operations.

For each operation of type 1, print one line containing the number of occurrences of the pattern on the analyzed path.