프로그램 역설계

Elsie는 길이가 $N$인 배열을 입력으로 받는 프로그램을 가지고 있습니다. 이 배열에는 0과 1로 이루어진 요소 $b[0], \dots, 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;

Elsie는 Bessie에게 프로그램의 동작 방식에 대한 여러 예제 출력 $M$개를 알려줍니다. 이제 Bessie의 목표는 주어진 출력을 토대로 Elsie의 프로그램을 유추하는 것입니다. 그러나, Elsie가 항상 정직하게 말한 것은 아닐 수 있습니다. 따라서 Bessie가 얻은 정보로 Elsie의 프로그램을 완벽하게 유추할 수 없는 경우도 있습니다.

입력은 테스트 케이스 $T$의 수로 시작하며, 각 테스트 케이스는 배열의 길이 $N$, 제공된 출력 예제의 수 $M$ 및 해당하는 $M$개의 입력-출력 쌍으로 구성됩니다.

Elsie의 설명이 유효한 프로그램을 유추할 수 있는 경우 'OK'를, 그렇지 않은 경우 'LIE'를 출력합니다.