ATMS - Automatic Teller Machines

Every member of Byteland Credit Society is entitled to loan any amount of Bytelandish ducats unless it is 1030 or more, but he has to return the whole amount within seven days. There are 100 ATMs in the Client Service Room of the Society. They are numbered from 0 to 99. Every ATM can perform one action only: it can pay or receive a fixed amount. The i-th ATM pays 2i ducats if i is even or it receives 2i ducats if i is odd. If a client is going to loan a fixed sum of money it is necessary to check if he is able to get the money using every ATM at most once. If so, numbers of ATMs he has to use should be determined. It is also necessary to check if the client can return the money in a similar way, and if so, to determine numbers of ATMs he has to use.

Example

A client who is going to loan 7 ducats gets 16 ducats from the ATM # 4 and 1 ducat from the ATM # 0 and then he returns 8 ducats in the ATM # 3 and 2 ducats in the ATM # 1. In order to return the amount of 7 ducats he receives 1 ducat from the ATM # 0 and then he returns 8 ducats in ATM # 3.

Task

Write a program that:

  • reads the number of clients n, for every client reads from the same file the amount of money he is going to loan;
  • checks for every client if he is able to get the money using every ATM at most once and if so, determines the numbers of ATMs he has to use;
  • outputs the results.

Input

In the first line of input there is one positive integer n <= 10000, which equals the number of clients.

In each of the following n lines there is one positive integer less than 1030 (at most 30 decimal digits). The number in the i-th line describes the amount of ducats which the client i is going to loan.

Output

For each client you should output two lines with a decreasing sequence of positive integers from the range [0..99] separated by single spaces, or one word "No":

In the first line of the i-th pair of lines there should be numbers of ATMs (in decreasing order) that the client i should use to get his loan or one word "No" if the loan cannot be received according to the rules;

In the second line of the i-th pair there should be numbers of ATMs (in decreasing order) which the client i should use to return his loan or the word "No".

Example

Sample input:
2
7
633825300114114700748351602698

Sample output:
4 3 1 0
3 0
No
99 3 1

Added by:Michał Czuczman
Date:2004-08-10
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:5th Polish Olympiad in Informatics, stage 3 (Piotr Chrząstowski-Wachtel)

hide comments
2010-06-17 02:03:44 ~!(*(@*!@^&
63 machines are enough,lol.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.