Victor has a program that helps him to find quickly GCD of many numbers. Therefore, the guard decided to change the rules: now Victor must find the greatest common divisor (GCD) of the numbers on the interval [l;r], and the guards must find the least common multiple (LCM). Who gets the less number that wins.
The first line contains the number of elements n(1≤n≤106) in array. The second line contains n numbers ai(1≤ai≤109) of array. The third line contains the number of queries m(1≤m≤105). Each of the next m lines contain three numbers q,l,r(1≤l≤r≤n). If q=1 you need to find the winner for a segment [l;r], if q=2 you need to replace the element at position l to the number r
For each query with number 1 print in a separate line "wins", if Victor wins, print "loser" if Victor lose and "draw" in a case of a draw.