Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

It’s Žika’s birthday. As is common for protagonists of programming problems written by someone without any better ideas for the problem statement, he got an array \(A_i\) containing \(N\) integers as a gift: This phenomenon is so common that this happened last year as well, when his birthday gift was another length-\(N\) array: \(B_i\)! Žika, like any normal person, doesn’t have any use for two different length-\(N\) arrays, so he wants to transform his new gift \(A_i\) into \(B_i\).

Because we needed the second problem in the B category, Žika decided that the only operation he will use on \(A\) is to choose two adjacent elements, swap their places, and then flip their signs. That is, if the array was \(A_1, A_2, \dots, A_i, A_{i+1}, \dots, A_N\), and he applies the operation to elements \(A_i\) and \(A_{i+1}\), the array will become \(A_1, A_2, \dots, -A_{i+1}, -A_i, \dots, A_N\). Your task is to tell Žika if it is possible to use this operation to transform \(A_i\) into \(B_i\), so that \(A_i = B_i\) for all \(i \in \{1, 2, \dots, N\}\).

Input format

The first line of the standard input contains the number of testcases \(T\). The following rows describe \(T\) independent testcases.

The first line of each testcase contains an integer \(N\): the length of the arrays \(A_i\) and \(B_i\). The following two lines contain \(N\) integers each: the elements of the arrays \(A_i\) and \(B_i\).

Output format

Your program should print \(T\) lines to the standard output: the answers to the \(T\) testcases, in order. For each testcase, your program shoud print “DA” if it is possible to transform \(A_i\) into \(B_i\) using the described operation, and “NE” otherwise (without quotes).

Sample

Input

3
2
1 2
-1 -2
2
1 2
-2 -1
4
1 2 3 4
-4 -3 -2 -1

Output

NE
DA
DA

Explanation

If the starting array is \(1, 2\) the only other array we can build is \(-2, -1\) (if we swap again, we’ll just end up with the initial array), so the answer is “no” in the first testcase, and “yes” in the second. In the third testcase, we can transform \(A_i\) into \(B_i\) by applying the following swaps: \((1,2)\), \((2,3)\), \((3,4)\), \((1,2)\), \((2,3)\), \((1,2)\).

Constraints

Testcases are split into four disjoint groups: