To celebrate the beginning of year 2015, Department of Lighting and Decoration (DLD) decided to lighten up the Dhaka-Chittagong highway. However, DLD does not have much funding for this project and they want to reduce the power usage for the lighting as well. So, they came up with a brilliant idea.

DLD will ask the houses near the highway to contribute and voluntarily set up lighting along the highway. The position of a light is marked by the distance from the starting point, D meter. Only one light can be placed within one meter and it will always be placed at integer meter only.

The lights can vary in power as well. Ranging from few Watts light up to a thousand Watt bulb. The power of each light, P, is represented in Watts which is also integer. A zero Watt light indicates either there is no light at that position or the light is turned off.

Initially, everyone who wants to participate would report where they want to setup the light, D, and the power of the light, P. Later, any of the two operations can be performed:

• Setup a light with new power. If there was a light at that location, it will be replaces, otherwise new light will be installed.
• Measure the total power of all the lights between two locations (inclusive)

Input

The input consists of less than 5 cases. Each case starts with N, the number of lights initially set up, on a line by itself. N can be as large as 200000. Each of next N lines contains one number between 0 and 1000, the initial powers of the lights in the order 1 to N. Then follow a number of actions, each on a line by itself. The number of actions can be as many as 200000. There are three types of action:

• “S D P” - set light at location D to P Watts.
• “M D1 D2” - measure the total power between the location D1 and D2 inclusive. D1 is smaller than or equal to D2.
• “END” - end of this case. Appears only once at the end of a list of actions.

A case with N = 0 signals the end of the input and it should not be processed.

Output

For each case in the input produce a line ‘Case n:’, where n is the case number, starting from 1.

For each measurement in the input, output a line containing one number: the measured power in Watts. The actions should be applied to the lights in the order given in the input. Print a blank line between cases.

Example

Input:
3
100
100
100
M 1 1
M 1 3
S 2 200
M 1 2
S 3 0
M 2 3
END
10
1
2
3
4
5
6
7
8
9
10
M 1 10
END
0

Output:
Case 1:
100
300
300
200

Case 2:
55

Authored By: Md. Imrul Hasan