경찰 가설

닐로고니아의 대중교통 시스템에는 주요 관광지를 잇는 고속 노선망이 있다. $N-1$개의 고속 열차가 $N$개의 관광지를 연결하며, 어느 관광지에서 출발하든 이 노선망만으로 다른 모든 관광지에 갈 수 있다.

역의 낙서는 세계 어디에나 흔하듯 이 나라 역에서도 흔하다. 경찰이 주목한 점은 각 역에 특정 스타일로 쓰인 글자가 정확히 하나씩 있다는 것이다. 범인들이 낙서를 바꾸어 연락을 주고받는다는 가설에 따라, 경찰은 낙서와 그 변경을 감시하는 시스템을 만들기로 했다.

감시할 패턴 $P$, 역 사이의 연결 관계, 각 역의 의심스러운 글자가 주어질 때, 다음 연산을 처리하는 프로그램을 작성하라.

• 1 u v: u에서 v까지 경로를 따라 이어지는 정점들에 대응하는 글자를 순서대로 읽었을 때, 패턴 $P$가 몇 번 나타나는지 출력한다.
• 2 u x: 역 u의 의심스러운 글자를 x로 바꾼다.

첫 줄에 두 정수 $N$과 $Q$ ($1 \le N, Q \le 10^5$)가 주어진다. 이는 역의 수와 연산의 수이다. 둘째 줄에는 감시할 패턴 $P$ ($1 \le |P| \le 100$)가 주어진다. 셋째 줄에는 각 역에 처음 대응하는 글자를 나타내는 길이 $N$의 문자열 $S$가 주어진다. 이어지는 $N-1$개의 줄에는 두 정수 $u$와 $v$가 주어지며, 이는 역 $u$와 역 $v$ 사이에 고속 열차가 있다는 뜻이다. 마지막 $Q$개의 줄에 연산이 주어진다.

종류가 1인 연산마다 분석한 경로에서 패턴이 나타나는 횟수를 한 줄에 출력한다.