Теперь у Вити есть программа, которая помогает ему быстро находить НОД многих чисел. Поэтому стражи решили изменить правила: теперь Витя должен найти наибольший общий делитель (НОД) чисел на промежутке [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", если была ничья.