Тепер у Віті є програма, яка допомогає йому швидко знаходити НСД багатьох чисел. Тому стражі вирішили змінити правила: тепер Вітя повинен знайти найбільший спільний дільник (НСД) чисел на проміжку [l;r], а стражі — найменше спільне кратне (НСК), у кого получиться число меншим, той і виграє.
Перший рядок містить кількість елементів у масиві n(1≤n≤106). У другому рядку знаходиться n чисел — елементи ai(1≤ai≤109) масива. У третьому рядку знаходиться кількість запитів m(1≤m≤105). Далі у m рядках знаходиться по три числа q,l,r(1≤l≤r≤n). Якщо q=1, потрібно визначити переможця для проміжка [l;r], якщо q=2, то потрібно замінити елемент у позиції l на число r.
Для кожного запиту з номером 1 у окремому рядку виведіт рядок "wins", якщо Вітя виграв, рядок "loser", якщо він програв і "draw", якщо була нічия.