Oscolcovo city has a campus consisting of n student dormitories, n universities and n military offices. Initially, the i-th dormitory belongs to the i-th university and is assigned to the i-th military office.
Life goes on and the campus is continuously going through some changes. The changes can be of four types:
Thus, at each moment of time each dormitory is assigned to exactly one university and one military office. Initially, all the dormitory are empty.
Your task is to process the changes that take place in the campus and answer the queries, how many people currently live in dormitory qj.
The first line contains two integers, n and m (1 ≤ n, m ≤ 5·105) — the number of dormitories and the number of queries, respectively.
Next m lines contain the queries, each of them is given in one of the following formats:
In the i-th line print the answer to the i-th query asking the number of people in the dormitory.
U 1 2
U 1 2
M 4 5
Consider the first sample test: