Digital Library Operations

You are given a digital library system that manages a collection of books. Each book has a title and a popularity score. Initially, the library contains n books with a default popularity score of 0. You are then given m operations that can modify the library. The operations can be one of the following types:

• ADD <title>: Add a new book with the given title to the library if it does not already exist. The initial popularity score of the new book is 0.
• UPDATE <title> <popularity>: Update the popularity score of an existing book with the provided popularity value.
• QUERY <substring>: Query the book which has a title containing the given substring and the highest popularity score. If no such book exists, the answer is \( -1 \).

For each QUERY operation, output the result as described above.

Note: All formulas are provided in \( \LaTeX \) format.

inputFormat

The input is given in the following format from standard input:

n
book_1
book_2
... 
book_n
m
operation_1
operation_2
... 
operation_m

Here, n is the number of initial books. The next n lines each contain a book title. Then, m is the number of operations, followed by m lines where each line defines an operation in one of the three forms as defined above.

outputFormat

For each QUERY operation, output the resulting popularity score on a new line. There is no output for ADD or UPDATE operations.

## sample

3
harrypotter
hobbit
catch22
1
QUERY har

0

</p>