L. Dynamic String Array
time limit per test
1 second
memory limit per test
256 MB
input
standard input
output
standard output

You are given an empty array of strings, let's call it $$$A$$$. You need to process $$$n$$$ queries of three different types.

The queries are as follows:

  • 1 S: Add the string $$$S$$$ to the array $$$A$$$.
  • 2 c: Append the character $$$c$$$ to the end of every string currently present in the array $$$A$$$.
  • 3 x: Check if the string $$$x$$$ exists in the array $$$A$$$. For this query, you must output "Yes" or "No".

Your task is to handle these queries and provide the correct output for all type 3 queries.

Input

The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of queries.

The following $$$n$$$ lines each describe a query. The format for each query is one of the following:

  • 1 S: where $$$S$$$ is a string consisting of lowercase English letters ($$$1 \le |S| \le 10^6$$$).
  • 2 c: where $$$c$$$ is a single lowercase English letter.
  • 3 x: where $$$x$$$ is a string consisting of lowercase English letters ($$$1 \le |x| \le 10^6$$$).

It is guaranteed that the sum of lengths of all strings $$$S$$$ in type 1 queries and all strings $$$x$$$ in type 3 queries does not exceed $$$10^6$$$.

Note: it is guaranteed that the first query is from type one.

Output

For each query of type 3, print "Yes" on a new line if the string $$$x$$$ is found in the array $$$A$$$. Otherwise, print "No".

Example
Input
5
1 abc
3 abc
2 c
3 abc
3 abcc
Output
Yes
No
Yes
Note

Let $$$A$$$ be the array of strings. We will trace its state through each query to understand the output.

  1. Initial State: The array $$$A$$$ is empty. $$$$$$ A = [ \quad ] $$$$$$

  2. Query 1: 1 abc This query adds the string "abc" to the array $$$A$$$. $$$$$$ A = [ \text{"abc"} ] $$$$$$

  3. Query 2: 3 abc This query checks if the string "abc" exists in $$$A$$$. It does. $$$$$$ \rightarrow \textbf{Output: Yes} $$$$$$

  4. Query 3: 2 c This query appends the character 'c' to every string currently in $$$A$$$. The string "abc" is modified to become "abcc". $$$$$$ A = [ \text{"abcc"} ] $$$$$$

  5. Query 4: 3 abc This query checks for the string "abc" in $$$A$$$. The array no longer contains "abc"; it only contains "abcc". $$$$$$ \rightarrow \textbf{Output: No} $$$$$$

  6. Query 5: 3 abcc This query checks for the string "abcc" in $$$A$$$. This string is present. $$$$$$ \rightarrow \textbf{Output: Yes} $$$$$$