Kenya is the birthplace of some of the best long-distance runners of all times. Indeed, eight of the most recent ten best times in the traditional 41.195 km of the marathon have been set by runners from that country. Dennis Kimetto, Wilson Kipsang and Eliud Kipchoge are three such runners, and they want to beat their discipline's world record once more tomorrow September 27, when they compete in the 42^nd edition of the Berlin Marathon.

Kimetto, Kipsang and Kipchoge are good friends, and they like to train together running by the Tana river in order to appreciate the beautiful trees that grow there. There are N trees by the river, which we will number from 1 to N. The i-th tree is of the species S_i and stands at a distance of i meters from the mouth of the river. Our three runners are especially motivated by the sight of many trees of different species. For this reason, each training day they choose a tree with number K from 1 to N, and then run from the K-th tree following the river, i.e. in the direction of trees K-1, K-2 and so on, stopping only when they see a tree of some species they have already seen that day, or when they reach the mouth of the river, whichever comes first.

For example, if there are N = 4 trees of species S₁ = 1, S₂ = 2, S₃ = 1 and S₄ = 3, when they choose K = 4 the training consists in running 3 meters, from tree number 4 up to tree number 1 (where they stop because this tree is of the same species as tree number 3). However, if they chose K = 2 they would run two meters up to the mouth of the river, where they would stop even without having seen two trees of the same species as they went.

Long-distance running requires decades of training, and in this time it is common for some trees to fall during storms. When this happens, the fallen tree is immediately replaced by another one, not necessarily of the same species. Kimetto, Kipsang and Kipchoge keep a diary where they take note of all the information relevant to their training. In particular, they know the species of all trees, and which number they chose to start running each day of training. Can you help them calculate how much they ran each training day?

Input

There are multiple test cases in the input file. For each test case, the first line contains two integers N and R, representing respectively the number of trees by the river and the number of entries in the training diary (1 ≤ N, R ≤ 5 × 10⁴). The second line contains N integers S_i indicating the species of the i-th tree when the training began (1 ≤ S_i ≤ 10⁶ for i = 1, 2, ..., N). Each of the following R lines contains the description of an entry in the training diary, in chronological order. This description starts with a character which can be a 'C' if the entry corresponds to a fallen tree or an 'E' if it corresponds to a training day. The entries for fallen trees contain two integers K and S after the 'C', indicating that the K-th tree fell and was replaced by another tree of species S (1 ≤ K ≤ N and 1 ≤ S ≤ 10⁶). The entries for training days contain an integer K after the 'E', indicating that the runners began a training day by running from the K-th tree (1 ≤ K ≤ N). There will always be at least one entry for a training day in each test case.

Output

For each test case, print one line for each entry corresponding to a training day, indicating the number of meters Kimetto, Kipsang and Kipchoge ran during that day.

Example

Input:
4 2
1 2 1 3
E 4
E 2
10 10
1 2 3 4 5 6 7 8 9 10
E 1
E 2
E 3
E 4
E 5
E 6
E 7
E 8
E 9
E 10
5 7
1 2 3 4 5
E 3
E 5
C 3 1
E 4
C 2 5
E 3
E 5

Output:
3
2
1
2
3
4
5
6
7
8
9
10
3
5
3
2
3