#include #include #include /* static bool debug = false; */ struct Vertex { const char *s; size_t weight; Vertex* left; Vertex* right; Vertex(const char *s, size_t weight) : s(s), weight(weight), left(NULL), right(NULL) {} Vertex(Vertex* left, Vertex* right, size_t weight) : s(NULL), weight(weight), left(left), right(right) {} }; class Rope { std::string s; Vertex *root; public: Rope(const std::string &s) : s(s) { root = new Vertex(&s[0], s.size()); } void process( int i, int j, int k ) { Vertex* left = NULL; Vertex* right = NULL; Vertex* out = NULL; int len = weight(root); /* if (debug) std::cout << std::endl << "PROCESS : " << i << " " << j << " " << k << std::endl; */ if (i > 0) { split(root, i, out); left = root; /* if (debug) { */ /* std::cout << " left : " << print(left) << std::endl; */ /* std::cout << " out : " << print(out) << std::endl; */ /* } */ } else { left = NULL; out = root; } if (len > (j + 1)) { split(out, (j - i + 1), right); /* if (debug) { */ /* std::cout << " out : " << print(out) << std::endl; */ /* std::cout << " right : " << print(right) << std::endl; */ /* } */ } else { right = NULL; } /* if (debug) std::cout << " concat left || right : "; */ root = concat(left, right); /* if (debug) std::cout << print(root) << std::endl; */ left = NULL; right = NULL; if (k > 0) { split(root, k, right); left = root; /* if (debug) { */ /* std::cout << " left : " << print(left) << std::endl; */ /* std::cout << " right : " << print(right) << std::endl; */ /* } */ root = concat(left, concat(out, right)); /* if (debug) std::cout << " root : " << print(root) << std::endl; */ } else { root = concat(out, root); /* if (debug) std::cout << " root : " << print(root) << std::endl; */ } } std::string result() { return print(root); } private: std::string print(Vertex *v) { /* std::cout << weight(v) << std::endl; */ if (v == NULL) return "NULL"; std::string res; in_order(v, res); return res; } void in_order(Vertex *v, std::string &r) { if (v == NULL) return; /* if (debug) { */ /* std::cout << v << " " << v->weight << " "; */ /* if (v->s != NULL) { */ /* for (int i = 0; i < v->weight; i++) */ /* std::cout << v->s[i]; */ /* } */ /* std::cout << std::endl << " " << v->left<< std::endl; */ /* std::cout << " " << v->right << std::endl; */ /* } */ in_order(v->left, r); if (v->s != NULL) { for (int i = 0; i < v->weight; i++) r.push_back(v->s[i]); } in_order(v->right, r); } size_t weight(Vertex *v) { size_t w = 0; while (v != NULL) { w += v->weight; v = v->right; } return w; } Vertex* concat(Vertex *left, Vertex *right) { if (right == NULL) return left; if (left == NULL) return right; return new Vertex(left, right, weight(left)); } // split into : [0 ; (key-1)] [key; ...] void split(Vertex* v, int key, Vertex*& outer) { /* if (debug) std::cout << " split " << key << " " << print(v) << std::endl; */ _split(v, key, outer); } int _split(Vertex* v, int key, Vertex*& outer) { if (v == NULL) return 0; if (key < v->weight) { if (v->left == NULL) { /* if (debug) std::cout << " found : " << v->s[key] << std::endl; */ Vertex *tmp = new Vertex(&v->s[key], v->weight - key); v->weight = key; outer = concat(tmp, outer); return v->weight; } else { outer = concat(v->right, outer); v->right = NULL; v->weight = _split(v->left, key, outer); // compress if (v->left != NULL && v->left->left != NULL && v->left->right == NULL) { Vertex *tmp = v->left; v->left = v->left->left; delete(tmp); } return v->weight; } } else { key -= v->weight; if (key == 0) { outer = concat(v->right, outer); v->right = NULL; return v->weight; } else { return v->weight + _split(v->right, key, outer); } } } }; int main() { std::ios_base::sync_with_stdio(0); std::string s; std::cin >> s; Rope rope(s); int actions; /* if (debug) std::cout << rope.result() << std::endl; */ std::cin >> actions; for (int action_index = 0; action_index < actions; ++action_index) { int i, j, k; std::cin >> i >> j >> k; rope.process(i, j, k); /* if (debug) std::cout << rope.result() << std::endl; */ } std::cout << rope.result() << std::endl; }