Misha has a tree with characters written on the vertices. He can choose two vertices $*s*$ and $*t*$ of this tree and write down characters of vertices lying on a path from $*s*$ to $*t*$. We'll say that such string corresponds to pair $(*s*, *t*)$.
Misha has $*m*$ queries of type: you are given $4$ vertices $*a*$, $*b*$, $*c*$, $*d*$; you need to find the largest common prefix of the strings that correspond to pairs $(*a*, *b*)$ and $(*c*, *d*)$. Your task is to help him.
Input
The first line contains integer $*n*$ ($1 ≤ *n* ≤ 300 000$) — the number of vertices in the tree.
Next follows a line consisting of $*n*$ small English letters. The $*i*$-th character of the string corresponds to the character written on the $*i*$-th vertex.
Next $*n* - 1$ lines contain information about edges. An edge is defined by a pair of integers $*u*$, $*v*$ ($1 ≤ *u*, *v* ≤ *n*$, $*u* ≠ *v*$), separated by spaces.
The next line contains integer $*m*$ ($1 ≤ *m* ≤ 1 000 000$) — the number of queries.
Next $*m*$ lines contain information about queries. A query is defined by four integers $*a*$, $*b*$, $*c*$, $*d*$ ($1 ≤ *a*, *b*, *c*, *d* ≤ *n*$), separated by spaces.
Output
For each query print the length of the largest common prefix on a separate line.
样例
6
bbbabb
2 1
3 2
4 3
5 2
6 5
6
2 5 3 1
1 5 2 3
5 6 5 6
6 3 4 1
6 2 3 4
2 2 4 5
2
2
2
0
1
0
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。