위젯 공장
시간 제한2초메모리 제한512 MB
각 작업자가 만든 위젯 종류와 요일 단위의 시작일과 해고일이 주어질 때, 각 위젯 종류를 만드는 데 걸리는 일수를 구한다.
문제
위젯 공장은 여러 종류의 위젯을 생산한다. 각 위젯은 숙련된 위젯공이 정성껏 만든다. 위젯을 만드는 데 걸리는 시간은 종류에 따라 다르다. 단순한 위젯은 3일이면 충분하지만, 가장 복잡한 위젯은 9일까지 걸린다.
공장은 지금 완전히 혼란스러운 상태다. 최근 공장이 새 주인에게 팔렸고, 새 책임자가 직원을 거의 모두 해고했다. 새 직원들은 위젯을 만드는 일에 대해 거의 아무것도 모르며, 각 종류의 위젯을 만드는 데 며칠이 걸리는지 기억하는 사람도 없는 것 같다. 고객이 위젯을 주문했는데 공장이 필요한 물건을 생산하는 데 며칠이 걸리는지 고객에게 말하지 못한다면 매우 난처할 것이다. 다행히 위젯공마다 공장에서 일을 시작한 날짜, 해고된 날짜, 어떤 종류의 위젯을 만들었는지 적은 기록이 남아 있다. 문제는 기록에 출근일과 퇴사일의 정확한 날짜가 없고 요일만 적혀 있다는 점이다. 그래도 이런 정보가 도움이 되는 경우가 있다. 예를 들어 어떤 위젯공이 화요일에 일을 시작해 41번 위젯을 만들었고 금요일에 해고되었다면, 41번 위젯을 만드는 데 4일이 걸린다는 것을 알 수 있다. 여러분의 과제는 이 기록들로부터 각 종류의 위젯을 만드는 데 필요한 일수를 (가능하다면) 알아내는 것이다.
입력
입력은 여러 개의 테스트 케이스 묶음으로 이루어진다. 각 테스트 케이스는 두 정수 n (1 ≤ n ≤ 100)과 m (1 ≤ m ≤ 100)이 있는 줄로 시작한다. n은 위젯 종류의 수, m은 기록의 수다. 이 줄 다음에 m개의 기록이 주어진다. 각 기록은 두 줄로 표현된다. 첫째 줄에는 이 위젯공이 만든 위젯의 총 개수 k (1 ≤ k ≤ 400)와 그가 일을 시작한 요일, 해고된 요일이 주어진다. 요일은 ‘MON’, ‘TUE’, ‘WED’, ‘THU’, ‘FRI’, ‘SAT’, ‘SUN’ 문자열로 주어진다. 둘째 줄에는 k개의 정수가 공백으로 구분되어 주어진다. 이 수는 1과 n 사이이며, 위젯공이 만든 위젯의 종류를 나타낸다. 예를 들어 다음 두 줄은 위젯공이 수요일에 일을 시작해 13번 위젯, 18번 위젯, 1번 위젯, 다시 13번 위젯을 만들었고 일요일에 해고되었음을 뜻한다.
4 WED SUN
13 18 1 13
위젯공은 일주일 내내 일하며, 공장에서의 첫날과 마지막 날 사이의 모든 날에 일했다. (주말과 휴일이 좋다면 위젯공이 되지 않는 게 좋다!)
입력은 n = m = 0인 테스트 케이스로 끝난다.
출력
각 테스트 케이스마다 한 줄에 n개의 정수를 공백으로 구분해 출력한다. 이는 각 종류의 위젯을 만드는 데 필요한 일수다. 첫 번째 수 앞과 마지막 수 뒤에는 공백이 없어야 하며, 두 수 사이에는 정확히 공백이 하나 있어야 한다. 가능한 해가 여러 개라면 ‘Multiple solutions.’를 (따옴표 없이) 출력한다. 입력과 일치하는 해가 없다고 확신한다면 ‘Inconsistent data.’를 (따옴표 없이) 출력한다.