В городе Осколково есть кампус, состоящий из n студенческих общежитий, n университетов и n военкоматов. Изначально i-е общежитие принадлежит i-му университету и приписано к i-му военкомату.
Жизнь бурлит, и в кампусе постоянно происходят изменения. Изменения бывают четырех типов:
- Университет под номером aj объединяется с университетом bj, после чего все общежития, которые принадлежали университету bj, переходят под контроль университета aj, а университет bj перестает существовать.
- Военкомат под номером cj объединяется с военкоматом dj, после чего все общежития, которые были приписаны к военкомату dj, переходят под контроль военкомата cj, а военкомат dj перестает существовать.
- Университет под номером xj производит заселение. Путь kxj — количество общежитий, которые принадлежат этому университету в момент заселения. Тогда количество студентов в каждом общежитии университета xj увеличивается на kxj (обратите внимание, чем больше общежитий принадлежат университету, тем больше студентов заселяется в каждое общежитие университета).
- Военкомат под номером yj производит облаву на все подконтрольные ему общежития и забирает из них всех студентов.
Таким образом, в любой момент времени каждое общежитие относится только к одному университету и одному военкомату. Изначально все общежития пусты.
Вам требуется обрабатывать изменения, происходящие в кампусе, а также отвечать на запросы, сколько человек живёт в общежитии qj в данный момент времени.
Выходные данные
В i-й строке выведите ответ на i-й запрос количества человек в общежитии.
Примечание
Рассмотрим первый тестовый пример:
- При первом запросе университету 1 принадлежит только общежитие номер 1, значит после запроса в общежитии 1 будет жить 1 студент.
- После третьего запроса университету номер 1 принадлежат общежития 1 и 2.
- Четвертый запрос увеличивает на 2 количество студентов, живущих в общежитиях 1 и 2, принадлежащих университету номер 1. После этого в первом общежитии живет 3 студента, а во втором — 2 студента.
- При пятом запросе обнуляется количество студентов, живущих в общежитии номер 1, приписанном к военкомату номер 1.