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.
输入描述:
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.
输出描述:
For each query print the length of the largest common prefix on a separate line.
示例1
输入
6<br />bbbabb<br />2 1<br />3 2<br />4 3<br />5 2<br />6 5<br />6<br />2 5 3 1<br />1 5 2 3<br />5 6 5 6<br />6 3 4 1<br />6 2 3 4<br />2 2 4 5<br />
输出
2<br />2<br />2<br />0<br />1<br />0<br />
加载中...