E. Delta Propagation
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ bags labeled $$$1$$$ to $$$n$$$. Each bag contains a set of colored coins. A color is a lowercase letter from a to z. Within a bag, no color appears more than once.

The contents of bag $$$i$$$ are denoted by the set $$$S_i$$$.

You may apply the following operation any number of times:

  1. Choose an index $$$i$$$ such that $$$1 \le i \lt n$$$.
  2. Replace the contents of bag $$$i$$$ by the symmetric difference of $$$S_i$$$ and $$$S_{i+1}$$$: $$$$$$ S_i \leftarrow S_i \,\Delta\, S_{i+1}, $$$$$$ while $$$S_{i+1}$$$ remains unchanged.

The symmetric difference of two sets $$$A$$$ and $$$B$$$ is $$$$$$ A \Delta B = (A \setminus B) \cup (B \setminus A). $$$$$$

For each bag, its set of colors is given as a string of distinct lowercase letters (the order does not matter).

Your task is to determine whether it is possible to transform the initial contents of all bags into their target contents.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

For each test case:

  • The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$).
  • The second line contains $$$n$$$ space-separated strings — the initial contents of the bags.
  • The third line contains $$$n$$$ space-separated strings — the target contents of the bags.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print YES if it is possible to reach the target contents of every bag, otherwise print NO.

Example
Input
5
3
a b c
ab bc c
4
a bc d e
abcde bcde de e
3
a b c
a b d
1
abc
ab
2
a b
b b
Output
YES
YES
NO
NO
NO
Note

For the first test case, performing the operation at $$$i = 1$$$ and then at $$$i = 2$$$ is sufficient to reach the target configuration.

For the second test case, the operation can be performed sequentially at $$$i = 3, 2, 1$$$ to obtain the target configuration.

For the third test case, the contents of the last bag in the initial and target configurations are different. Since bag $$$n$$$ is never changed by any operation, it is not possible to reach the target state.

For the fourth test case, the same reasoning applies: when $$$n = 1$$$, no operation can be performed, so the initial set must already match the target set. It does not, hence the target state cannot be reached.

For the fifth test case, the only possible move is at $$$i = 1$$$. After performing it, bag $$$1$$$ becomes $$$\{a\} \Delta \{b\} = \{a,b\}$$$, and further applications just alternate between $$$\{a\}$$$ and $$$\{a,b\}$$$. Therefore, the target state cannot be reached.