룬 숲

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

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

이러한 규칙을 통해 나무에서 만든 문자열을 $S\left( x,y \right)$라고 부른다. 문자열 놀이를 하는 동안 나무에 적혀있는 문자가 사라지거나 변하는 일은 없다.

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

룬 숲의 나무 한 그루가 주어진다. 두 곰은 이 나무에서 문자열 놀이를 $M$번 할 것이다. $i$번째 놀이에서 흑곰이 고른 정점 $a\_i,b\_i$와 흰곰이 고른 정점 $c\_i,d\_i$가 주어진다. 이때 $S\left( a\_i,b\_i \right)$와 $S\left( c\_i,d\_i \right)$를 왼쪽 끝부터 비교했을 때 몇 글자가 겹치는지 답해야 한다.

첫 번째 줄에 정점의 개수 $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\lt 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\left( a\_i,b\_i \right)$와 $S\left( c\_i,d\_i \right)$를 왼쪽 끝부터 비교했을 때 겹치는 글자의 개수를 출력한다.