Ayush, Ashish and Vivek are busy preparing a new problem for the next Codeforces round and need help checking if their test cases are valid.

Each test case consists of an integer $n$ and two arrays $a$ and $b$, of size $n$. If after some (possibly zero) operations described below, array $a$ can be transformed into array $b$, the input is said to be valid. Otherwise, it is invalid.

An operation on array $a$ is:   select an integer $k$ $(1 \le k \le \lfloor\frac{n}{2}\rfloor)$  swap the prefix of length $k$ with the suffix of length $k$ 

For example, if array $a$ initially is $\{1, 2, 3, 4, 5, 6\}$, after performing an operation with $k = 2$, it is transformed into $\{5, 6, 3, 4, 1, 2\}$.

Given the set of test cases, help them determine if each one is valid or invalid.


-----Input-----

The first line contains one integer $t$ $(1 \le t \le 500)$ — the number of test cases. The description of each test case is as follows.

The first line of each test case contains a single integer $n$ $(1 \le n \le 500)$ — the size of the arrays.

The second line of each test case contains $n$ integers $a_1$, $a_2$, ..., $a_n$ $(1 \le a_i \le 10^9)$ — elements of array $a$.

The third line of each test case contains $n$ integers $b_1$, $b_2$, ..., $b_n$ $(1 \le b_i \le 10^9)$ — elements of array $b$.


-----Output-----

For each test case, print "Yes" if the given input is valid. Otherwise print "No".

You may print the answer in any case.


-----Example-----
Input
5
2
1 2
2 1
3
1 2 3
1 2 3
3
1 2 4
1 3 4
4
1 2 3 2
3 1 2 2
3
1 2 3
1 3 2

Output
yes
yes
No
yes
No



-----Note-----

For the first test case, we can swap prefix $a[1:1]$ with suffix $a[2:2]$ to get $a=[2, 1]$.

For the second test case, $a$ is already equal to $b$.

For the third test case, it is impossible since we cannot obtain $3$ in $a$.

For the fourth test case, we can first swap prefix $a[1:1]$ with suffix $a[4:4]$ to obtain $a=[2, 2, 3, 1]$. Now we can swap prefix $a[1:2]$ with suffix $a[3:4]$ to obtain $a=[3, 1, 2, 2]$.

For the fifth test case, it is impossible to convert $a$ to $b$.

Difficulty: interview

Starter code:

Solutions:
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    works = True
    if n % 2:
        if a[n//2] != b[n//2]:
            works = False

    pairsA = []
    for i in range(n//2):
        f = a[i]
        s = a[n - i - 1]
        if f > s:
            f, s = s, f
        pairsA.append((f,s))

    pairsB = []
    for i in range(n//2):
        f = b[i]
        s = b[n - i - 1]
        if f > s:
            f, s = s, f
        pairsB.append((f,s))

    pairsA.sort()
    pairsB.sort()

    if works and pairsA == pairsB:
        print('Yes')
    else:
        print('No')


from collections import deque

def Hopcroft_Karp(adj, L):
    """
    Computes maximal matching in unweighted bipartite graph `adj`. Here `L` is
    a boolean array which gives the left part of the bipartite graph. If w is
    in adj[v], then precisely one of L[v], L[w] should be True.
    
    Returns (N, matching), where N is the cardinality of the matching, and
    matching is a list encoding the matched vertex (where a -1 indicates an
    unmatched vertex).
    """
    N = len(adj)
    matching = [-1 for _ in range(N)]

    while True:
        # If our matching changes, we need another iteration.
        extended = False
        
        # Do a BFS starting at all unmatched left nodes.
        sources = [v for v in range(N) if matching[v] == -1 and L[v]]
        
        # Keep track of your immediate predecessor in the BFS.
        # -1 means an unvisited node. Sources have themselves as predecessor.
        bfs_pred = [-1 for _ in range(N)]
        
        # Keep track of which BFS source started your subtree.
        # -1 means an unvisited node.
        bfs_source = [-1 for _ in range(N)]
        
        for v in sources:
            bfs_pred[v] = v
            bfs_source[v] = v
        
        queue = deque(sources)
        while len(queue) > 0:
            cur = queue.popleft()
            
            # If the node that started this subtree has been matched, stop growing the BFS.
            if matching[bfs_source[cur]] != -1:
                continue
            
            for nb in adj[cur]:
                if matching[nb] == -1:
                    # We have found an augmenting path. 
                    # Use a clever loop to use the path to update the matching.
                    while nb != -1:
                        matching[nb], matching[cur], nb, cur = cur, nb, matching[cur], bfs_pred[cur]
                    extended = True
                    break
                else:
                    new = matching[nb]
                    if bfs_pred[new] == -1:
                        bfs_pred[new] = cur
                        bfs_source[new] = bfs_source[cur]
                        queue.append(new)
        if not extended:
            break

    return sum(1 for x in matching if x != -1)//2, matching

t = int(input())

for _ in range(t):
    n = int(input())
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]

    if n % 2:
        if a[n//2] != b[n//2]:
            print("No")
            continue

    a_pairs = []
    b_pairs = []
    for i in range(n//2):
        if a[i] < a[n-i-1]:
            a_pairs.append((a[i], a[n-i-1]))
        else:
            a_pairs.append((a[n-i-1], a[i]))
        if b[i] < b[n-i-1]:
            b_pairs.append((b[i], b[n-i-1]))
        else:
            b_pairs.append((b[n-i-1], b[i]))

    adj = [[] for _ in range(len(a_pairs) + len(b_pairs))]
    for i, ap in enumerate(a_pairs):
        for j, bp in enumerate(b_pairs):
            if ap == bp:
                adj[i].append(len(a_pairs) + j)
                adj[len(a_pairs)+j].append(i)

    if Hopcroft_Karp(adj, [True]*len(a_pairs) + [False]*len(b_pairs))[0] == len(a_pairs):
        print("Yes")
    else:
        print("No")


def solve():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    if n % 2 == 1:
        if a[n // 2] != b[n // 2]:
            print('No')
            return
    u, v = list(), list()
    def add(s, p, q):
        if p > q:
            p, q = q, p
        s.append((p, q))
    for i in range(n // 2):
        add(u, a[i], a[n - i - 1])
        add(v, b[i], b[n - i - 1])
    if sorted(u) == sorted(v):
        print('Yes')
    else:
        print('No')
t = int(input())
for _ in range(t):
    solve()

q = int(input())
for _ in range(q):
	n = int(input())
	l1 = list(map(int,input().split()))
	l2 = list(map(int,input().split()))
	x1 = 0 
	x2 = 0
	if n%2 == 1:
		x1 = l1.pop(n//2)
		x2 = l2.pop(n//2)
	if x1 != x2:
		print("No")
	else:
		if n%2 == 1:
			n-= 1
		d1 = []
		d2 = []
		for i in range(n//2):
			d1.append([min(l1[i],l1[n-i-1]),max(l1[i],l1[n-i-1])])
			d2.append([min(l2[i],l2[n-i-1]),max(l2[i],l2[n-i-1])])
		d1.sort()
		d2.sort()
		if d1 == d2:
			print("Yes")
		else:
			print("No")

import sys

def ii():
    return sys.stdin.readline().strip()

def idata():
    return [int(x) for x in ii().split()]

def solve_of_problem():
    n = int(ii())
    data = idata()
    data1 = idata()
    if n == 1:
        if data1 == data:
            print('Yes')
        else:
            print('No')
        return
    if sorted(data) != sorted(data1):
        print('No')
        return
    if n % 2 == 1:
        if data[n // 2] != data1[n // 2]:
            print('No')
            return
        data = data[:n // 2] + data[n // 2 + 1:]
        data1 = data1[:n // 2] + data1[n // 2 + 1:]
        n -= 1
    d = dict()
    for i in range(n // 2):
        d[str(data[i]) + ' ' + str(data[n - i - 1])] = 0
        d[str(data[n - 1 - i]) + ' ' + str(data[i])] = 0
        d[str(data1[i]) + ' ' + str(data1[n - i - 1])] = 0
        d[str(data1[n - 1 - i]) + ' ' + str(data1[i])] = 0
    for i in range(n // 2):
        d[str(data[i]) + ' ' + str(data[n - i - 1])] += 1
        d[str(data[n - 1 - i]) + ' ' + str(data[i])] += 1
        d[str(data1[i]) + ' ' + str(data1[n - i - 1])] -= 1
        d[str(data1[n - 1 - i]) + ' ' + str(data1[i])] -= 1
    if min(d.values()) < 0:
        print('No')
        return
    print('Yes')
    return

for ______ in range(int(ii())):
    solve_of_problem()


for _ in range(int(input())):
    n = int(input())
    a = tuple(map(int, input().split()))
    b = tuple(map(int, input().split()))
    if sorted(zip(a, reversed(a))) == sorted(zip(b, reversed(b))):
        print("Yes")
    else:
        print("No")


for _ in range(int(input())):
    n=int(input())
    k=n//2
    a=list(map(int,input().split()))
    b=list(map(int,input().split()))
    dicA={}
    dicB={}
    for i in range(k):
        p,q=a[i],a[-i-1]
        if p>q:
            if (q,p) not in dicA:
                dicA[(q,p)]=0
            dicA[(q,p)]+=1
        else:
            if (p,q) not in dicA:
                dicA[(p,q)]=0
            dicA[(p,q)]+=1

    for i in range(k):
        p,q=b[i],b[-i-1]
        if p>q:
            if (q,p) not in dicB:
                dicB[(q,p)]=0
            dicB[(q,p)]+=1
        else:
            if (p,q) not in dicB:
                dicB[(p,q)]=0
            dicB[(p,q)]+=1

    if n%2==1:
        if a[k]!=b[k]:
            print("No")
        else:
            res="Yes"
            for p,q in dicA:
                if (p,q) not in dicB:
                    res="No"
                elif dicA[(p,q)]!=dicB[(p,q)]:
                    res="No"
            print(res)
    else:
        res="Yes"
        for p,q in dicA:
            if (p,q) not in dicB:
                res="No"
            elif dicA[(p,q)]!=dicB[(p,q)]:
                res="No"
        print(res)

from collections import Counter
T = int(input().strip())
for t in range(T):
    n = int(input().strip())

    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    if Counter(a) != Counter(b):
        print('No')
        continue
    mid = n//2 + n % 2
    aa = Counter(tuple(sorted([a[i],a[n-i-1]])) for i in range(mid))
    bb = Counter(tuple(sorted([b[i],b[n-i -1]])) for i in range(mid))


    # print(aa)
    # print(bb)
    if aa != bb:
        print('No')
        continue
    print('Yes')



import sys
input = sys.stdin.readline

t=int(input())
for tests in range(t):
    n=int(input())
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))

    C=[]
    D=[]

    if n%2==1:
        if A[n//2]!=B[n//2]:
            print("No")
            continue

    for i in range(n//2):
        C.append(sorted([A[i],A[-i-1]]))
        D.append(sorted([B[i],B[-i-1]]))

    #print(C)
    #print(D)

    if sorted(C)==sorted(D):
        print("Yes")
    else:
        print("No")


from collections import defaultdict
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    for _ in range(II()):
        n = II()
        aa = LI()
        bb = LI()

        if n%2:
            if aa[n//2]!=bb[n//2]:
                print("No")
                continue

        cnt=defaultdict(int)
        for i in range(n//2):
            l=aa[i]
            r=aa[n-1-i]
            if l>r:l,r=r,l
            cnt[l,r]+=1

        ng=False
        for i in range(n//2):
            l=bb[i]
            r=bb[n-1-i]
            if l>r:l,r=r,l
            if cnt[l,r]==0:ng=True
            cnt[l,r]-=1

        if ng:print("No")
        else:print("Yes")

main()


t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    paira = []
    for i in range((n+1)//2):
        paira.append(tuple(sorted([a[i], a[~i]])))

    pairb = []
    for i in range((n+1)//2):
        pairb.append(tuple(sorted([b[i], b[~i]])))


    paira.sort()
    pairb.sort()

    if paira == pairb:
        print("Yes")
    else:
        print("No")