/*input
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;
#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"
const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;
template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }
template<typename T>
void print(vector<T> vec, string name = "") {
cout << name;
for (auto u : vec)
cout << u << ' ';
cout << '\n';
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// struct node {
// char val;
// int prior;
// int cnt;
// node *left = NULL, *right = NULL;
// node(char a) : val(a), prior(rng()), cnt(1) { }
// node(node *kit) {
// val = kit->val;
// prior = kit->prior;
// cnt = kit->cnt;
// left = kit->left;
// right = kit->right;
// }
// };
// inline int cnt(node *t) { return (t ? t->cnt : 0); }
// inline void upd_cnt(node *t) { if (t) t->cnt = cnt(t->left) + cnt(t->right) + 1; }
// void merge(node *&t, node *l, node *r) {
// if (!l or !r)
// t = (l ? l : r);
// else if (l->prior < r->prior)
// merge(r->left, l, r->left), t = r;
// else
// merge(l->right, l->right, r), t = l;
// upd_cnt(t);
// }
// void split(node *t, int key, node *&l, node *&r, int add = 0) {
// if (!t)
// return void(l = r = NULL);
// int imp_key = add + cnt(t->left);
// if (key <= imp_key)
// split(t->left, key, l, t->left, add), r = t;
// else
// split(t->right, key, t->right, r, imp_key + 1), l = t;
// upd_cnt(t);
// }
// void insert(node *&curr, node *ka) {
// if (!curr) curr = ka;
// else if (ka->prior > curr->prior) {
// ka->left = curr;
// curr = ka;
// // split(curr, ka->key, ka->left, ka->right), curr = ka;
// } else {
// if (!curr->right) {
// insert(curr->right, ka);
// } else {
// node *naujas = new node(curr->right);
// insert(naujas, ka);
// curr->right = naujas;
// }
// }
// upd_cnt(curr);
// }
// // void insert(node *&curr, node *ka) {
// // if (!curr)
// // curr = ka;
// // else if (ka->prior > curr->prior)
// // split(curr, ka->key, ka->left, ka->right), curr = ka;
// // else
// // insert(ka->key < curr->key ? curr->left : curr->right, ka);
// // }
// char gauk(node *curr, int k) {
// int imp_key = cnt(curr->left);
// // printf("k = %d, imp_key = %d, currval = %c\n", k, imp_key, curr->val);
// if (imp_key == k) return curr->val;
// else if (imp_key < k)
// return gauk(curr->right, k - imp_key - 1);
// else
// return gauk(curr->left, k);
// }
// vector<node*> buvo;
char last;
vii jump;
void Init() {
jump = vii((int)1e6, vi(20, -1));
// buvo.push_back(new node(' '));
}
void TypeLetter(char L) {
jump[0][4] = 5;
// // printf("type L = %c\n", L);
// if (buvo.empty()) {
// buvo.push_back(new node(L));
// } else {
// buvo.push_back(new node(buvo.back()));
// insert(buvo.back(), new node(L));
// }
last = L;
}
void UndoCommands(int U) {
// printf("Undo U = %d\n", U);
// printf("kit = %d\n", (int)buvo.size() - 1 - U);
// node *naujas = new node(buvo[buvo.size() - 1 - U]);
// buvo.push_back(naujas);
}
char GetLetter(int P) {
// printf("gaunu P = %d\n", P);
return last;
// assert(buvo.size());
// return gauk(buvo.back(), P);
}
