Rubbish Sorting

Bob has many pieces of rubbish. Each piece of rubbish has a type, which is represented by a positive integer. Bob has q operations, and each operation is one of the following two types:

• 1 s x: Bob tells you that the piece of rubbish with name s has a type x.
• 2 s: Bob asks you for the type of the piece of rubbish named s.

Note that in a type 2 operation, the string s might not have appeared in any previous type 1 operations.

The similarity between two strings \(s_1\) and \(s_2\) is defined as \[ sim(s_1,s_2)=\sum_{i=1}^{\min\{|s_1|,|s_2|\}} [s_{1,i}=s_{2,i}], \] where \([P]\) equals \(1\) if the proposition \(P\) is true, and \(0\) otherwise, and the string indices start at 1.

For a query operation 2 s, consider all strings that have appeared in previous type 1 operations. The type assigned to s is defined to be the type of the string that has the maximum similarity to s. If there are multiple strings with the maximum similarity, choose the one with the smallest type value.

Your task is to process the operations in order and print the result for each query operation.

inputFormat

The first line contains an integer q representing the number of operations.

Each of the following q lines represents an operation. An operation is in one of the following formats:

• 1 s x — indicate that the piece of rubbish named s has type x (with x a positive integer).
• 2 s — a query asking for the type of rubbish s.

It is guaranteed that when a query operation (2 s) is encountered, there is at least one previous operation of type 1.

outputFormat

For each query operation (2 s), output the determined type for the string s on a separate line.

sample

6
1 abcd 10
1 abc 5
2 abcde
2 ab
1 ab 3
2 abc

10
5
5