E. Misha and LCP on Treetime limit per test8 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputMisha 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.InputThe 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.OutputFor each query print the length of the largest common prefix on a separate line.ExamplesInput6bbbabb2 13 24 35 26 562 5 3 11 5 2 35 6 5 66 3 4 16 2 3 42 2 4 5Output222010
Input6bbbabb2 13 24 35 26 562 5 3 11 5 2 35 6 5 66 3 4 16 2 3 42 2 4 5
Output222010
['binary search', 'dfs and similar', 'hashing', 'string suffix structures', 'trees', '*3000']