В городе Осколково есть кампус, состоящий из n студенческих общежитий, n университетов и n военкоматов. Изначально i-е общежитие принадлежит i-му университету и приписано к i-му военкомату.
Жизнь бурлит, и в кампусе постоянно происходят изменения. Изменения бывают четырех типов:
Таким образом, в любой момент времени каждое общежитие относится только к одному университету и одному военкомату. Изначально все общежития пусты.
Вам требуется обрабатывать изменения, происходящие в кампусе, а также отвечать на запросы, сколько человек живёт в общежитии qj в данный момент времени.
В первой строке записаны два целых числа n и m (1 ≤ n, m ≤ 5·105) — число общежитий и число запросов соответственно.
В следующих m строках находятся запросы, каждый из которых задан в одном из следующих форматов:
В i-й строке выведите ответ на i-й запрос количества человек в общежитии.
2 7
A 1
Q 1
U 1 2
A 1
Z 1
Q 1
Q 2
1
0
2
5 12
U 1 2
M 4 5
A 1
Q 1
A 3
A 4
Q 3
Q 4
Z 4
Q 4
A 5
Q 5
2
1
1
0
1
Рассмотрим первый тестовый пример:
Название |
---|