| VK Cup 2016 - Раунд 3 |
|---|
| Закончено |
В одной социальной сети есть n официальных страниц компаний, пронумерованных от 1 до n. Также имеется n компаний, при этом i-й компании принадлежит страница номер i.
Недавно появилась новая функция подписки. Теперь каждая официальная страница подписана ровно на одну другую официальную страницу. Более того, не разрешена ситуация, когда страница компании i подписана на страницу компании j, а страница компании j подписана на страницу компании i. Разумеется, официальная страница компании не может быть подписана сама на себя.
Пусть страница i подписана на какую-то другую страницу j0. Также пусть на i подписаны k страниц j1, j2, ..., jk. Тогда те, кто заходят на страницу i, видят k + 2 различных рекламных объявления от компаний i, j0, j1, ..., jk. На страницу i ежедневно заходят ровно ti человек, и каждый из них нажимает ровно на одно рекламное объявление. Для каждой из k + 1 компании j0, j1, ..., jk на них кликнет ровно 
пользователей, которые зайдут на страницу компании i. Оставшиеся 
пользователей нажмут на рекламу компании i.
Суммарный доход компании равен количеству людей, которые нажмут на её рекламу.
Лимак и Радевуш просят вас помочь им. Изначально официальная страница компании i подписана на страницу fi. Вам требуется обработать q запросов трёх типов:
- 1 i j — официальная страница компании i теперь подписана на официальную страницу компании j. Гарантируется, что перед этим i не была подписана на j. Обратите внимание на дополнительное ограничение на количество запросов этого типа.
- 2 i — выведите суммарный доход компании i.
- 3 — выведите два целых числа: минимальный доход среди всех компаний и максимальный доход среди всех компаний.
В первой строке входных данных записаны два целых числа n и q (3 ≤ n ≤ 100 000, 1 ≤ q ≤ 100 000) — количество официальных страниц и количество запросов соответственно.
Во второй строке записаны n целых чисел t1, t2, ..., tn (1 ≤ ti ≤ 1012), где ti означает количество людей, ежедневно посещающих страницу компании i.
В третьей строке записано n целых чисел f1, f2, ..., fn (1 ≤ fi ≤ n). Изначально официальная страница компании i подписана на официальную страницу компании fi.
Далее следуют q строк, i-я из которых описывает i-й запрос. Первое число в каждой строке — это typei (1 ≤ typei ≤ 3) — тип соответствующего запроса.
Гарантируется, что будет не более 50 000 запросов первого типа и будет хотя бы один запрос второго или третьего типа (то есть потребуется вывести хотя бы одно число).
Также гарантируется, что ни в какой момент официальная страница не подписана сама на себя и две страницы не подписаны друг на друга.
Для каждого запроса второго типа выведите одно целое число — суммарный доход компании в данный момент. Для каждого запроса третьего типа выведите два целых числа — минимальный и максимальный доход компании соответственно.
5 12
10 20 30 40 50
2 3 4 5 2
2 1
2 2
2 3
2 4
2 5
1 4 2
2 1
2 2
2 3
2 4
2 5
3
10
36
28
40
36
9
57
27
28
29
9 57
В первом примере имеется 5 официальных страниц. На i-ю страницу ежедневно заходят i·10 пользователей.
На картинке количество пользователей записано в кружочке. Стрелочка из a в b означает, что страница a подписана на страницу b.
Левая картинка отражает стартовую ситуацию. Первая компания получает 
дохода от своей собственной страницы и 
дохода от страницы компании 2. Таким образом, суммарный доход равен 5 + 5 = 10. После первого запроса (2 1) следует вывести 10.
Правый рисунок показывает ситуацию после запроса 1 4 2 (после которого официальная страница 4 подписана на официальную страницу 2). Теперь первая компания всё ещё получает 5 единиц дохода от своей страницы, но только 
— от второй страницы. Таким образом, суммарный доход равен 5 + 4 = 9.
