The Smart Beaver from ABBYY has come up with a new developing game for children. The Beaver thinks that this game will help children to understand programming better. The main object of the game is finite rooted trees, each of their edges contains some lowercase English letter. Vertices on any tree are always numbered sequentially from 1 to m , where m is the number of vertices in the tree. Before describing the actual game, let's introduce some definitions. We'll assume that the sequence of vertices with numbers v 1 , v 2 , ... , v k ( k ≥ 1 ) is a forward path , if for any integer i from 1 to k - 1 vertex v i is a direct ancestor of vertex v i + 1 . If we sequentially write out all letters from the the edges of the given path from v 1 to v k , we get some string ( k = 1 gives us an empty string). We'll say that such string corresponds to forward path v 1 , v 2 , ... , v k . We'll assume that the sequence of tree vertices with numbers v 1 , v 2 , ... , v k ( k ≥ 1 ) is a backward path if for any integer i from 1 to k - 1 vertex v i is the direct descendant of vertex v i + 1 . If we sequentially write out all the letters from the edges of the given path from v 1 to v k , we get some string ( k = 1 gives us an empty string). We'll say that such string corresponds to backward path v 1 , v 2 , ... , v k . Now let's describe the game that the Smart Beaver from ABBYY has come up with. The game uses two rooted trees, each of which initially consists of one vertex with number 1 . The player is given some sequence of operations. Each operation is characterized by three values ( t , v , c ) where: t is the number of the tree on which the operation is executed ( 1 or 2 ); v is the vertex index in this tree (it is guaranteed that the tree contains a vertex with this index); c is a lowercase English letter. The actual operation is as follows: vertex v of tree t gets a new descendant with number m + 1 (where m is the current number of vertices in tree t ), and there sh