구역 심사

"우리 마을에 사무용 건물을 짓고 싶으시다고요? 정말 반갑습니다!" 시장은 환하게 웃으며 나를 다시 시청 안으로 안내했다. "건축 허가 신청서가 우리 마을의 모든 구역 규정을 충족하는지만 확인하면 됩니다. 바로 확인해 드릴 수 있어요."

그는 "구역 심사"라고 적힌 문으로 나를 데려갔다. 줄지어 늘어선 책상들로 가득 찬 거대한 방을 보고 나는 깜짝 놀랐다. 각 책상에는 장부 한 권, 서류함 하나, 그리고 넉넉한 연필과 지우개를 갖춘 심사원이 앉아 있었다.

시장은 내 신청서를 받아 들더니, 번호가 매겨진 칸들이 여러 줄 그려진 종이 한 장을 꺼냈다. 그는 그 종이를 가장 가까운 책상의 서류함에 넣으며 말했다. "이 종이를 심사원들에게 돌립니다. 만약 모든 칸이 체크된 채로 이 책상으로 돌아오면 신청이 승인됩니다." 그 책상의 심사원은 종이를 집어 몇 개의 칸에 체크 표시를 하고, 장부에 몇 줄을 적은 뒤, 근처 복사기로 사본을 만들어 다른 여러 책상에 나눠 주었다. 그 책상들의 심사원들도 각자 체크 표시를 더하거나 일부를 지우고, 장부에 기록하고, 사본을 만들어 다시 돌렸다. 곧 사본들이 방 안을 이리저리 날아다니는 것 같았다.

"하지만 아무도 제 신청서를 제대로 보지 않았잖아요!" 내가 말했다.

"아니요," 시장이 말했다. "심사원들은 각자 우리 구역 규정의 몇몇 부분을 꼼꼼히 공부했습니다. 어떤 규칙은 어떤 신청서든 자동으로 만족한다고 확신하는 심사원이 있고, 또 어떤 규칙은 어떤 신청서도 결코 만족할 수 없다고 믿는 심사원도 있죠. 그래서 각 심사원은 단지 몇몇 칸에 체크를 하고 다른 몇몇 칸의 체크를 지울 뿐입니다."

"우리는," 그가 덧붙였다. "우리 구역 심사가 얼마나 단호한지 자랑스럽게 생각합니다. 근처 법대에서 가장 고압적이고 따지기 좋아하는 하급생만 골라 뽑거든요."

"그럼 표시를 마친 사본을 어디로 보낼지는 어떻게 정하나요?" 내가 물었다.

"글쎄요," 시장이 말했다. "제 생각엔 대개 가장 싫어하는 동료에게 넘겨서 경쟁자의 일감을 늘리려는 것 같습니다." 바로 그때 종이 한 장이 가장 가까운 책상에 놓였다. "얼마나 진행됐는지 봅시다." 그가 종이를 집어 들며 말했다. "아니, 아직 네 칸이 비어 있군요. 좀 더 나아지는지 기다려 봐야겠습니다."

"이러다 영원히 끝나지 않을 것 같은데요." 내가 한숨을 쉬었다.

"아닙니다." 시장이 말했다. "각 심사원은 지금까지 넘긴 신청서의 모든 버전을 장부에 기록합니다. 종이가 도착하면 먼저 이전에 넘긴 모든 버전에 있던 체크 표시를 전부 더한 다음, 자신의 체크와 지우기를 합니다. 그 결과가 이미 넘긴 버전과 똑같다면 두 번 다시 넘기지 않습니다."

따라서 이 과정은 반드시 끝난다. 규칙을 정확히 정리하면 다음과 같다.

• 신청서에는 $0$번부터 번호가 매겨진 고정된 개수의 칸이 있다. 신청서의 한 버전은 현재 체크된 칸들의 집합이다.
• 심사원은 $0$번부터 번호가 매겨진다. 각 심사원에게는 항상 체크하는 칸들의 집합, 항상 지우는 칸들의 집합, 그리고 사본을 전달할 심사원들의 목록이 정해져 있다.
• 신청서는 아무 칸도 체크되지 않은 빈 양식으로 시작하여 $0$번 심사원의 서류함에 놓인다.
• 심사원이 신청서를 받으면 새 버전을 다음과 같이 만든다. (1) 받은 신청서와 자신이 이전에 넘긴 모든 버전을 합친 뒤, (2) 자신이 항상 체크하는 칸을 모두 체크하고, (3) 자신이 항상 지우는 칸을 모두 지운다. 이 새 버전이 이미 넘긴 어떤 버전과 똑같다면 버린다. 그렇지 않으면 장부에 기록하고 목록의 각 심사원에게 사본을 전달한다.

$0$번 심사원의 책상을 떠나는 마지막 버전에 체크된 칸들을 출력하라.

입력은 하나 이상의 문제 세트로 이루어진다.

각 세트의 첫 줄에는 두 개의 양의 정수, 즉 양식의 칸 개수와 사무실의 심사원 수가 주어진다. 두 값이 모두 $0$인 줄은 입력의 끝을 나타내며 문제 세트가 아니다.

그다음 각 세트에는 $0$번 심사원부터 시작하여 심사원마다 세 줄이 주어진다(칸과 심사원 모두 $0$번부터 번호가 매겨진다). 각 줄에는 공백으로 구분된 $0$개 이상의 정수가 들어 있다.

• 이 심사원이 항상 체크하는 칸들의 번호,
• 이 심사원이 항상 지우는 칸들의 번호,
• 이 심사원이 수정한 사본을 전달하는 심사원들의 번호.

각 문제 세트에 대해, $0$번 심사원의 책상을 떠나는 마지막 사본에 체크된 칸들의 번호를 오름차순으로 한 칸 공백으로 구분하여 한 줄에 출력한다. 체크된 칸이 하나도 없으면 빈 줄을 출력한다.