특수 서비스 예약 시스템

특수 서비스를 다루는 회사의 예약 시스템을 만드는 일을 맡았다. 이 회사는 온갖 종류의 서비스를 진행하지만, 질문은 하지 말라는 말을 들었다. 앞서 이 시스템을 만들려던 개발자가 몇 명 있었으나 지금은 아무도 행방을 알 수 없어서 도움을 구할 수도 없다.

시스템은 예약과 취소 요청을 하나씩 받고, 받는 즉시 수락인지 거절인지 정해야 한다. 모든 예약은 하루 전체를 차지하며, 여기서 만드는 부분은 하루만 관리한다.

회사에는 직원이 여럿 있고, 직원마다 자격이 하나 이상 있다. 각 예약에는 숫자 식별자가 붙고, 특정 자격을 갖춘 인원을 몇 명 요구한다. 한 사람은 하루 동안 예약 하나의 요구 하나만 담당한다. 이사가 든 예를 그대로 옮기면, 마리오는 배관공이면서 암살자일 수 있지만 하루에는 예약 하나에서 한 가지 일만 한다.

예약은 다음 두 조건을 모두 만족할 때만 수락한다.

• 그 식별자를 쓰는 활성 예약이 없다.
• 주어진 직원으로 현재 활성 예약 전부와 새 예약의 요구를 모두 충족하는 배정이 존재한다.

취소는 그 식별자를 쓰는 활성 예약이 있을 때만 수락한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 직원 수 $N$과 그 테스트 케이스에 들어 있는 예약과 취소의 수 $B$가 주어진다.

이어지는 $N$개의 줄에 직원이 한 명씩 주어진다. 각 줄은 수 $c$로 시작하고, 공백으로 구분된 문자열 $c$개가 이어진다. 이 문자열이 그 직원의 자격 이름이다.

그다음 $B$개의 줄에는 예약 또는 취소가 주어진다. 예약은 단어 book으로 시작하고, 그 예약의 숫자 식별자 $I$, 수 $d$, 공백으로 구분된 문자열 $d$개가 차례로 이어진다. 이 문자열이 그 예약의 자격 요구 전부다. 취소는 단어 cancel과 취소할 예약의 식별자 $I$로 이루어진다.

• $0 < T \le 50$
• $1 \le N \le 200$
• $1 \le B \le 1000$
• $1 \le c \le 16$
• $0 \le d \le 16$
• $0 \le I \le 1000$
• 자격 이름의 길이는 10자 이하다. 전체 직원에게 나타나는 자격의 종류는 100가지를 넘지 않는다.
• 활성 예약은 수락된 뒤 아직 취소되지 않은 예약이다.
• 인원을 한 명도 잡지 않는 예약도 들어올 수 있다. 이런 예약은 회사 대표가 직접 처리하니, 계속 질문하지 말자.
• 입력과 출력의 양이 많다. 빠른 입출력 방법을 쓰는 편이 좋다.

예약과 취소마다 한 줄씩 출력한다. 요청을 수락하면 Accepted를, 거절하면 Rejected를 출력한다.