Как известно, все люди делятся на две группы: те, кто ещё не теряли важные данные, и те, кто уже делают бэкапы. Кирилл, находящийся на пути из первой группы во вторую после инцидента с тестами, описанного в задаче «Очередной пробный тур», решил, что существующие решения для резервного копирования данных не устраивают его по тем или иным причинам. Именно поэтому Кирилл решился на создание собственной системы резервного копирования, которую он решил назвать незатейливо, но гордо: «Защитная Бэкап-Система», сокращённо ЗБС. Ошибки в такой важной системе недопустимы, поэтому Кирилл попросил вас протестировать бета-версию своего продукта.

ЗБС устроена следующим образом: пусть в локальной сети работают n компьютеров, пронумерованных целыми числами от 1 до n. Некоторые пары компьютеров соединены проводами. В целях экономии локальная сеть не содержит лишних проводов, то есть между любыми двумя компьютерами в сети существует единственный путь. Изначально на i-м компьютере записано a_i байт информации. ЗБС умеет обрабатывать два типа запросов:

1. Скопировать всю информацию с компьютера номер v на все соседние компьютеры (то есть на те компьютеры, которые непосредственно соединены с ним проводом). При этом если до копирования на компьютере v было x_v байт информации, то после копирования на всех соседних с ним компьютерах становится на x_v байт информации больше, а на самом компьютере v остаётся x_v байт информации.
2. Вывести объём информации на компьютере номер v в данный момент. Так как этот объём может расти очень быстро, необходимо вывести лишь его остаток от деления на число 10⁹ + 7.

Для тестирования ЗБС необходимо написать программу, которая будет быстро обрабатывать описанные выше запросы. Этим вам сейчас и предстоит заняться.

В первой строке дано целое число n (1 ≤ n ≤ 10⁵) — количество компьютеров в сети. Во второй строке даны целые числа a₁, …, a_n — объём информации (в байтах) на компьютерах в начальный момент времени (0 ≤ a_i ≤ 10⁹). В каждой из следующих n − 1 строк записаны целые числа x и y (1 ≤ x, y ≤ n; x ≠ y), обозначающие наличие провода между компьютерами с номерами x и y. Гарантируется, что сеть является связной.

В следующей строке дано целое число m (1 ≤ m ≤ 10⁵) — количество запросов к системе. Далее в m строках перечислены запросы в порядке их выполнения. Каждый запрос задаётся парой целых чисел t и v (1 ≤ t ≤ 2; 1 ≤ v ≤ n), где число t задаёт тип запроса, а число v — номер компьютера, к которому применяется запрос.

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