题目描述

鸭哥和薯条哥在玩一个游戏，游戏中有一个长度为$n$的数组$a$,他们会玩$q$轮游戏，每轮游戏都是独立的。游戏规则如下，双方都会执行最优策略：

第一步，游戏给出一个区间$[l,r]$。

第二步，薯条哥在$[l,r]$区间中选择一个数。

第三步，鸭哥将区间扩展成$[L,R] ([L,R]$必须包含$[l,r])$，然后在$[L,R]$区间中选择一个数，但不能跟薯条哥选同一个数。

第四步，鸭哥和薯条哥选择的数字较大的一方获胜，若相同则平局。

鸭哥想知道他每一轮的输赢状态，并且他想知道要达到输赢状态所需的$[L,R]$区间长度最小是多少。

输入描述

第一行输入两个正整数$n,q(2\le n,q\le 2×10^5)$,表示数组长度和询问次数。

第二行输入$n$个正整数$a(1\le a_i\le 10^9)$,表示数组。

接下来$q$行，每行输入两个整数$(1\le l\le r\le n)$，表示询问

输出描述

对于每个询问先输出一行，若鸭哥可以获胜则输出“$win$”,若平局则输出“$draw$”,多失败则输出“$lose$”。

第二行输出达到最终状态所需的区间长度的最小值。

样例

输入

6 2
1 1 4 5 1 4
1 3
4 4

输出

win
4
lose
2

样例解释

第$1$个询问，薯条哥会选择数字$4$，鸭哥将区间扩展成[$1,4$]，选择数字$5$，鸭哥获胜，扩展后的区间长度为$4$。

第$2$个询问，薯条哥会选择数字$5$，鸭哥将区间扩展成[$3,4$]，选择数字$4$，薯条哥获胜，扩展后的区间长度为$2$。