#P4131. 并行博弈

    ID: 3257 传统题 1000ms 512MiB 尝试: 87 已通过: 45 难度: 4 上传者: 标签>难度分类普及+/提高-构造与建模奇偶性分析单调量证明终止CF1600

并行博弈

并行博弈

题目描述

lyp 和 ld 同时玩若干个翻转棋游戏。每个棋盘有 nn 行 mm 列,每格放一枚黑色或白色棋子。左上角为 (1,1)(1,1),行号向下增加,列号向右增加。

lyp 先手,双方轮流操作。每次选一个棋盘和其中一枚黑棋 (x,y)(x,y),将该棋盘上所有满足 1≤x′≤x1\le x'\le x、1≤y′≤y1\le y'\le y 的棋子翻色,包括所选黑棋。轮到一方时,若所有棋盘上都没有可选的黑棋,这一方输。判断双方都采用最优策略时谁会获胜。

输入格式

第一行一个整数 TT(1≤T≤201\le T\le20),表示数据组数。

每组数据先给出一个正整数 KK,表示棋盘数。接下来依次给出 KK 个棋盘。每个棋盘先有一行两个正整数 n,mn,m,再有 nn 行,每行 mm 个整数。0 表示白棋,1 表示黑棋。每个棋盘的尺寸满足 nmK≤105n m K\le10^5。

输出格式

对每组数据输出一行。lyp 必胜时输出 lyp win,否则输出 ld win。

样例 #1

样例输入 #1

1
1
2 2
1 1
1 0

样例输出 #1

lyp win