Migrated from Lutece 2821 期望游戏

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Alice 和 Bob 正在玩游戏。

这个游戏基于一个长度为 $n$ 的由小写字母组成的字符串 $s$。在每轮游戏开始之前，Alice 会选择一个回文子串 $s_{a..b}$，Bob 会选择一个回文子串 $s_{c..d}$。

每轮游戏开始时会有一个空串 $t$，然后不断的往 $t$ 后面等概率添加一个小写字母（即每个字母被选的概率为 $\frac{1}{26}$），令 $E(s)$ 为 $s$ 第一次成为 $t$ 的子串时 $t$ 的期望长度。

Alice 胜利当且仅当 $E(s_{a..b}) < E(s_{c..d})$； Bob 胜利当且仅当 $E(s_{c..d}) < E(s_{a..b})$； 否则视为平局。

给定字符串 $s$，有 $q$ 次询问，每次给出 $a,b,c,d$ ，请输出游戏结果。

Input

第一行一个正整数 $T$ 表示数据组数。

对于每组数据，第一行一个正整数 $n$ 表示串长，第二行为字符串 $s$。

第三行为询问次数 $q$，接下来 $q$ 行每行四个整数 $a,b,c,d$ 表示 Alice 和 Bob 选择的子串。

Output

对于每组询问，若 Alice 胜利输出 Win； Bob 胜利输出 Lose；否则输出 Draw。

Samples

1
7
abbabba
5
1 1 2 2
1 4 4 7
2 3 1 7
1 4 5 6
2 3 3 5

Draw
Draw
Win
Lose
Win

Constraints

$T\le 25,n\le 10^5,q\le 10^5$.

Resources

2022 UESTC ICPC Training for String and Search Algorithm