ATM

바이트랜드 신용조합의 회원은 누구나 $10^{30}$ 미만인 임의의 정수 금액을 바이트랜드 더컷(ducat)으로 대출받을 수 있으며, 대출금 전액을 7일 이내에 갚아야 한다.

조합의 고객 서비스실에는 $0$번부터 $99$번까지 번호가 매겨진 ATM 100대가 있다. 각 ATM은 번호에 따라 정해진 한 가지 동작만 수행한다. $i$번 ATM은 $i$가 짝수이면 $2^i$ 더컷을 지급하고, $i$가 홀수이면 $2^i$ 더컷을 받는다.

어떤 금액을 대출받으려면 각 ATM을 최대 한 번씩만 사용하여 순수 현금 흐름이 그 금액과 정확히 같아지도록 해야 한다. 짝수 번호 ATM이 지급한 더컷은 받은 것으로, 홀수 번호 ATM이 받은 더컷은 낸 것으로 계산한다. 각 고객에 대해 요청한 금액을 이 방식으로 대출받을 수 있는지, 가능하다면 어떤 ATM을 사용해야 하는지 판단해야 한다. 대출금을 갚는 경우에도 같은 질문을 하는데, 이때는 순수 현금 흐름이 그 금액의 음수와 같아야 한다.

예를 들어 $7$ 더컷을 대출받으려면 $4$번 ATM에서 $16$ 더컷을, $0$번 ATM에서 $1$ 더컷을 받은 뒤 $3$번 ATM에 $8$ 더컷을, $1$번 ATM에 $2$ 더컷을 낸다(합계 $16 + 1 - 8 - 2 = 7$). $7$ 더컷을 갚으려면 $0$번 ATM에서 $1$ 더컷을 받은 뒤 $3$번 ATM에 $8$ 더컷을 낸다(합계 $1 - 8 = -7$).

각 고객에 대해 요청 금액을 대출받을 수 있는지와 갚을 수 있는지를 판단하고, 각 경우에 사용할 ATM 번호를 출력하는 프로그램을 작성하라.

첫째 줄에 고객 수를 나타내는 양의 정수 $n$ ($n \le 1000$)이 주어진다. 이어지는 $n$개의 줄에는 각각 $10^{30}$ 미만인 양의 정수 하나가 주어지며(십진수로 최대 30자리), $i$번째 줄의 수는 $i$번 고객이 대출받으려는 금액이다.

$2n$개의 줄을 입력 순서대로, 각 고객마다 두 줄씩 출력한다. $i$번 고객에 대해:

• 첫째 줄에는 요청 금액을 대출받기 위해 사용하는 ATM 번호들을 내림차순으로 공백 하나로 구분하여 출력하고, 규칙에 따라 대출이 불가능하면 NIE 한 단어만 출력한다.
• 둘째 줄에는 같은 형식으로 금액을 갚기 위해 사용하는 ATM 번호들을 출력하고, 갚는 것이 불가능하면 NIE를 출력한다.

모든 ATM 번호는 $[0, 99]$ 범위에 있다. (NIE는 폴란드어로 "아니오"라는 뜻이다.)