问题 E: 逆向工程 Reverse Engineering

Elsie 有一个程序，接受一个 N（1≤N≤100）个变量的数组 b[0],…,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≤M≤100）个不同输入的正确输出。Bessie 现在正试图对 Elsie 的程序进行逆向工程。不幸的是，Elsie 可能说了谎；可能不存在上述形式的程序行为与 Elsie 所说的均一致。

对于 T（1≤T≤10）个子测试用例中的每一个，判断 Elsie 是否一定在说谎。

输入的第一行包含 T，为子测试用例的数量。

每一个子测试用例的第一行包含两个整数 N 和 M，以下 M 行，每行包含一个由 N 个 0 或 1 组成的字符串，表示一个输入（即 b[0]…b[N−1] 的值），以及另一个字符（0 或 1）表示输出。相邻的子测试用例之间用空行分隔。

输入样例：

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 的程序一定始终对相同的输入产生相同的输出。

可以证明对于最后一个子测试用例不存在对应的合法的程序。

输入：
10

2 2
00 1
11 1

2 3
01 1
10 0
11 0

2 4
11 0
00 1
10 1
01 1

2 4
00 1
01 0
11 0
10 0

2 4
10 0
11 0
01 1
00 1

2 4
11 1
10 0
01 1
00 0

2 4
01 1
00 0
11 1
10 0

2 4
11 1
01 0
10 1
00 0

2 4
11 1
00 0
01 1
10 0

2 4
01 1
11 0
10 1
00 0
输出：
OK
OK
OK
OK
OK
OK
OK
OK
OK
LIE