문제
엘씨는 N개의 0이나 1로 이루어진 변수 b[0],…,b[N−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을 반환한다.
엘씨는 배씨에게 M(1≤M≤100)개의 다른 입력에 대한 출력을 알려 주었고, 배씨는 이를 토대로 엘씨의 프로그램을 리버스 엔지니어링하려고 한다.
유감스럽게도 엘씨는 거짓말을 했을 수도 있다. 위 형식의 어떤 프로그램도 엘씨가 말한 것과 일치하지 않는 경우가 있을 수 있다는 말이다.
각 T(1≤T≤10) 테스트 케이스에 대해 엘씨가 거짓말을 했는지 판별하자.
입력
첫 번째 줄에는 테스트 케이스의 수 T가 입력된다 (1≤T≤10).
두 번째 줄부터 각 테스트 케이스의 첫 번째 줄에는 정수 N과 M이 입력되고 (1≤N≤100, 1≤M≤100), 이어 M줄에 N개의 0 또는 1로 이루어진 입력값 b[0]…b[N−1]이 입력되고, 이어서 추가적인 0 또는 1로 이루어진 출력값이 입력된다.
각 테스트 케이스의 사이엔 빈 줄이 주어진다.
출력
각 테스트 케이스에 대하여 각 줄에 엘씨가 거짓말을 안했으면 "OK", 거짓말을 했으면 "LIE"를 출력하시오.
예제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
힌트
출처
USACO 2022 December Bronze