/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
// C++ program to implement persistent segment
// tree.
#define MAXN 1000002
/* data type for individual
* node in the segment tree */
struct node
{
// stores sum of the elements in node
int val;
// pointer to left and right children
node* left, *right;
// required constructors........
node() {}
node(node* l, node* r, int v)
{
left = l;
right = r;
val = v;
}
};
// input array
int arr[MAXN];
// root pointers for all versions
node* version[MAXN];
// Constructs Version-0
// Time Complexity : O(nlogn)
void build(node* n,int low,int high)
{
if (low==high)
{
n->val = arr[low];
return;
}
int mid = (low+high) / 2;
n->left = new node(NULL, NULL, 0);
n->right = new node(NULL, NULL, 0);
build(n->left, low, mid);
build(n->right, mid+1, high);
n->val = n->left->val + n->right->val;
}
/**
* Upgrades to new Version
* @param prev : points to node of previous version
* @param cur : points to node of current version
* Time Complexity : O(logn)
* Space Complexity : O(logn) */
void upgrade(node* prev, node* cur, int low, int high,
int idx, int value)
{
if (idx > high or idx < low or low > high)
return;
if (low == high)
{
// modification in new version
cur->val = value;
return;
}
int mid = (low+high) / 2;
if (idx <= mid)
{
// link to right child of previous version
cur->right = prev->right;
// create new node in current version
cur->left = new node(NULL, NULL, 0);
upgrade(prev->left,cur->left, low, mid, idx, value);
}
else
{
// link to left child of previous version
cur->left = prev->left;
// create new node for current version
cur->right = new node(NULL, NULL, 0);
upgrade(prev->right, cur->right, mid+1, high, idx, value);
}
// calculating data for current version
// by combining previous version and current
// modification
cur->val = cur->left->val + cur->right->val;
}
int query(node* n, int low, int high, int l, int r)
{
if (l > high or r < low or low > high)
return 0;
if (l <= low and high <= r)
return n->val;
int mid = (low+high) / 2;
int p1 = query(n->left,low,mid,l,r);
int p2 = query(n->right,mid+1,high,l,r);
return p1+p2;
}
/*int main(int argc, char const *argv[])
{
// creating Version-0
// storing root node for version-0
version[0] = root;
// upgrading to version-1
version[1] = new node(NULL, NULL, 0);
upgrade(version[0], version[1], 0, n-1, 4, 1);
// upgrading to version-2
version[2] = new node(NULL, NULL, 0);
upgrade(version[1],version[2], 0, n-1, 2, 10);
cout << "In version 1 , query(0,4) : ";
cout << query(version[1], 0, n-1, 0, 4) << endl;
cout << "In version 2 , query(3,4) : ";
cout << query(version[2], 0, n-1, 3, 4) << endl;
cout << "In version 0 , query(0,3) : ";
cout << query(version[0], 0, n-1, 0, 3) << endl;
return 0;
}*/
ll N;
vector<ll> com; //last index of Seg Tree after command i
vector<ll> s; //size of word after command i
ll V;
void Init()
{
N=1000000; REP(i,0,N) {arr[i]=0;}
node* root = new node(NULL, NULL, 0);
build(root, 0, MAXN-1); version[0]=root; V=1;
s.pb(0); com.pb(0);
}
void TypeLetter(char L)
{
ll u = (ll) (L-'a');
version[V] = new node(NULL,NULL,0);
upgrade(version[V-1],version[V],0,MAXN-1,s.back(),u);
s.pb(s.back()+1); com.pb(V); V++;
}
void UndoCommands(int U)
{
ll root_ind = com[com.size()-1-U]; ll cursize = s[com.size()-1-U]; s.pb(cursize);
version[V] = new node(NULL,NULL,0);
upgrade(version[root_ind],version[V],0,MAXN-1,MAXN-1,0);
com.pb(V); V++;
}
char GetLetter(int P)
{
ll ans = query(version[V-1],0,MAXN-1,P,P);
char c_ans = (char) ('a' + ans);
return c_ans;
}
