马蜂丑，请轻喷。

我的思路就再题解区里面，可以去看。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;

typedef long long ll;
typedef double db;
typedef __int128 III;
const db eqs=1e-6;
const int inf=1e9;
void cmax(int &a,int b){a=max(a,b);}
void cmin(int &a,int b){a=min(a,b);}
bool db_eq(db a,db b){return fabs(a-b)<eqs;}

const int MAXN=10000+5;
string s; 
vector<int>a,b;
vector<int>st;
int c[MAXN][MAXN];

void clean1(){while(!a.empty()) a.pop_back();}
void clean2(){while(!b.empty()) b.pop_back();}

int div()
{
//	cout<<"514"<<endl;
	int yu=0,id,cur=-1;
	int len=a.size(),x=0;
	if(a.size()==1 && a[0]==1)
	{
		a[0]=0;
		return 1;
	}
	if(a.size()==1 && a[0]==2)
	{
		a[0]=0;
		return 2;
	}
	for(int i=0;i<len;i++)
	{
		if(x*10+a[i]>=3) 
		{
			id=i;
			break;
		}
		x=x*10+a[i];
	}
	yu=x;
//	cout<<id<<" "<<x<<" ";
	for(int i=id;i<len;i++)
	{
		b.push_back((a[i]+yu*10)/3);
		yu=(yu*10+a[i])%3;
	}
//	cout<<yu<<endl;
	clean1();
	for(int i=0;i<b.size();i++) a.push_back(b[i]);
	clean2();
	return yu;
}

void power()
{
	c[0][1]=1,c[0][2]=-1;
	for(int i=1;i<st.size();i++)
	{
		int id;
		for(int j=1;;j++) 
		{
			if(c[i-1][j]==-1) 
			{
				id=j-1;
				break;
			}
		}
//		cout<<id<<endl;
		for(int j=id;j>=1;j--)
		{
			c[i][j]+=c[i-1][j]*3;
			if(c[i][j]>=10) c[i][j-1]+=c[i][j]/10,c[i][j]%=10;
		}
		if(c[i][0]>0)
		{
			for(int j=id;j>=0;j--) c[i][j+1]=c[i][j];
			c[i][id+2]=-1;
			c[i][0]=0;
		}
		else c[i][id+1]=-1;
	}
}

void print()
{
	for(int i=0;i<a.size();i++) cout<<a[i];
	cout<<endl;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>s;
//	cout<<s<<endl;
	int len=s.size();
	for(int i=0;i<len;i++) a.push_back(s[i]-'0');
//	print();
	while(a[0]!=0)
	{
		st.push_back(div());
//		print();
//		cout<<114<<endl;
	}/*
	while(!st.empty())
	{
		cout<<st.top()<<" ";
		st.pop();
	}
	cout<<endl;*/
	power();/*
	cout<<st.size()<<endl;
	for(int i=0;i<st.size();i++) 
	{
		cout<<i<<" ";
		for(int j=1;;j++)
		{
			if(c[i][j]==-1)
			{
				cout<<endl;
				break;
			}
			cout<<c[i][j];
		}
	}*/
//	for(int i=0;i<st.size();i++) cout<<st[i]<<" ";cout<<endl;
	cout<<0<<endl;
	for(int i=0;i<st.size();i++)
	{
		int x=st[i];
		if(x==0) continue;
		if(x==1)
		{
			for(int j=1;;j++)
			{
				if(c[i][j]==-1)
				{
					cout<<" ";
					break;
				}
				cout<<c[i][j];
			}
		}
		else
		{
			for(int j=1;;j++)
			{
				if(c[i][j]==-1)
				{
					cout<<" ";
					break;
				}
				cout<<c[i][j];
			}
			for(int j=1;;j++)
			{
				if(c[i][j]==-1)
				{
					cout<<" ";
					break;	
				}
				cout<<c[i][j];
			}
		}
	}
	return 0;
}