CS
Problems Base course RU

Problem

Every version of a text

tree text editors version control randomized

An editor keeps the whole history of a text: each edit creates a new version, the old ones remain, and any of them can be edited, which creates branches as in a version control system. Version 0 is the original text. Requests are of three kinds:

  • + v p s: take version v, insert the string s before the character with number p (characters are numbered from zero; p may equal the length, then at the end), and save the result as the next version;
  • - v p k: take version v, delete k characters starting from the p-th, and save it as the next version;
  • ? v p: print the character with number p in version v.

New versions are numbered in order of appearance: the first edit creates version 1, the second version 2, and so on; questions create no versions. The texts in the tests are War and Peace in English translation, with spaces replaced by _ and line breaks removed; the inserted words are taken from the same text.

In the example version 1 is NatashaIlyinichna__Rostova, and its seventh character is I; version 2 is the same without the first eight characters and begins with l; and version 0 still begins with N.

Input

The first line holds the original text: from 1 to 300,000 visible ASCII characters without spaces. The second holds the number of requests q (1 ≤ q ≤ 20,000). Then q lines with requests; an inserted string is from 1 to 100 visible ASCII characters without spaces. All requests are valid: the version exists and positions lie within the text.

Output

The answers to the questions, one character per line.

Examples

Example 1

Input
Natasha_Rostova
5
+ 0 7 Ilyinichna_
? 1 7
- 1 0 8
? 2 0
? 0 0
Output
I
l
N

Limits

Time · Python
5000 ms
Time · Go
1500 ms
Memory
256 MB
Judging
7 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Keeping each version as a copy will not work: twenty thousand copies of three hundred thousand characters is six gigabytes. How can a new version share with the old one everything the edit did not touch?

2Hint 2

Text as a tree of pieces with an implicit key: a rope. Insertion and deletion are splits and merges of the tree. And if splits and merges never change existing nodes but create new ones, the old version stays intact.

3The idea

A rope on a treap with an implicit key: a node holds a piece of text (up to 256 characters), a priority and the subtree length. The operations split (the first k characters and the rest) and merge (concatenating two trees) are written so that instead of changing a node they create a copy of it with new links: path copying. Then each edit creates O(log n) new nodes and perhaps cuts one piece, and all versions live at the same time: a version is a root. The character with number p is found by a descent on subtree lengths.

4Walkthrough

Insertion: split version v at position p, merge the left part, a tree of the pieces of s and the right part. Deletion: split at p, cut the first k characters off the right part and throw them away, merge the rest. If a split falls inside a piece, the piece is divided into two new nodes. Priorities are random; a copy of a node keeps its priority, so the shape of the tree stays correct.

Memory is O(n/256 + q log n) nodes plus the cut pieces. In Python it is convenient to keep nodes as immutable tuples: then a shared node simply cannot be changed.

4+Solution
5Complexity

O(log n + 256) per edit and O(log n) per question, on average over the random priorities.

6Common mistakes
  • A copy per version. Correct, but the memory is the sum of the lengths of all versions. This is wrong.py: it exceeds the memory limit.
  • Changing nodes on a split. An ordinary split rewrites links in existing nodes, and the old versions that share them quietly change. Answers to questions about old versions become wrong.
  • New priorities for copies. If a copied node is given a new random priority, the order “the parent’s priority is greater” breaks, and merge stops keeping the tree balanced.

Algorithms behind it

DS Data structure Rope Text in pieces in the leaves of a tree: an insertion or deletion in the middle is a path to a leaf and one piece; the line number comes from counters in the nodes. O(log n + C) per insertion, deletion, access 1 problem DS Data structure Persistent data structures Every change is a new version, and the old ones live on; only the path from the root is copied. The median of any period is a difference of two versions. O(log n) per change and query 1 problem DS Data structure Treap A key and a random priority: O(log n) depth on average, split and merge, an array with piece reversal in O(log n). O(log n) on average for search, insert, delete, split and merge 1 problem
The algorithms catalogue