#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <fstream>
#include <cassert>
#include <map>
#include <array>
#include <deque>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;

const int L = 26;
const int MN = 1000000;

struct S {
	int size=0;
	int st[L/2+2];

	int operator[](int i) const { return st[i]; }
	int& operator[](int i) { return st[i]; }

	bool operator==(const S& s) const {
		return size==s.size && equal(st,st+size,s.st);
	}
	bool operator<(const S& s) const {
		if (size!=s.size) return size<s.size;
		for(int i=0; i<size; ++i) if (st[i]!=s[i]) return st[i]<s[i];
		return 0;
	}

	S& operator+=(int x) {
		st[size++] = x;
		return *this;
	}
	void resize(int i) {size=i;}
};
ostream& operator<<(ostream& o, const S& s) {
	o<<'[';
	for(int i=0; i<s.size; ++i) o<<s[i]<<' ';
	o<<']';
	return o;
}
struct U {
	char op=0;
	int v:24=0;

	S apply(S st) const {
		switch(op) {
		case '+':
			st[st.size-1] -= v;
			st[st.size++] = v;
			break;
		case '*':
			st[st.size-1] /= v;
			st[st.size++] = v;
			break;
		case 'S':
			swap(st[st.size-2],st[st.size-1]);
			break;
		case 'D':
			--st.size;
			break;
		case 'O':
			--st.size;
			break;
		case 'R':
			swap(st[st.size-1],st[st.size-2]);
			swap(st[st.size-2],st[st.size-3]);
			break;
		default:
			cout<<"Invalid op "<<op<<'\n';
			assert(0);
		}
		return st;
	}
};

//typedef array<char,L+1> C;
struct C {
	static constexpr int size = 24;

	unsigned char data[size];
	U undo;

	unsigned char operator[](int i) const { return data[i]; }
	unsigned char& operator[](int i) { return data[i]; }
	unsigned char* begin(){return data;}
	unsigned char* end(){return data+size;}

	bool operator==(const C& c) const {
		for(int i=0; i<size; ++i) if (data[i]!=c[i]) return 0;
		return 1;
	}
	bool operator<(const C& c) const {
		for(int i=0; i<size; ++i) if (data[i]!=c[i]) return data[i]<c[i];
		return 0;
	}
};
namespace std {
	template<>
	struct hash<S> {
		size_t operator()(const S& s) const {
			size_t r=s.size;
			const int P = 1e9+7;
			for(int i=0;i<s.size; ++i) {
				r = P*r + s[i];
			}
			return r;
		}
	};
	template<>
	struct hash<C> {
		size_t operator()(const C& s) const {
			size_t r=0;
			const int P = 1e9+7;
			bool mid=0;
			for(int i=0;i<(int)s.size && (mid || s[i]!=0); ++i) {
				r = P*r + s[i];
				mid |= s[i]&128;
			}
			return r;
		}
	};
};
ostream& operator<<(ostream& o, const C& s) {
	o<<'[';
	bool mid=0;
	for(int i=0; i<(int)s.size && (mid || s[i]!=0); ++i) o<<(int)s[i]<<' ',mid=s[i]&128;
	o<<']';
	return o;
}
C pack(const S& s) {
	C c={};
	int j=0;
	for(int i=0; i<s.size; ++i) {
		int x = s[i];
		int sj = j;
		while(x>0) {
			if (j>=c.size) return {};
			c[j++] = char(x%128);
			x /= 128;
		}
		reverse(c.begin()+sj,c.begin()+j);
		while(sj+1<j) c[sj++]|=128;
	}
	if (j>c.size) cout<<"too big "<<j<<" for "<<s<<' '<<c<<'\n';
	assert(j<=(int)c.size);
	return c;
}
S unpack(const C& c) {
	S s={};
	bool mid=0;
	for(int i=0; i<(int)c.size && (mid||c[i]!=0); ++i) {
		int x = c[i];
		s[s.size] *= 128;
		if (x & 128) {
			s[s.size] += x&127;
			mid=1;
		} else {
			s[s.size++] += x;
			mid=0;
		}
	}
	return s;
}

deque<C> nxt;

struct From {
	ull hash;
	U undo;
	bool operator<(const From& f) const {
		return hash < f.hash;
	}
	bool operator==(const From& f) const { return hash==f.hash; }
};
From toFrom(const C& c) {
	ull p = 999999999999999989;
	ull h = 0;
	for(int i: c.data) {
		h = p*h + i;
	}
	return {h, c.undo};
}

//unordered_map<C,U> from;
deque<From> from;
//deque<pair<lll,U>> from;
int maxL=L;

void add(const S& prev, const S& st, char op) {
	if (st.size > maxL) return;
	int sum=0;
	for(int i=0; i<st.size; ++i) sum += st[i];
	if (sum >= MN) return;
#if 0
	C pst = pack(st);
	cout<<"st: "<<st<<'\n';
	cout<<"pst: "<<pst<<'\n';
	cout<<"unpack: "<<unpack(pst)<<'\n';
#endif
//	assert(unpack(pack(st))==st);
//	for(int i=0; i<st.size; ++i) assert(st[i]>0);
#if 0
	auto& u = from[pack(st)];
	if (!u.op) {
		u={op,prev[prev.size-1]};
		nxt.push_back(st);
	}
#else
	C c = pack(st);
	if (c[0]==0) return;
	if (binary_search(from.begin(),from.end(),toFrom(c))) return;
	c.undo = {op, prev[prev.size-1]};
	nxt.push_back(c);
#endif
}

void go(const S& st) {
#if 0
	cout<<"go "<<st.length()<<" : ";
	for(int i=0; i<st.length(); ++i)cout<<int(st[i])<<' ';
	cout<<'\n';
#endif
	int c = st.size;
	S s = st;
	// DUP
	s += s[c-1];
	add(st,s,'D');
	if (c>=2) {
		// OVER
		s[c] = s[c-2];
		add(st,s,'O');

#if 1
		if (c>=3) {
			// ROT
			s.resize(c);
			s[c-3] = st[c-2];
			s[c-2] = st[c-1];
			s[c-1] = st[c-3];
			add(st,s,'R');
			s[c-3] = st[c-3];
			s[c-2] = st[c-2];
			s[c-1] = st[c-1];
		}
#endif

#if 1
		if (st[c-1]!=st[c-2]) {
			// SWAP
			s.resize(c);
			swap(s[c-2],s[c-1]);
			add(st,s,'S');
			swap(s[c-2],s[c-1]);
		}
#endif

		s.resize(c-1);
		// +
		s[c-2] += st[c-1];
		if (s[c-2]<MN) add(st,s,'+');

#if 1
		if (st[c-2]!=1 && st[c-1]!=1 && ll(st[c-2])*st[c-1]<MN) {
			// *
			s[c-2] = st[c-2] * st[c-1];
			add(st,s,'*');
		}
#endif
	}
}
int blen[MN];

string getPath(int x) {
	S s;
	s += x;
	string res;
//	cout<<"getting path "<<x<<'\n';
	while(s.size>1 || s[0]>1) {
#if 0
		cout<<"path st "<<s.length()<<" : ";
		for(int i: s)cout<<i<<' ';
		cout<<'\n';
#endif

#if 0
		const auto& f = from[pack(s)];
//		cout<<"from "<<f.first.length()<<' '<<f.second<<'\n';
		res += f.op;
		s = f.apply(s);
#else
		auto it = lower_bound(from.begin(),from.end(),toFrom(pack(s)));
		assert(it != from.end());
		s = it->undo.apply(s);
		res += it->undo.op;
#endif
	}
	reverse(res.begin(),res.end());
	return res;
}

int main() {
	cout<<sizeof(S)<<' '<<sizeof(C)<<' '<<sizeof(U)<<' '<<sizeof(lll)<<' '<<sizeof(pair<ll,U>)<<'\n';
	deque<C> cur;
	S s0;
	s0+=1;
	cur.push_back(pack(s0));
	for(int i=0; i<L; ++i) {
		maxL = L-i;
		//if (i+5<L) maxL = L-i-1;
		cout<<"\nLEVEL "<<i<<' '<<cur.size()<<" ; "<<from.size()<<'\n';
		for(const C& c: cur) {
			go(unpack(c));
		}
		for(const C& c: nxt) {
			S s = unpack(c);
			if (s.size==1) {
				int x = s[0];
				assert(x>0);
				if (x<MN && blen[x]==0) blen[x]=i+1;
			}
		}
		sort(nxt.begin(),nxt.end());
		nxt.erase(unique(nxt.begin(),nxt.end()),nxt.end());

		for(const C& c: nxt) from.push_back(toFrom(c));
		sort(from.begin(),from.end());
		from.erase(unique(from.begin(),from.end()),from.end());

		swap(cur,nxt);
		nxt.clear();
	}
	ofstream out("best.out");
	for(int i=2; i<MN; ++i) {
		if (blen[i]>0) {
			//cout<<i<<" -> "<<blen[i]<<" : "<<getPath(i)<<'\n';
			out<<i<<' '<<getPath(i)<<'\n';
		}
	}
}