In the country of Unlearned Lessons 2#4482
Sign in

In the country of Unlearned Lessons 2

3 seconds
512 megabytes
Very easy

Now, Vitya has a program that helps him quickly find the greatest common divisor (GCD) of many numbers. However, the guards decided to make the task more challenging: Vitya must calculate the GCD of the numbers on a segment [l; r], while the guards calculate the least common multiple (LCM) of the same numbers. The winner is the one whose result is smaller.

Input

The first line contains the number of elements in the array n~(1 \le n \le 10^6).

The second line contains numbers — the elements of the array a_i~(1 \le a_i \le 10^9).

The third line specifies the number of queries m~(1 \le m \le 10^5).

Each of the following lines contains three integers q, l, r~(1 \le l \le r \le n):

  • If q = 1, determine the winner for the segment [l; r];

  • If q = 2, replace the element at position with the number .

Output

For each query with q = 1, print the result in a separate line:

  • "wins" if Vitya wins;

  • "loser" if Vitya loses;

  • "draw" if it's a tie.

Examples

Example 1

Loading
Loading