Description

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 and thrifty 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.
Furthermore, Niflheimr likes to reuses the same expression many times because a expression may have several sub-expressions (i.e. *-43+21 contains +21, -43, *-43+21).
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.

Hint: If you got a TLE, 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, *parent;
} Node;

-------------------- 2020/04/13 16:40 Important Update --------------------
Because of the property of % operator, there will be 2 kind of answer for each output.
For example, 10006 mathematically equals to -1 under module 10007, while 10006 is not equal to -1 under % operation
( 10006%10007 = 10006, -1%10007 = -1).
To avoid this situation, Please revise each result r into the output x which satisfies:

• r mathematically equals to x under module 10007.
• 0 ≤ x < 10007

Ex: -1, -10 should be revised into 10006, 9997 respectively.

 

Input

First line of input is an integer N, indicating the # of operations.
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(個位數).

There’s one kind of operations on the each of following N lines.
Type of operations:

• “D A B”: delete from A-th character to B-th character in the expression.
• “Q A”: print the value of sub-expression with root at A-th 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∗10⁵
• 1 ≤ N ≤ 10⁵
• The height of the binary tree is always ≤ 20.
• 1 ≤ A, B ≤ length of expression
• The expression is always valid after each operation “D A B”.
• The expression will never be empty.
• There won’t be any cross-subtree deletion, i.e. the following case won’t happen in our testcase:
  

Output

Print the value of sub-expression for each operation “Q A”.
Niflheimr hates negative and big numbers, since it will make calculation more complex. So for every output, please print the result after modulo 10007, which means the output is between 0~10006.

 

Explantation of Sample IO

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss