Description

Daniel, Hank, and Noah are brothers. They were each given some binary tree of the same size which stores integers to traverse. They decide to traverse the binary tree with preorder, inorder and postorder respectively.

They want to know whether they are given the same binary tree or not.

Input

The first line of each input is t - The number of testcases.

Then the first line of each testcase contains n - The number of nodes of the binary tree.

Then followed by three lines.

pre - The preorder traversal of a tree.

in - The inorder traversal of a tree.

post - The postorder traversal of a tree.

Each data stored by the node i of the tree is a integer a_i. Each data in the traversal is seperated by an empty space.

Constrain

• 1 ≤ t ≤ 10
• 1 ≤ n ≤ 2 * 10⁵
• 1 ≤ a_i ≤ n
• In the same traversal, a_i ≠ a_j (if i ≠ j)
• It is promised that the nodes of each traversals are the same. Only the order of each nodes varies.

Output

For each testcase, if the three traversal is from the same tree, print "yes" in lowercase.

Otherwise, print "no" in lowercase.

Remember to print a ‘\n’ at the end of the output.

Sample Input  Download

Sample Output  Download

Tags

Discuss