D. Кампус
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

В городе Осколково есть кампус, состоящий из n студенческих общежитий, n университетов и n военкоматов. Изначально i-е общежитие принадлежит i-му университету и приписано к i-му военкомату.

Жизнь бурлит, и в кампусе постоянно происходят изменения. Изменения бывают четырех типов:

  1. Университет под номером aj объединяется с университетом bj, после чего все общежития, которые принадлежали университету bj, переходят под контроль университета aj, а университет bj перестает существовать.
  2. Военкомат под номером cj объединяется с военкоматом dj, после чего все общежития, которые были приписаны к военкомату dj, переходят под контроль военкомата cj, а военкомат dj перестает существовать.
  3. Университет под номером xj производит заселение. Путь kxj — количество общежитий, которые принадлежат этому университету в момент заселения. Тогда количество студентов в каждом общежитии университета xj увеличивается на kxj (обратите внимание, чем больше общежитий принадлежат университету, тем больше студентов заселяется в каждое общежитие университета).
  4. Военкомат под номером yj производит облаву на все подконтрольные ему общежития и забирает из них всех студентов.

Таким образом, в любой момент времени каждое общежитие относится только к одному университету и одному военкомату. Изначально все общежития пусты.

Вам требуется обрабатывать изменения, происходящие в кампусе, а также отвечать на запросы, сколько человек живёт в общежитии qj в данный момент времени.

Входные данные

В первой строке записаны два целых числа n и m (1 ≤ n, m ≤ 5·105) — число общежитий и число запросов соответственно.

В следующих m строках находятся запросы, каждый из которых задан в одном из следующих форматов:

  • «U aj bj» — объединение университетов;
  • «M cj dj» — объединение военкоматов;
  • «A xj» — заселение в университет xj;
  • «Z yj» — облава в военкомате yj;
  • «Q qj» — запрос количества человек в общежитии qj.
Все числа в запросах целые положительные и не превосходят n. Гарантируется, что на момент запроса университеты и военкоматы, фигурирующие в запросе, существуют.
Выходные данные

В 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
Примечание

Рассмотрим первый тестовый пример:

  • При первом запросе университету 1 принадлежит только общежитие номер 1, значит после запроса в общежитии 1 будет жить 1 студент.
  • После третьего запроса университету номер 1 принадлежат общежития 1 и 2.
  • Четвертый запрос увеличивает на 2 количество студентов, живущих в общежитиях 1 и 2, принадлежащих университету номер 1. После этого в первом общежитии живет 3 студента, а во втором — 2 студента.
  • При пятом запросе обнуляется количество студентов, живущих в общежитии номер 1, приписанном к военкомату номер 1.