Simulating String Operations with Prefix-Suffix Queries

You are given a sequence of operations to perform on an initially empty string. Each operation is either an append operation or a query.

An append operation has the form append x where x is a lowercase letter, and it appends the character to the end of the current string.

A query operation has the form query and requires you to compute the length of the longest proper prefix of the current string that is also a suffix. This is commonly computed using the KMP (Knuth–Morris–Pratt) algorithm's prefix function.

For each query operation, you must output the result on a new line. If there are no query operations, output nothing.

Note: A proper prefix of a string is a prefix that is not equal to the string itself.

inputFormat

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

Each of the following n lines contains an operation. An operation is either of the form:

• append x — append the lowercase character x to the current string, or
• query — output the length of the longest proper prefix which is also a suffix of the current string.

outputFormat

For each query operation encountered in the input, output the respective result on a new line. If no query operation is present, the output should be empty.

## sample

6
append a
append b
append a
query
append b
query

1
2

</p>