룬 숲

흑곰과 흰곰은 룬 숲에 사는 커모드 곰 남매이다. 두 곰은 숲에 있는 나무 한 그루에서 문자열 놀이를 하려고 한다. 룬 숲의 나무는 $1$부터 $N$까지의 정점과 $N-1$개의 양방향 간선으로 이루어진 연결 그래프이다. $i$번 정점에는 알파벳 대문자 $r_i$가 적혀 있다. 두 곰은 다음 규칙에 따라 나무에서 각자 원하는 문자열을 하나 만든다.

1. 빈 문자열 $S$를 준비한다.
2. 정점 $x$와 정점 $y$를 고른다. 두 정점은 같아도 된다.
3. 정점 $x$에서 시작해 정점 $y$에서 끝나는 단순 경로(중복된 정점이 없는 경로)를 따라 이동한다. 방문한 순서대로 정점에 적힌 문자를 $S$의 오른쪽 끝에 붙인다. 정점 $x$와 $y$에 적힌 문자도 포함한다.

이렇게 나무에서 만든 문자열을 $S(x,y)$라고 한다. 놀이를 하는 동안 나무에 적힌 문자는 사라지거나 바뀌지 않는다.

흑곰은 정점 $a$와 $b$를 골라 $S(a,b)$를 만든다. 흰곰은 정점 $c$와 $d$를 골라 $S(c,d)$를 만든다. 두 문자열을 왼쪽 끝부터 비교했을 때 몇 글자가 겹치는지 확인한다. 이것이 커모드 곰의 문자열 놀이이다.

첫 번째 줄에 정점의 개수 $N$이 주어진다. $(2\leq N\leq 2\times 10^5)$

두 번째 줄부터 $N$개의 줄에 걸쳐 $i+1$번째 줄에 $i$번 정점에 적힌 문자 $r_i$가 주어진다. $r_i$는 알파벳 대문자이다.

$N+2$번째 줄부터 $N-1$개의 줄에 걸쳐 간선의 양 끝 정점 $u_i$와 $v_i$가 공백으로 구분되어 주어진다. $(1\leq u_i < v_i\leq N)$

$2N+1$번째 줄에 정수 $M$이 주어진다. $(1\leq M\leq 2\times 10^5)$

$2N+2$번째 줄부터 $M$개의 줄에 걸쳐 흑곰과 흰곰이 고른 정점 $a_i, b_i, c_i, d_i$가 공백으로 구분되어 주어진다. $(1\leq a_i,b_i,c_i,d_i\leq N)$

$M$개의 줄에 걸쳐 $S(a_i,b_i)$와 $S(c_i,d_i)$를 왼쪽 끝부터 비교했을 때 겹치는 글자의 개수를 출력한다. $i$번째 줄에 $i$번째 놀이의 답을 쓴다.