A rooted tree is a non-directed connected graph without any cycles with a distinguished vertex, which is called the tree root. Consider the vertices of a rooted tree, that consists of n vertices, numbered from 1 to n . In this problem the tree root is the vertex number 1. Let's represent the length of the shortest by the number of edges path in the tree between vertices v and u as d ( v , u ) . A parent of vertex v in the rooted tree with the root in vertex r ( v ≠ r ) is vertex p v , such that d ( r , p v ) + 1 = d ( r , v ) and d ( p v , v ) = 1 . For example, on the picture the parent of vertex v = 5 is vertex p 5 = 2 . One day Polycarpus came across a rooted tree, consisting of n vertices. The tree wasn't exactly ordinary: it had strings written on its edges. Polycarpus positioned the tree on the plane so as to make all edges lead from top to bottom if you go from the vertex parent to the vertex (see the picture). For any edge that lead from vertex p v to vertex v (1 < v ≤ n ) , he knows string s v that is written on it. All strings are written on the edges from top to bottom. For example, on the picture s 7 =" ba ". The characters in the strings are numbered starting from 0. Polycarpus defines the position in this tree as a specific letter on a specific string. The position is written as a pair of integers ( v , x ) that means that the position is the x -th letter of the string s v ( 1 < v ≤ n , 0 ≤ x < | s v | ), where | s v | is the length of string s v . For example, the highlighted letters are positions ( 2, 1 ) and ( 3, 1 ). Let's consider the pair of positions ( v , x ) and ( u , y ) in Polycarpus' tree, such that the way from the first position to the second goes down on each step. We will consider that the pair of such positions defines string z . String z consists of all letters on the way from ( v , x ) to ( u , y ) , written in the order of this path. For example, in the picture the highlighted positions define string " bacaba ". Polycarpus