//#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
#include <iostream>
#include <random>
#include <unordered_map>
#include <unordered_set>
#ifdef _MSC_VER
#include <opencv2/core.hpp>
#include <opencv2/highgui.hpp>
#include <opencv2/imgproc.hpp>
#include <ppl.h>
//#include <windows.h>
#endif

using namespace std;

//呪文
#define DUMPOUT cerr
#define dump(...) DUMPOUT<<"  ";DUMPOUT<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl;DUMPOUT<<"    ";dump_func(__VA_ARGS__)

typedef unsigned uint; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; typedef pair<string, string> pss;
template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const pair<_KTy, _Ty>& m) { o << "{" << m.first << ", " << m.second << "}"; return o; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const map<_KTy, _Ty>& m) { if (m.empty()) { o << "{ }"; return o; } o << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _KTy, typename _Ty> ostream& operator << (ostream& o, const unordered_map<_KTy, _Ty>& m) { if (m.empty()) { o << "{ }"; return o; } o << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const vector<_Ty>& v) { if (v.empty()) { o << "{ }"; return o; } o << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const set<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } o << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { o << ", " << *itr; } o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const unordered_set<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } o << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { o << ", " << *itr; }	o << "}"; return o; }
template <typename _Ty> ostream& operator << (ostream& o, const stack<_Ty>& s) { if (s.empty()) { o << "{ }"; return o; } stack<_Ty> t(s); o << "{" << t.top(); t.pop(); while (!t.empty()) { o << ", " << t.top(); t.pop(); } o << "}";	return o; }
template <typename _Ty> ostream& operator << (ostream& o, const list<_Ty>& l) { if (l.empty()) { o << "{ }"; return o; } o << "{" << l.front(); for (auto itr = ++l.begin(); itr != l.end(); ++itr) { o << ", " << *itr; } o << "}"; return o; }
template <typename _KTy, typename _Ty> istream& operator >> (istream& is, pair<_KTy, _Ty>& m) { is >> m.first >> m.second; return is; }
template <typename _Ty> istream& operator >> (istream& is, vector<_Ty>& v) { for (size_t i = 0; i < v.size(); i++) is >> v[i]; return is; }
namespace aux { // print tuple
	template<typename Ty, unsigned N, unsigned L> struct tp { static void print(ostream& os, const Ty& v) { os << get<N>(v) << ", "; tp<Ty, N + 1, L>::print(os, v); } };
	template<typename Ty, unsigned N> struct tp<Ty, N, N> { static void print(ostream& os, const Ty& v) { os << get<N>(v); } };
}

template<typename... Tys> ostream& operator<<(ostream& os, const tuple<Tys...>& t) { os << "{"; aux::tp<tuple<Tys...>, 0, sizeof...(Tys)-1>::print(os, t); os << "}"; return os; }

template<typename A, size_t N, typename T> inline void Fill(A(&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); }

void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) { DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...); }

#define PI 3.14159265358979323846
#define EPS 1e-10
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
#define REP(i,n)  FOR(i,0,n)
#define all(j) (j).begin(), (j).end()
#define SZ(j) ((int)(j).size())
#define fake false



struct SXor128 {
	unsigned x, y, z, w;
	SXor128() { x = 123456789; y = 362436069; z = 521288629; w = 88675123; }
	SXor128(int _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; }
	void setSeed() { x = 123456789; y = 362436069; z = 521288629; w = 88675123; }
	void setSeed(int _w) { x = 123456789; y = 362436069; z = 521288629; w = _w; }
	unsigned nextUInt() {
		unsigned t = (x ^ (x << 11));
		x = y; y = z; z = w;
		return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
	}
	unsigned nextUInt(unsigned mod) {
		unsigned t = (x ^ (x << 11));
		x = y; y = z; z = w;
		w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
		return w % mod;
	}
	unsigned nextUInt(unsigned l, unsigned r) {
		unsigned t = (x ^ (x << 11));
		x = y; y = z; z = w;
		w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
		return w % (r - l + 1) + l;
	}
	double nextDouble() {
		return double(nextUInt()) / UINT_MAX;
	}
} rnd;

class timer {
	vector<timer> timers;
	int n = 0;
public:
#ifdef _MSC_VER
	double limit = 9.9;
#else
	double limit = 9.9;
#endif
	double t = 0;
	timer() {}
	timer(int size) : timers(size) {}
	bool elapses() const {
		return time() - t > limit;
	}
	void measure() {
		t = time() - t;
		++n;
	}
	void measure(char id) {
		timers[id].measure();
	}
	void print() {
		if (n % 2)
			measure();
		for (int i = 0; i < 128; ++i) {
			if (timers[i].n)
				cerr << (char)i << ' ' << timers[i].t << 's' << endl;
		}
		cerr << "  " << t << 's' << endl;
	}
	static double time() {
#ifdef _MSC_VER
		return __rdtsc() / 2.6e9;
#else
		unsigned long long a, d;
		__asm__ volatile ("rdtsc" : "=a" (a), "=d" (d));
		return (d << 32 | a) / 2.6e9;
#endif
	}
} timer(128);



constexpr int N = 10000;
//string S;

const vector<ll> base_cost({ 150, 2000, 30000, 600000, 10000000 });
const vector<ll> base_prod({ 1, 10, 120, 2000, 25000 });

enum EAct { CLICK, BUY, SELL, REINFORCE, ENHCLICK, NOTHING };
const vector<EAct> acts({ CLICK, BUY, REINFORCE, ENHCLICK, SELL });
const map<string, EAct> dict_acts_se({ { "click", CLICK },{ "buy", BUY },{ "sell", SELL },{ "reinforce", REINFORCE },{ "enhclick", ENHCLICK },{ "nothing", NOTHING } });
const map<EAct, string> dict_acts_es({ { CLICK, "click" } ,{ BUY, "buy" },{ SELL, "sell" },{ REINFORCE, "reinforce" },{ ENHCLICK, "enhclick" },{ NOTHING, "nothing" } });

enum EBld { HAND, LILY, FACTORY, CASINO, GRIMOIRE, NONE };
const vector<EBld> blds({ HAND, LILY, FACTORY, CASINO, GRIMOIRE });
const map<string, EBld> dict_blds_se({ { "hand", HAND },{ "lily", LILY },{ "factory", FACTORY },{ "casino", CASINO },{ "grimoire", GRIMOIRE },{ "none", NONE } });
const map<EBld, string> dict_blds_es({ { HAND, "hand" },{ LILY,"lily" },{ FACTORY,"factory" },{ CASINO, "casino" },{ GRIMOIRE,"grimoire" },{ NONE,"none" } });

enum EEff { FEVER = 1, SALE = 2 };

class State {
public:
	typedef shared_ptr<State> StatePtr;

	shared_ptr<string> S;

	// history : 解答出力用．あとで undo とか実装するかも
	char hist_act[N];
	char hist_bld[N];
	//string hist_act;
	//string hist_bld;

	// ターン数
	int turn;

	// effect のフラグ
	int eff_state;
	// effect の残りターン数
	int eff_turn[3];

	// 所持クッキー
	ll cookies;
	// cookies per click
	ll cpc;

	// 施設保有数
	short num_blds[5];
	// 基本生産性
	ll prod[5];
	// 購入コスト
	ll cost_buy[5];
	// 施設強化コスト
	ll cost_rif[5];
	// クリック強化コスト
	ll cost_enhclk;

	// 最もグレードの高い施設
	EBld bld_maxgrade;

	State() {
		turn = 0;
		cookies = 0;
		cpc = 1;
		eff_state = eff_turn[FEVER] = eff_turn[SALE] = 0;
		for (const auto& act : acts) {
			num_blds[act] = 0;
			prod[act] = base_prod[act];
			cost_buy[act] = cost_rif[act] = base_cost[act];
			cost_rif[act] *= 10;
		}
		cost_enhclk = 15;
		bld_maxgrade = HAND;
	}

	// 行動．行動不可能(クッキー不足, 施設数 0 での売却)の場合 false が返る
	bool action(EAct act, EBld bld) {

		// 消費クッキーの計算
		ll gains = 0, losts = 0, sells = 0;
		switch (act)
		{
		case CLICK:	gains = cpc; break;
		case BUY: losts = cost_buy[bld]; break;
		case SELL:
			if (!num_blds[bld]) return false;	// 売る施設がないよ
			sells = cost_buy[bld] * 5 / 6;	// 現在の施設価格
			sells = (sells + 3) / 4;		// 25%
			break;
		case REINFORCE: losts = cost_rif[bld]; break;
		case ENHCLICK: losts = cost_enhclk; break;
		}
		ll diff =
			gains * ((eff_state & FEVER) ? 7 : 1)
			+ sells
			- ((eff_state & SALE) ? (losts * 9 + 9) / 10 : losts);

		// クッキー不足
		if (cookies + diff < 0) return false;

		// 各種 status の更新
		switch (act)
		{
		case BUY:
			num_blds[bld]++;
			cost_buy[bld] = (cost_buy[bld] * 6 + 4) / 5;
			break;
		case SELL:
			num_blds[bld]--;
			cost_buy[bld] = cost_buy[bld] * 5 / 6;
			break;
		case REINFORCE:
			prod[bld] <<= 1;
			cost_rif[bld] *= 10;
			break;
		case ENHCLICK:
			cpc <<= 1;
			cost_enhclk *= 10;
			break;
		}

		// history に追加
		hist_act[turn] = act;
		hist_bld[turn] = bld;
		//hist_act.push_back(act);
		//hist_bld.push_back(bld);

		// 行動によるクッキー総数の更新
		cookies += diff;

		// 生産によるクッキー総数の更新
		ll fever_const = (eff_state & FEVER) ? 7 : 1;
		for (const auto& bld : blds) cookies += num_blds[bld] * prod[bld] * fever_const;

		// 特殊効果のターン減少
		eff_turn[FEVER]--;
		eff_turn[SALE]--;
		eff_state ^= eff_turn[FEVER] ? 0 : FEVER;
		eff_state ^= eff_turn[SALE] ? 0 : SALE;

		// 特殊効果の発動
		switch (S->at(turn))
		{
		case 'B':
			cookies = (cookies * 101 + 99) / 100;
			break;
		case 'F':
			eff_state |= FEVER;
			eff_turn[FEVER] = 20;
			break;
		case 'S':
			eff_state |= SALE;
			eff_turn[SALE] = 1;
			break;
		}

		// ターン数インクリメント
		turn++;
		return true;
	}

	// 十分なクッキーが集まるまで click してからコマンドを実行
	bool autoplay(EAct act, EBld bld, int turn_range = N) {
		int cur_turn = turn;
		while (!action(act, bld)) {
			action(CLICK, NONE);
			// turn_range ターン経過した場合は false
			if (turn >= min(N, cur_turn + turn_range)) return false;
		}
		return true;
	}

	// 効率のいい ( Log(1+ΔCpT/CpT)/T の最も大きな ) ものを貪欲に実行する
	// https://ita.hatenadiary.jp/entry/20130920/p1
	// undo があるといいんだけど
	bool greedy() {
		ll cur_turn = turn;
		ll cur_prod_sum = 0;
		for (auto bld : blds)
			cur_prod_sum += num_blds[bld] * prod[bld];
		cur_prod_sum += cpc;

		double best_score = DBL_MIN;
		EAct best_act;
		EBld best_bld;

		for (auto act : { BUY, REINFORCE }) {
			for (auto bld : blds) {
				State next_state(*this);
				if (!next_state.autoplay(act, bld)) continue;
				ll next_turn = next_state.turn;
				ll next_prod_sum = 0;
				for (auto b : blds)
					next_prod_sum += next_state.num_blds[b] * next_state.prod[b];
				next_prod_sum += cpc;
				double score = log(1 + double(next_prod_sum - cur_prod_sum) / next_prod_sum) / (next_turn - cur_turn);
				if (score > best_score) {
					best_score = score;
					best_act = act;
					best_bld = bld;
				}
			}
		}
		for (auto act : { ENHCLICK }) {
			EBld bld = NONE;
			State next_state(*this);
			if (!next_state.autoplay(act, bld)) continue;
			ll next_turn = next_state.turn;
			ll next_prod_sum = 0;
			for (auto b : blds)
				next_prod_sum += next_state.num_blds[b] * next_state.prod[b];
			next_prod_sum += cpc;
			double score = log(1 + double(next_prod_sum - cur_prod_sum) / next_prod_sum) / (next_turn - cur_turn);
			if (score > best_score) {
				best_score = score;
				best_act = act;
				best_bld = bld;
			}
		}
		if (best_score == DBL_MIN) return false;
		autoplay(best_act, best_bld);
		if (best_bld != NONE) {
			bld_maxgrade = (EBld)max((int)bld_maxgrade, (int)best_bld);
		}
		return true;
	}

	void show_log(ostream& os) {
		map<char, int> eff_cnt;
		for (auto s : *S) {
			if (s != 'N') {
				eff_cnt[s]++;
				os << s;
			}
		}
		os << endl;
		os << eff_cnt << endl;
		for (int i = 0; i < turn; i++) {
			EAct act = EAct(hist_act[i]);
			EBld bld = EBld(hist_bld[i]);
			if (act == CLICK) continue;

			os << dict_acts_es.at(act);
			if (bld != NONE) os << " " << dict_blds_es.at(bld);
			os << endl;
		}
	}
};

typedef shared_ptr<State> StatePtr;

StatePtr solve(const StatePtr& init_state) {
	init_state->autoplay(ENHCLICK, NONE);
	init_state->autoplay(ENHCLICK, NONE);

	ll best_cookies = init_state->cookies;
	StatePtr best_state = init_state;

	SXor128 r(init_state->cookies % 1000000007);

	//int loopcnt = 0;
	for (int turn_thresh = 5500; turn_thresh <= 8500; turn_thresh += 50) {
		
		StatePtr state(new State(*init_state));

		int total_blds = 0;
		vector<int> max_num_blds;
		ll total_sell = 0;
		while (state->turn < N) {
			if (state->turn < turn_thresh) {
				state->greedy();
			}
			else {
				if (!total_blds) {
					for (auto bld : blds) {
						total_blds += state->num_blds[bld];
						max_num_blds.push_back(state->num_blds[bld]);
					}
				}

				if (state->turn < 9970)
					state->action(CLICK, NONE);
				else {
					ll maxsell = -1;
					EBld maxbld = NONE;
					for (auto bld : blds) {
						if (!state->num_blds[bld]) continue;
						ll sell = state->cost_buy[bld] * 5 / 6;
						sell = (sell + 3) / 4;
						if (maxsell < sell) {
							maxsell = sell;
							maxbld = bld;
						}
					}
					if (maxsell != -1) {
						total_sell += maxsell;
						state->action(SELL, maxbld);
					}
				}
			}
		}

		if (state->cookies > best_cookies) {
			best_state = state;
			best_cookies = state->cookies;
			//cerr << best_cookies << ": " << max_num_blds << endl;
		}
	}

	//cerr << loopcnt << endl;

	return best_state;
}

//vector<StatePtr> getAllNextStates(const StatePtr& nowState) {
//	vector<EAct> acts({ BUY, REINFORCE, ENHCLICK });
//	vector<EBld> blds({ HAND, LILY, FACTORY, CASINO, GRIMOIRE });
//
//	vector<StatePtr> res;
//
//	ll now_turn = nowState->turn;
//	for (auto& act : acts) {
//		if (act != ENHCLICK) {
//			for (auto& bld : blds) {
//				StatePtr newState(new _State(*nowState));
//				if (!newState->autoplay(act, bld)) continue;
//				if (newState->turn >= 9000 || newState->turn - now_turn > 500) continue;
//				res.push_back(newState);
//			}
//		}
//		else {
//			EBld bld = NONE;
//			StatePtr newState(new _State(*nowState));
//			if (!newState->autoplay(act, bld)) continue;
//			if (newState->turn >= 9000 || newState->turn - now_turn > 500) continue;
//			res.push_back(newState);
//		}
//	}
//	return res;
//}

string testcase(unsigned seed) {
	SXor128 r(seed);
	REP(i, 100) r.nextUInt();

	int range_min = 0, range_max = 199;
	string S(N, 'N');
	while (range_min < N) {
		int idx = r.nextUInt(range_min, range_max);
		if (idx >= N) break;
		int kind = r.nextUInt(3);
		if (kind == 0) S[idx] = 'B';
		else if (kind == 1) S[idx] = 'F';
		else S[idx] = 'S';
		range_min = idx + 100;
		range_max = idx + 200;
	}

	return S;
}


//#ifdef _MSC_VER
//typedef struct SMouseParams {
//	int event, x, y, flags;
//	SMouseParams() {}
//	SMouseParams(int event, int x, int y, int flags) : event(event), x(x), y(y), flags(flags) {}
//}*SMouseParamsPtr;
//
//void mouse_callback(int event, int x, int y, int flags, void* params) {
//	SMouseParamsPtr mp = static_cast<SMouseParamsPtr>(params);
//	mp->event = event;
//	mp->x = x;
//	mp->y = y;
//	mp->flags = flags;
//}
//
//struct Button {
//	//int x1, y1, x2, y2;
//	cv::Rect roi;
//	EAct act;
//	EBld bld;
//	string text;
//	cv::Mat_<cv::Vec3b> img;
//
//	Button(int x1, int y1, int x2, int y2, EAct act, EBld bld, string text)
//		: roi(x1, y1, x2 - x1, y2 - y1), act(act), bld(bld), text(text)
//	{
//		img = cv::Mat_<cv::Vec3b>(y2 - y1, x2 - x1, cv::Vec3b(255, 255, 255));
//		cv::rectangle(img, cv::Rect(0, 0, x2 - x1, y2 - y1), cv::Scalar(0, 0, 0), 3, cv::LINE_AA);
//		cv::putText(img, text, cv::Point(20, y2 - y1 - 32), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
//		//ll diff = state->diff(act, bld);
//		//cv::putText(img, to_string(abs(diff)), cv::Point(20, y2 - y1 - 8), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
//	}
//};
//
//void play(StatePtr state) {
//
//	int W = 500;
//	int H = 500;
//	cv::Mat_<cv::Vec3b> board(H, W, cv::Vec3b(255, 255, 255));
//
//	vector<Button> buttons;
//	buttons.emplace_back(0, 0, 250, 250, CLICK, NONE, "cookie");
//	buttons.emplace_back(0, 250, 250, 500, ENHCLICK, NONE, "enhance click");
//	for (int i = 0; i < 5; i++) {
//		buttons.emplace_back(250, 100 * i, 500, 100 * i + 50, BUY, EBld(i), "buy " + dict_blds_inv.at(EBld(i)));
//		buttons.emplace_back(250, 100 * i + 50, 500, 100 * i + 100, REINFORCE, EBld(i), "reinforce " + dict_blds_inv.at(EBld(i)));
//	}
//
//	for (int i = 0; i < buttons.size(); i++) {
//		cv::Mat img_roi = board(buttons[i].roi);
//		//dump(buttons[i].roi, buttons[i].img.size(), board.size());
//		buttons[i].img.copyTo(img_roi);
//	}
//
//	cv::String winname = "window";
//	cv::namedWindow(winname);
//	cv::imshow(winname, board);
//	cv::waitKey(15);
//
//	SMouseParamsPtr mp(new SMouseParams(0, 0, 0, 0));
//	cv::setMouseCallback(winname, mouse_callback, mp);
//
//	state->autoplay(ENHCLICK, NONE);
//	state->autoplay(ENHCLICK, NONE);
//	REP(i, 5) state->autoplay(BUY, HAND);
//	state->autoplay(REINFORCE, HAND);
//	REP(i, 2) state->autoplay(BUY, HAND);
//	state->autoplay(ENHCLICK, NONE);
//
//
//	int key;
//	do {
//		cv::Mat_<cv::Vec3b> cur_board = board.clone();
//
//		cv::Point p(mp->x, mp->y);
//
//		EAct act_selected;
//		EBld bld_selected;
//		ll diff_selected;
//		ll fever_const = (state->effects_state & FEVER) ? 7 : 1;
//		bool sale = state->effects_state & SALE;
//		ll total_cps = 0;
//		for (int i = 0; i < buttons.size(); i++) {
//			EAct act = buttons[i].act;
//			EBld bld = buttons[i].bld;
//			ll diff = state->diff(act, bld);
//			cv::putText(cur_board(buttons[i].roi), to_string(abs(diff)), cv::Point(20, buttons[i].roi.height - 8), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
//			if (act == BUY) {
//				ll sum_cps = state->blds_count[bld] * state->productivity[bld] * fever_const;
//				total_cps += sum_cps;
//				cv::putText(cur_board(buttons[i].roi), to_string(state->blds_count[bld]),
//					cv::Point(200, buttons[i].roi.height - 32), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
//				cv::putText(cur_board(buttons[i].roi), to_string(sum_cps),
//					cv::Point(150, buttons[i].roi.height - 8), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
//			}
//			if (buttons[i].roi.contains(p)) {
//				act_selected = buttons[i].act;
//				bld_selected = buttons[i].bld;
//				diff_selected = diff;
//			}
//		}
//
//		cv::putText(cur_board, "turn: " + to_string(state->turn), cv::Point(20, 20), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
//		cv::putText(cur_board, "cps: " + to_string(total_cps), cv::Point(20, 40), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
//
//		cv::putText(cur_board(buttons[0].roi), to_string(state->total_cookies), cv::Point(20, 100), cv::FONT_HERSHEY_SIMPLEX, 0.5, cv::Scalar(0, 0, 0), 1, cv::LINE_AA);
//
//		//cv::imshow(winname, cur_board);
//		//key = cv::waitKey(15);
//
//		if (/*key == 'a'*/ state->turn < 8000) {
//			optimal(state);
//			// 足りなかったら足りるまでクッキーを焼き続ける
//			//if(!state->autoplay(act_selected, bld_selected)) return;
//		}
//		else if (/*key == 'c'*/ state->turn < 9950) {
//			if (!state->autoplay(CLICK, NONE)) return;
//		}
//		else if (state->turn < 10000) {
//			ll maxsell = -1;
//			EBld maxbld = NONE;
//			for (int i = 4; i >= 0; i--) {
//				ll d = state->diff(SELL, EBld(i));
//				if (maxsell < d) {
//					maxsell = d;
//					maxbld = EBld(i);
//				}
//			}
//			if (maxsell != -1) {
//				state->action(SELL, maxbld, maxsell);
//			}
//		}
//		else {
//			key = 27;
//		}
//
//	} while (key != 27);
//}
//#endif

#ifdef _MSC_VER
int _main() {
	timer.measure();

	cin.tie(0);
	ios::sync_with_stdio(false);

	int T = 32;
	vector<ll> scores(T);
	vector<unsigned> seeds(T);
	REP(i, 100) rnd.nextUInt();

	REP(i, T) seeds[i] = rnd.nextUInt();

	concurrency::parallel_for(0, T, [&](int i) {
		//double start = timer.time() - timer.t;
		//double end = start + 9.0;
		unsigned seed = seeds[i];

		shared_ptr<string> S(new string(testcase(seed)));
		StatePtr state(new State);
		state->S = S;

		state = solve(state);

		cerr << seed << " ";
		scores[i] = state->cookies;
	}, concurrency::affinity_partitioner());

	cerr << endl;
	cerr << "total: " << accumulate(all(scores), 0LL)  << endl;

	return 0;
}
#endif

int main() {
	timer.measure();

	cin.tie(0);
	ios::sync_with_stdio(false);

	shared_ptr<string> S(new string);
	int buf;
	cin >> buf >> (*S);
	//shared_ptr<string> S(new string(testcase(0)));

	StatePtr state(new State);
	state->S = S;

	state = solve(state);

	for (int i = 0; i < state->turn; i++) {
		EAct act = EAct(state->hist_act[i]);
		EBld bld = EBld(state->hist_bld[i]);
		cout << dict_acts_es.at(act);
		if (bld != NONE) cout << " " << dict_blds_es.at(bld);
		cout << endl;
	}

	return 0;
}