Statement
Nikita has a profound collection of rocks, all of which have names. In his spare time, Nikita loves to play with his rocks. He does this by arranging his rocks in a line. He occasionally adds more rocks to the end of the line. Unfortunately, he has so many rocks, that he often forgets which rocks he already added. He is not allowed to add a rock that already exists in the line (because they're all unique!). He may also switch the position of two rocks. More importantly, the most fun part is finding the mass of a few consecutive rocks! Obviously, you get the mass of each rock from its name. The name of each rock is unique and consists only of lowercase letters. The longest name Nikita will assign a rock is 100 letters long. The mass of a rock is the sum of the letters in its name, where a = 1, b = 2, c = 3 … z = 26. E.g. rock will have a mass of 47.
Input
You will execute (1 ≤ C ≤ 100 000) commands. There are 5 types of commands, in the following format:
- A R - add rock R to the end of the line, R is a string – the name of the rock, output "Can't add R" if rock R already exists in the line.
- S X Y - swap the position of rocks X and Y – X and Y are both strings – the name of the two rocks, it is guaranteed that both X and Y exist in the line.
- M X Y - output the mass of rocks in between (inclusive) the rocks X and Y. Both the rocks are guaranteed to exist in the line.
- R X Y - replace rock X with new rock Y – X and Y are both strings. X is guaranteed to exist in the line and Y is guaranteed to not exist in the line.
- N - output the number of rocks currently in the line.
Output
Output depends on the commands in input. See the input specification. All output for each command goes on its own separate line.
Example input
12 A a A b A c M a c M b c S a c M b a R c d M d b A c A d N
Example output
6 5 3 6 Can't add d 4
Explanation
After the first 3 commands, the rocks that exist in the line are a, b, c, in that order. The mass of a to c is a + b + c = 1 + 2 + 3 = 6. The mass of b, c is 2 + 3 = 5. The position of a and b are swapped so that the line is now c, b, a. The mass of b and a is 2 + 1 = 3. Rock c is taken out and replaced with rock d so the line becomes d, b, a. The mass of d and b is 4 + 2 = 6. Rock c gets added successfully into the line, which is now d, b, a, c. Rock d can't get added since it already exists. Finally, there are 4 rocks in the line at the end.
Time and memory limit:
- 2 seconds
- 256MB
Problem source: DMOJ