Олимпиадный тренинг

Задача . E. Caisa и дерево


Задача

Темы: Деревья Перебор математика *2100 теория чисел поиск в глубину и подобное

Caisa сейчас дома и его сын придумал для него простую задачку.

Задано корневое дерево, состоящее из n вершин, пронумерованных от 1 до n (вершина 1 — корень дерева). В каждой вершине записано некоторое значение. Требуется ответить на q запросов. Каждый запрос является одним из следующих:

  • Формат запроса «1 v». Выпишем последовательность вершин вдоль пути от корня до вершины v: u1, u2, ..., uk (u1 = 1; uk = v). Выведите такую вершину ui, что gcd(значение вершины ui, значение вершины v) > 1 и i < k. Если существует несколько таких вершин, выведите вершину с максимальным значением i. Если таких вершин вовсе нет, выведите -1.
  • Формат запроса «2 v w». Нужно изменить значение, записанное в вершине v, на w.

Вам заданы все запросы, помогите Caisa справиться с этой задачей.

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

В первой строке записаны два целых числа n, q (1 ≤ n, q ≤ 105).

Вторая строка содержит n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 2·106), где ai обозначает значение, записанное в вершине i изначально.

В каждой из следующих n - 1 строк записаны два целых числа xi и yi (1 ≤ xi, yi ≤ n; xi ≠ yi), обозначающие, что в дереве есть ребро между вершинами xi и yi.

В каждой из следующих q строк задан запрос в формате, описанном выше. Для каждого запроса выполняются следующие неравенства: 1 ≤ v ≤ n и 1 ≤ w ≤ 2·106. Обратите внимание: не более 50 запросов из всех меняют значение в вершине.

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

Для каждого запроса первого типа выведите ответ на него.

Примечание

Запись gcd(x, y) обозначает наибольший общий делитель целых чисел x и y.


Примеры
№Входные данныеВыходные данные
1 
4 6
10 8 4 3
1 2
2 3
3 4
1 1
1 2
1 3
1 4
2 1 9
1 4
 
-1
1
2
-1
1

time 10000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++5
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет