本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

Elsie 有一个程序，它的输入是一个包含 $N$（$1\le N\le 100$）个变量的数组 $b[0],\dots,b[N-1]$，每个变量的值为 0 或 1，并返回对输入应用一系列 if / else if / else 语句后的结果。 每条语句最多检查一个输入变量的值，并返回 0 或 1。 这种程序的一个示例可能是： if (b[1] == 1) return 1; else if (b[0] == 0) return 0; else return 1; 例如，如果上述程序的输入是 "10"（也就是 $b[0] = 1$ 且 $b[1] = 0$），那么输出应为 1。 Elsie 告诉了 Bessie 对于 $M$（$1\le M\le 100$）个不同输入的正确输出。Bessie 现在试图对 Elsie 的程序进行逆向工程。不幸的是，Elsie 可能撒了谎；也可能不存在任何符合上述形式的程序与 Elsie 所说的内容一致。 对于 $T$（$1\le T\le 10$）组测试数据中的每一组，判断 Elsie 是否一定在撒谎。

输入格式

第一行包含 $T$，表示测试用例数量。 每个测试用例以两个整数 $N$ 和 $M$ 开始，接下来有 $M$ 行，每行包含一个由 $N$ 个 0 和 1 组成的字符串表示一个输入（即 $b[0] \ldots b[N-1]$ 的取值），以及一个额外字符（0 或 1）表示输出。 相邻测试用例之间用空行分隔。

输出格式

对于每个测试用例，在单独一行输出 "OK" 或 "LIE"。

4

1 3
0 0
0 0
1 1

2 4
00 0
01 1
10 1
11 1

1 2
0 1
0 0

2 4
00 0
01 1
10 1
11 0

OK
OK
LIE
LIE

提示

下面是第一组测试用例的一个合法程序： if (b[0] == 0) return 0; else return 1; 第一组测试用例的另一个合法程序： if (b[0] == 1) return 1; else return 0; 第二组测试用例的一个合法程序： if (b[1] == 1) return 1; else if (b[0] == 0) return 0; else return 1; 显然，第三组测试用例不存在合法程序，因为 Elsie 的程序对相同输入必须始终产生相同输出。 可以证明，最后一组测试用例也不存在合法程序。 SCORING: 输入 2 和 3 满足 $N = 2$。 输入 4 和 5 满足 $M = 2$。 输入 6 到 12 没有额外限制。 题目鸣谢：Benjamin Qi

来源

USACO|2022|Bronze