Description
This problem is the midterm exam bonus!
Niflheimr is a poor student. He can't afford to buy a scientific caculator, but his simple calculator can't type in a mathematical expression.
So he decided to create a calculator on his own!
He learned in class that he can evaluate an expression by converting the expression into prefix and create a binary tree accordingly.
Unfortunately, Niflheimr is a careless person. He often types the expression wrong, and if that happens, after he removed the wrong part, he has to rebuild the whole binary tree and calculate everything again. He thinks that rebuilding is too sloooooooooow, so he asks you to help him make it fast.
If you can help him correctly, he will feel happy and give you a big AC.
==========
Note (2018.4.11) : (Thanks J3soon for the reminder!) There won't be any cross-subtree deletion, i.e. the following case won't happen in our testcase:
Note2 (2018.4.12) : In this problem, the expression will never be empty.
Sorry for the incompleteness of the problem description ><"
==========
Hint: If you got a TLE in the last testcase, instead of rebuilding the tree all the time, try to add some extra field in the node inside the binary tree, e.g. size, and utilize them to speed up operations.
For example, you can define your Node inside the binary tree like this:
typedef struct _node {
int dark_magic; // ???
int size; // ??? Use this field to find the index of each node. Try figure out HOW TO by yourself!
int type; // which kind of operation is this node, e.g. NUM / ADD / SUB / MUL.
struct _node *left, *right;
} Node;
Input
First line of input is an integer N, indicating the # of deletions.
Second line of input is the expression in prefix. The expression contains only +, -, * and digits. All the number in the expression are between 1 and 9, that is, every number in the expression are DIGITS(個位數).
The following N lines are deletions, the format is "A B", indicating that Niflheimr wants to delete from Ath character to Bth character in the expression.
Note that the index starts from 1, and the index of the characters in the expression should be re-calculated after each deletion.
It is guaranteed that:
- The length of the expression is less than 3*105
- 1 ≤ N ≤ 3*104
- The height of the binary tree is always ≤ 20.
- The range of deletion is always within the expression, i.e. 1 ≤ A, B ≤ length of expression
- The expression is always valid after each operation.
Output
The output consists of N+1 lines.
First line of output is the result of the original expression.
The following N lines are the results after each deletion.
Niflheimr hates big numbers, since it will make calculation more complex. So for every output, please print the result after modulo 10007 (% 10007).