ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Уральская региональная командная олимпиада по программированию 2014

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Защитная Бэкап-Система

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Как известно, все люди делятся на две группы: те, кто ещё не теряли важные данные, и те, кто уже делают бэкапы. Кирилл, находящийся на пути из первой группы во вторую после инцидента с тестами, описанного в задаче «Очередной пробный тур», решил, что существующие решения для резервного копирования данных не устраивают его по тем или иным причинам. Именно поэтому Кирилл решился на создание собственной системы резервного копирования, которую он решил назвать незатейливо, но гордо: «Защитная Бэкап-Система», сокращённо ЗБС. Ошибки в такой важной системе недопустимы, поэтому Кирилл попросил вас протестировать бета-версию своего продукта.
ЗБС устроена следующим образом: пусть в локальной сети работают n компьютеров, пронумерованных целыми числами от 1 до n. Некоторые пары компьютеров соединены проводами. В целях экономии локальная сеть не содержит лишних проводов, то есть между любыми двумя компьютерами в сети существует единственный путь. Изначально на i-м компьютере записано ai байт информации. ЗБС умеет обрабатывать два типа запросов:
  1. Скопировать всю информацию с компьютера номер v на все соседние компьютеры (то есть на те компьютеры, которые непосредственно соединены с ним проводом). При этом если до копирования на компьютере v было xv байт информации, то после копирования на всех соседних с ним компьютерах становится на xv байт информации больше, а на самом компьютере v остаётся xv байт информации.
  2. Вывести объём информации на компьютере номер v в данный момент. Так как этот объём может расти очень быстро, необходимо вывести лишь его остаток от деления на число 109 + 7.
Для тестирования ЗБС необходимо написать программу, которая будет быстро обрабатывать описанные выше запросы. Этим вам сейчас и предстоит заняться.

Исходные данные

В первой строке дано целое число n (1 ≤ n ≤ 105) — количество компьютеров в сети. Во второй строке даны целые числа a1, …, an — объём информации (в байтах) на компьютерах в начальный момент времени (0 ≤ ai ≤ 109). В каждой из следующих n − 1 строк записаны целые числа x и y (1 ≤ x, yn; xy), обозначающие наличие провода между компьютерами с номерами x и y. Гарантируется, что сеть является связной.
В следующей строке дано целое число m (1 ≤ m ≤ 105) — количество запросов к системе. Далее в m строках перечислены запросы в порядке их выполнения. Каждый запрос задаётся парой целых чисел t и v (1 ≤ t ≤ 2; 1 ≤ vn), где число t задаёт тип запроса, а число v — номер компьютера, к которому применяется запрос.

Результат

На каждый запрос второго типа выведите в отдельной строке остаток от деления ответа на число 109 + 7.

Примеры

исходные данныерезультат
4
1 1 1 1
1 2
1 3
2 4
9
2 1
2 2
2 3
2 4
1 1
2 1
2 2
2 3
2 4
1
1
1
1
1
2
2
1
2
1 1
1 2
14
2 2
2 1
1 1
2 2
1 2
2 1
1 1
2 2
1 2
2 1
1 1
2 2
1 2
2 1
1
1
2
3
5
8
13
21
Автор задачи: Никита Сивухин
Источник задачи: Уральская региональная командная олимпиада по программированию 2014
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2030. Защитная Бэкап-Система