题目描述

给定一棵 $n$ 个节点的树，每个节点有一个小写字母。有 $m$ 组询问，每组询问为树上 $a \to b$ 和 $c \to d$ 组成的字符串的最长公共前缀。

输入格式

第一行一个整数 $n$，$1\le n\le 300000$。

第二行一个长度为 $n$ 的字符串，由小写字母组成。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示顶点 $u$ 和 $v$ 之间存在一条边。

接下来一个整数 $m$，$1\le m\le 1000000$。

接下来 $m$ 行，每行四个整数 $a,b,c,d$，表示一个询问。

输出格式

对于每个询问，在一行中输出一个整数表示答案。

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