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 \le n \le 300000) - 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 \le u,v \le n, u \neq v), separated by spaces.

The next line contains integer m (1 \le m \le 1000000) - the number of queries.

Next m lines contain information about queries. A query is defined by four integers a, b, c, d (1 \le a,b,c,d \le n), separated by spaces.

For each query print the length of the largest common prefix on a separate line.