Numeric String Template
Contest: Codeforces Round 966 (Div. 3)
Difficulty rating: 1000
Tags: data structures, strings

Kristina has an array $$$a$$$, called a template, consisting of $$$n$$$ integers. She also has $$$m$$$ strings, each consisting only of lowercase Latin letters. The strings are numbered from $$$1$$$ to $$$m$$$. She wants to check which strings match the template.

A string $$$s$$$ is considered to match the template if all of the following conditions are simultaneously satisfied:

- The length of the string $$$s$$$ is equal to the number of elements in the array $$$a$$$.
- The same numbers from $$$a$$$ correspond to the same symbols from $$$s$$$. So, if $$$a_i = a_j$$$, then $$$s_i = s_j$$$ for ($$$1 \le i, j \le n$$$).
- The same symbols from $$$s$$$ correspond to the same numbers from $$$a$$$. So, if $$$s_i = s_j$$$, then $$$a_i = a_j$$$ for ($$$1 \le i, j \le n$$$).

For example, if $$$a$$$ = [$$$3, 5, 2, 1, 3$$$], then the string "abfda" matches the template, while the string "afbfa" does not, since the character "f" corresponds to both numbers $$$1$$$ and $$$5$$$.

Input format:
The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The following descriptions are for the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in the array $$$a$$$.

The second line of each test case contains exactly $$$n$$$ integers $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

The third line of each test case contains a single integer $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — the number of strings to check for template matching.

Following are $$$m$$$ strings, each containing a non-empty string $$$s_j$$$ ($$$1 \le |s_j| \le 2 \cdot 10^5$$$), consisting of lowercase Latin letters.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$, and that the sum of the lengths of all strings does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output $$$m$$$ lines. On the $$$i$$$-th line ($$$1 \le i \le m$$$) output:

- "YES", if the string with index $$$i$$$ matches the template;
- "NO" otherwise.

You may output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The first test case is explained in the problem statement.

Example input:
3
5
3 5 2 1 3
2
abfda
afbfa
2
1 2
3
ab
abc
aa
4
5 -3 5 -3
4
aaaa
bcbc
aba
cbcb

Example output:
YES
NO
YES
NO
NO
NO
YES
NO
YES

Editorial:
To solve the problem, we can use two dictionaries (map): match the characters of the string to the numbers of the array in the map $$$m_1$$$ and the numbers of the array to the characters of the string in the map $$$m_2$$$.
First, we check the length of the string to see if it is equal to the number $$$n$$$. If the string is longer or shorter, the answer is "NO".
Otherwise, we will loop through the characters of the string and check the following conditions:
• The map $$$m_1$$$ does not contain the character $$$s_i$$$ as a key, and the map $$$m_2$$$ does not contain the number $$$a_i$$$ as a key. Then let's perform the assignments $$$m_1[s_i] = a_i$$$ and $$$m_2[a_i] = s_i$$$.
• One of the maps contains the current array element or string character as a key, but its value does not match the character or number in the current position. Then the answer to the problem is — "NO", you can break the loop.
If the loop reaches the end of the line, the answer to the problem is "YES".