ATMs

The Credit Society of Byteland lets any member borrow any whole number of Bytelandish ducats below $10^{30}$, and the entire sum must be paid back within seven days.

The Society's Client Service Room holds 100 ATMs, numbered $0$ through $99$. Each ATM only ever performs one fixed action tied to its number: ATM $i$ pays out $2^i$ ducats if $i$ is even, and collects $2^i$ ducats if $i$ is odd.

A client borrows a given amount by using each ATM at most once so that the net cash flow equals that amount: ducats paid out by even ATMs are gained, and ducats collected by odd ATMs are given up. For each client we must decide whether the requested amount can be borrowed this way and, if it can, which ATMs to use. We ask the same question about returning the amount, where the net cash flow must instead equal the negative of that amount.

For example, to borrow $7$ ducats a client takes $16$ ducats from ATM $4$ and $1$ ducat from ATM $0$, then pays $8$ ducats into ATM $3$ and $2$ ducats into ATM $1$; the net is $16 + 1 - 8 - 2 = 7$. To return $7$ ducats the client takes $1$ ducat from ATM $0$ and pays $8$ ducats into ATM $3$; the net is $1 - 8 = -7$.

Write a program that reads the number of clients and each requested amount, decides for every client whether the amount can be borrowed and whether it can be returned, and reports the ATMs to use in each case.

The first line contains a single positive integer $n$ ($n \le 1000$), the number of clients. Each of the next $n$ lines contains one positive integer smaller than $10^{30}$ (up to 30 decimal digits): the amount the corresponding client wants to borrow.

Print $2n$ lines, two for each client, in input order. For client $i$:

• the first line lists the numbers of the ATMs, in strictly decreasing order and separated by single spaces, that the client uses to borrow the requested amount, or the single word NIE if borrowing it under the rules is impossible;
• the second line lists, in the same format, the ATMs used to return the amount, or NIE if returning it is impossible.

Every ATM number lies in the range $[0, 99]$. (NIE means "no".)