#1040. EXIT - Tìm cửa thoát

Một mê cung có dạng một cây nhị phân đầy đủ có độ sâu . Các nút của cây được đánh số theo qui tắc:

• Gốc của cây được đánh số
• Với một nút trong thì con trái của nó được đánh số là và con phải của nó được đánh số là (độ sâu của một nút được định nghĩa bằng nếu là nút gốc và bằng độ sâu của nút cha với các nút khác. Với cách đánh số trên, các nút lá luôn ở độ sâu và có số hiệu từ đến ) Trong mê cung có duy nhất một nút lá có cửa thoát. Nhiệm vụ của bạn là phải tìm cửa thoát dựa theo thông tin trả về của lần khảo sát: Thông tin mỗi lần khảo sát có dạng:
  • . Cửa thoát nằm trên lá với tổ tiên ở độ sâu có số hiệu từ đến hoặc
  • . Cửa thoát không nằm trên các lá với tổ tiên ở độ sâu có số hiệu từ đến Hỏi rằng với các thông tin trên có xác định được số hiệu nút lá có cửa thoát hay không?

Dữ liệu vào:

• Dòng đầu tiên ghi hai số nguyên dương
• dòng tiếp theo, mỗi dòng ghi năm số thể hiện thông tin của một khảo sát với nếu thuộc dạng và nếu thuộc dạng

Dữ liệu ra:

• Nếu dữ liệu khảo sát mâu thuẫn ghi "No" (không nháy kép)
• Nêu có nhiều lá thỏa mãn thì ghi "Multi" (không có nháy kép)
• Nếu có duy nhất một lá thỏa mãn ghi số hiệu của lá này

Ví dụ:

Dữ liệu vào:

4 3
4 10 14 1
3 6 6 0
2 3 3 1

Dữ liệu ra:

14