B. 动物之王
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
善良的鳄鱼

善良的鳄鱼与邪恶的小老鼠发现了一个长度为 $$$n$$$ 的十进制块数组。为了证明谁才是动物之王，它们决定玩一个比大小的小游戏。最初它们各有一个数字 $$$0$$$ ，然后双方将分别进行 $$$q_1$$$ 和 $$$q_2$$$ 次操作。

每次操作会从这个数组中截取一段连续的块，将这一段按固定 $$$10^9$$$ 进制拼接成一个整数，再与当前拥有的数字进行加、减或乘。最后比较两个数的大小，谁大谁就赢。

显然这种简单的小游戏还是太无聊了。因此鳄鱼提议，为了提升游戏的难度，同时为了避免出现打假赛的情况，每只动物最后计算出的数都必须在 $$$[0,10^{20000}]$$$ 内。这里的区间是闭区间，也就是说 $$$0$$$ 和 $$$10^{20000}$$$ 本身都是合法的。如果有动物最后的答案不在这个范围内，就要遭到严厉的惩罚。

现在鳄鱼和小老鼠已经完成了各自的操作。善良的鳄鱼迫切地想知道自己能不能成为动物之王，于是它便请教你来帮它计算游戏的结果。

具体来说，给定一个长度为 $$$n$$$ 的数组 $$$A$$$（下标从 $$$1$$$ 开始）。每个 $$$A_i$$$ 满足 $$$0 \le A_i \lt 10^9$$$ 。对于区间 $$$[l,r]$$$ ，定义

$$$$$$ value(l,r)=A_l\cdot(10^9)^{r-l}+A_{l+1}\cdot(10^9)^{r-l-1}+\cdots+A_r. $$$$$$

也就是说，每个块都视为固定 $$$9$$$ 位十进制块来拼接。允许块本身有前导零。例如数组片段 $$$[1,23]$$$ 表示整数 $$$1000000023$$$ ，而不是 $$$123$$$ 。

特别地，$$$10^{20000}$$$ 有 $$$20001$$$ 位十进制数字，是合法上界而不是非法值。由于一个块表示 $$$9$$$ 位十进制数字，且 $$$10^{20000}=100\cdot(10^9)^{2222}$$$ ，当一段长度为 $$$2223$$$ 、形如 $$$[100,0,0,\ldots,0]$$$ 的块被拼接时，它表示的正是 $$$10^{20000}$$$ 。

游戏开始时，鳄鱼拥有的数值 $$$x=0$$$ ，小老鼠拥有的数值 $$$y=0$$$ 。

鳄鱼将按顺序执行 $$$q_1$$$ 次操作，每次操作的对象是它当前的数值 $$$x$$$ 。

小老鼠将按顺序执行 $$$q_2$$$ 次操作，每次操作的对象是它当前的数值 $$$y$$$ 。

如果某动物的操作次数为 $$$0$$$ ，则其数值保持初始值 $$$0$$$ 。

每次操作包含三个参数：$$$op,l,r$$$ ，含义如下：

  1. 首先取数组 $$$A$$$ 中从第 $$$l$$$ 个块到第 $$$r$$$ 个块（包含两端）的连续片段，将其按上述方式视为整数 $$$a=value(l,r)$$$ 。
  2. 设当前动物的数值为 $$$z$$$（即鳄鱼操作时为 $$$x$$$ ，小老鼠操作时为 $$$y$$$），根据 $$$op$$$ 的值更新 $$$z$$$ ：
    • 若 $$$op=0$$$ ，则 $$$z=z+a$$$ ；
    • 若 $$$op=1$$$ ，则 $$$z=z-a$$$ ；
    • 若 $$$op=2$$$ ，则 $$$z=z\cdot a$$$ 。

所有操作执行完毕后，分别检查两只动物的数值是否处于合法区间 $$$[0,10^{20000}]$$$ ：

  • 若 $$$x \lt 0$$$ 或 $$$x \gt 10^{20000}$$$ ，则鳄鱼违规；否则鳄鱼合法。
  • 若 $$$y \lt 0$$$ 或 $$$y \gt 10^{20000}$$$ ，则小老鼠违规；否则小老鼠合法。

请注意，操作过程中 $$$x$$$ 和 $$$y$$$ 可以暂时小于 $$$0$$$ 或者大于 $$$10^{20000}$$$ 。你只需要判定所有操作结束后的 $$$x$$$ 和 $$$y$$$ 是否在 $$$[0,10^{20000}]$$$ 内。

换言之，只看最终结果是否满足 $$$0 \le x,y \le 10^{20000}$$$ 。最终结果恰好等于 $$$10^{20000}$$$ 时不违规；最终结果大于 $$$10^{20000}$$$ ，例如 $$$10^{20000}+1$$$ ，才违规。

Input

第一行包含一个整数 $$$T$$$（$$$1 \le T \le 10$$$），表示测试数据的组数。

对于每组测试数据：

第一行包含一个整数 $$$n$$$ （$$$1 \le n \le 2 \cdot 10^4$$$），表示数组长度。

第二行包含 $$$n$$$ 个整数 $$$A_1,A_2,\ldots,A_n$$$（$$$0 \le A_i \lt 10^9$$$），表示十进制块数组。

第三行包含两个整数 $$$q_1,q_2$$$（$$$0 \le q_1 \le 2 \cdot 10^4，0 \le q_2 \le 2 \cdot 10^4$$$） ，分别表示鳄鱼和小老鼠的操作次数。

接下来 $$$q_1$$$ 行，每行包含三个整数 $$$op_i,l_i,r_i$$$（$$$0 \le op_i \le 2$$$ ，$$$1 \le l_i \le r_i \le n$$$），表示鳄鱼的第 $$$i$$$ 次操作。

接下来 $$$q_2$$$ 行，每行包含三个整数 $$$op_i,l_i,r_i$$$（$$$0 \le op_i \le 2$$$ ，$$$1 \le l_i \le r_i \le n$$$），表示小老鼠的第 $$$i$$$ 次操作。

数据保证对于每个测试文件，所有测试数据满足：

$$$$$$ \sum n \le 2 \cdot 10^4,\quad \sum q_1 \le 2 \cdot 10^4,\quad \sum q_2 \le 2 \cdot 10^4. $$$$$$

Output

对于每组测试数据，按以下规则输出结果。注意输出时不要带引号。

  • 若双方均违规，输出 'both cheat'。
  • 若仅鳄鱼违规（小老鼠合法），输出 'crocodile cheats'。
  • 若仅小老鼠违规（鳄鱼合法），输出 'little mouse cheats'。
  • 若双方均合法：
    • 若 $$$x \gt y$$$ ，输出 'crocodile win'；
    • 若 $$$x \lt y$$$ ，输出 'little mouse win'；
    • 若 $$$x=y$$$ ，输出 'draw'。
Example
Input
3
2
0 123
1 1
0 2 2
0 1 2
1
10
1 0
1 1 1
3
1 234567890 0
2 1
0 1 2
2 2 3
0 2 3
Output
draw
crocodile cheats
crocodile win
Note

样例解释：

  • 第一组：鳄鱼取第 $$$2$$$ 个块，得到 $$$123$$$ 。小老鼠取区间 $$$[1,2]$$$ ，因为块宽固定为 $$$9$$$ 位，得到 $$$0\cdot10^9+123=123$$$ 。双方合法且相等，输出 'draw'。
  • 第二组：鳄鱼执行 $$$0-10=-10$$$ ，最终违规；小老鼠没有操作，保持 $$$0$$$ ，合法。因此输出 'crocodile cheats'。
  • 第三组：鳄鱼先取区间 $$$[1,2]$$$ ，得到 $$$1\cdot10^9+234567890=1234567890$$$ ，再乘以区间 $$$[2,3]$$$ 的值 $$$234567890\cdot10^9$$$ ；小老鼠只取区间 $$$[2,3]$$$ 。双方最终均合法，鳄鱼数值更大，输出 'crocodile win'。