Perfect Memory

Hektor and Wiktor have a new and fascinating hobby: memorizing long sequences of integers. Each of them specializes in a particular kind of sequence. Hektor likes palindromes best, that is, sequences whose values at mirror positions are equal (the first matches the last, the second matches the second to last, and so on). Wiktor is an expert on antipalindromes, that is, sequences whose values at mirror positions are opposite (they sum to zero).

Lately the boys started wondering what becomes possible when they combine their skills. If they could split any sequence of integers into the sum of a palindrome and an antipalindrome, each of them could memorize his favorite kind of sequence, and together they could easily reconstruct the original.

For a given sequence $S$ of integers with even length $N$, compute two sequences $P$ and $A$, each of length $N$, such that $P$ is a palindrome, $A$ is an antipalindrome, and adding the elements of $P$ and $A$ at corresponding positions yields the sequence $S$.

The first line contains a natural number $Z$ ($1 \le Z \le 10$), the number of test sets. The sets are then described one after another.

The first line of each set contains one nonzero even natural number $N$ ($1 \le N \le 1000000$), the length of the sequence $S$.

The second line of each set contains $N$ integers $s_i$ ($-1000000 \le s_i \le 1000000$), the consecutive elements of the sequence $S$, separated by spaces.

For each set:

• If the given sequence $S$ can be split into the sum of the sequences $P$ and $A$ described above, print the sequence $P$ on the first line (with elements separated by single spaces) and the sequence $A$ on the second line.
• Otherwise print the word NIE on a single line.