Kỹ Thuật Đảo Ngược

Elsie có một chương trình nhận vào một mảng gồm $N$ biến nhị phân và thực thi một loạt các câu lệnh if/else if/else, mỗi câu lệnh kiểm tra tối đa một biến và trả về 0 hoặc 1. Bessie biết $M$ cặp input-output đúng nhưng nghi ngờ Elsie có thể đã nói dối.

Hãy xác định liệu có tồn tại một chương trình hợp lệ nhất quán với tất cả các cặp input-output được cung cấp hay không.

Dữ liệu vào

• Dòng đầu tiên chứa $T$ ($1\le T\le 10$), số lượng bộ test.
• Với mỗi bộ test (các bộ test cách nhau bởi dòng trống):
  • Dòng 1: hai số nguyên $N$ và $M$ ($1\le N,M\le 100$).
  • $M$ dòng tiếp theo: mỗi dòng chứa một xâu nhị phân độ dài $N$ (input) và một chữ số nhị phân (output).

Dữ liệu ra

Với mỗi bộ test, in "OK" nếu tồn tại chương trình hợp lệ, ngược lại in "LIE".

Ràng buộc

• $1\le N\le 100$
• $1\le M\le 100$
• $1\le T\le 10$

Ví dụ