e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

ADA University - January 13 - Segment Tree

У країні невивчених уроків 2

prb4482 Тепер у Віті є програма, яка допомогає йому швидко знаходити НСД багатьох чисел. Тому стражі вирішили змінити правила: тепер Вітя повинен знайти найбільший спільний дільник (НСД) чисел на проміжку [l; r], а стражі – найменше спільне кратне (НСК), у кого получиться число меншим, той і виграє.

Вхідні дані

Перший рядок містить кількість елементів у масиві n (1n106). У другому рядку знаходиться n чисел – елементи ai (1ai109) масива. У третьому рядку знаходиться кількість запитів m (1m105). Далі у m рядках знаходиться по три числа q, l, r (1lrn). Якщо q = 1, потрібно визначити переможця для проміжка [l; r], якщо q = 2, то потрібно замінити елемент у позиції l на число r.

Вихідні дані

Для кожного запиту з номером 1 у окремому рядку виведіт рядок "wins", якщо Вітя виграв, рядок "loser", якщо він програв і "draw", якщо була нічия.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
5
2 4 6 10 8
6
1 1 5
1 2 3
2 5 15
2 3 10
1 3 5
1 1 1
Вихідні дані #1
wins
wins
wins
draw
Автор Олександр Бурков
Джерело Дистанційна Літня Комп`ютерна Школа - літо 2013 року