In a country of Unlearned Lessons 2

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.

Input

The first line contains the number of elements $n(1\le n\le 10^6)$ in array. The second line contains $n$ numbers $a_i(1\le a_i\le 10^9)$ of array. The third line contains the number of queries $m(1\le m\le 10^5)$. Each of the next $m$ lines contain three numbers $q,l,r(1\le l\le r\le 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$

Output

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.

Examples