很像二進制的做法，並且需要用到大數
//====================================================================||
// ||
// ||
// Author : GCA ||
// 6AE7EE02212D47DAD26C32C0FE829006 ||
//====================================================================||
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
using namespace std;
#ifdef ONLINE\_JUDGE
#define ll "%lld"
#else
#define ll "%I64d"
#endif
typedef unsigned int uint;
typedef long long int Int;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\\n")
#define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln()
#define De(x)printf(#x"%d\\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\
printf("%d ",dp\[htx\]\[hty\]);}Pln();}
#define M 55
#define PII pair<int,int\>
#define PB push\_back
#define oo INT\_MAX
#define Set\_oo 0x3f
#define Is\_debug true
#define debug(...) if(Is\_debug)printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#define FOR(it,c) for(\_\_typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define eps 1e-6
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
int tmp=min(x,y);
return min(tmp,z);
}
int max3(int x,int y,int z){
int tmp=max(x,y);
return max(tmp,z);
}
class bignum{
public:
Int str\[1000\];
int byte\[1000\];
int bnum;
static const int maxn=50;
bignum(){
Set(str,0);
bnum=-1;
}
void print(){
int i=0;
for(i=maxn-1;i>0;i--)
if(str\[i\]!=0)break;
printf("%lld",str\[i\]);
for(i--;i>=0;i--){
printf("%04lld",str\[i\]);
}
}
bool bigz(){
for(int i=maxn-1;i>=0;i--){
if(str\[i\]>0)return true;
}
return false;
}
void div(){
Int c=0;
bnum=0;
while(bigz()){
c=0;
for(int i=maxn-1;i>=0;i--){
Int tmp=(str\[i\]+c);
str\[i\]=tmp/2;
c=(tmp%2)\*10000;
}
byte\[bnum++\]=c/10000;
}
}
void sub(int a){
Int c=0;
for(int i=0;i<maxn;i++){
Int tmp=str\[i\]-a-c;
a=0;
if(tmp<0){
c=1;
str\[i\]=tmp+10000;
}else{
str\[i\]=tmp;
c=0;
}
}
}
void mul(int a){
Int c=0;
Int str2\[1000\];
Set(str2,0);
for(int i=0;i<maxn;i++){
Int tmp=str\[i\]\*a;
str2\[i\]+=tmp%10000;
c=tmp/10000;
for(int k=i+1;k<maxn;k++){
Int tmp2=str2\[k\]+c;
str2\[k\]+=tmp2%10000;
c=tmp2/10000;
}
}
memcpy(str,str2,sizeof(str));
}
};
int main() {
ios\_base::sync\_with\_stdio(0);
char str\[1000\],stmp\[10\];
while(~scanf("%s",str)){
if(!strcmp(str,"0"))break;
for(int i=0;i<10;i++)stmp\[i\]='0';
bignum n;
bignum p;
int len=strlen(str);
int j=0,s=0;
for(int i=len-1;i>=0;i--){
stmp\[3-j\]=str\[i\];
j++;
if(j>=4||i==0){
stmp\[4\]='';
sscanf(stmp,"%lld",&n.str\[s\]);
s++;
for(int k=0;k<4;k++)stmp\[k\]='0';
j=0;
}
}
n.sub(1);
p.str\[0\]=1;
// n.print();
// Pln();
n.div();
if(n.bnum==0){
printf("{ }\\n");
}else{
printf("{");
for(int i=0;i<n.bnum;i++){
// printf("%d\\n",n.byte\[i\]);
if(n.byte\[i\]){
printf(" ");
p.print();
if(i!=n.bnum-1)printf(",");
}
p.mul(3);
}
printf(" }\\n");
}
}
}