Diamond Cipher

Time limit1sMemory limit512 MB

Summary

The program writes each password as signed powers of three and lists the Up and Down switches.

Level: Medium6 of 10
Topics: Math, String, Greedy
Solved: No attempts yet

Problem

A renowned jewelry company has hired you to build safe-securing software. The company makes two kinds of safes for storing diamonds: one with $20$ switches and one with $200$ switches. To open a safe you need a password made of digits. Write a program that, given a password, tells you how to set the switches.

The switches are numbered starting from $0$ , and switch $i$ is assigned the value $3^i$ . Each switch has three states: Up, Middle, and Down. The safe opens when the sum of the values of the switches turned Up, minus the sum of the values of the switches turned Down, equals the password.

Write a program that:

reads the safe passwords from standard input,
computes a switch setting for each password,
writes the result to standard output.

Input

The first line contains the number of passwords $N$ ( $1 \le N \le 250$ ). Each of the next $N$ lines contains one safe password, given as a non-negative integer with no leading zeros. In half of the tests every password corresponds to a safe with $20$ switches; in the other half a safe with $200$ switches may be required.

Output

For each password, print the switch setting that opens the safe on two lines. On the first line, print the number of switches turned Up, followed by their numbers in ascending order. On the second line, print the number of switches turned Down, followed by their numbers in ascending order. Separate all numbers on a line with a single space. If no switch is turned Up (or Down), print just $0$ on that line.

Examples3

Example 1
Input
```
2
5
10
```
Expected output
```
1 2
2 0 1
2 0 2
0
```
Example 2
Input
```
1
1
```
Expected output
```
1 0
0
```

Example 3

Input

Expected output