#include<bits/stdc++.h> using namespace std; #define mp make_pair #define INF 10000000 #define MOD 1000000007 #define MID ((l+r)/2) #define HASHMOD 2305843009213693951 #define ll long long #define ull unsigned long long #define F first #define S second typedef pair<ll, ll> ii; typedef pair<ii, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef map<int, int> mii; #define EPS 1e-6 #define FOR(i,n) for(int i=0;i<((int)(n));i++) #define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++) #define FOA(v, a) for(auto v : a) static int last_id=0; struct trie{ trie* let[26]; int id; trie* par; char last; int s=0; trie(){ FOR(i,26) let[i] = nullptr; id = last_id++; } trie(char x, int ns, trie* p){ id = last_id++; FOR(i,26) let[i] = nullptr; last = x; s = ns; par = p; } trie* add(char x){ //cout<<"adding "<<x<<" to "<<last<<endl; if(let[x-'a']==nullptr) let[x-'a'] = new trie(x, s+1, par->let[last-'a']); return let[x-'a']; } }; static vector<trie*> history; trie* anc[1001000][30]; //unordered_map<trie*, vector<trie*> > anc; trie root; //bool used[1001000]; #define LAY 25 void prepr(trie* node){ //cout<<node->id<<endl; if(node==root.let[0]) return; //cout<<node->last<<endl; //cout<<node->par->last<<endl; anc[node->id][0] = node->par; FORi(i,1,LAY){ anc[node->id][i] = anc[anc[node->id][i-1]->id][i-1]; } //used[node->id] = true; } trie* ancest(trie* node, int x){ int ind=0; if(x>node->s) return root.let[0]; while(x){ if(x%2==1) node = anc[node->id][ind]; ind++; x/=2; } return node; } void Init() { //cout<<"INITED\n"; root.let[0] = new trie('a', 0, &root); history.push_back(root.let[0]); FOR(i,LAY) anc[root.let[0]->id][i] = root.let[0]; //prepr(root.let[0]); } void TypeLetter(char L) { history.push_back(history.back()->add(L)); //if(!used[history.back()->id]) prepr(history.back()); } void UndoCommands(int U) { history.push_back(history[history.size()-U-1]); } char GetLetter(int P) { //FOA(v,history) cout<<v<<" "<<v->last<<endl; int up = history.back()->s - P-1; return ancest(history.back(), up)->last; }