작업 할당기

공용 컴퓨팅을 위한 인프라 컨소시엄(ICPC)은 전 세계 자원봉사자들이 운영하는 컴퓨터 네트워크로, 서로 컴퓨팅 자원을 공유한다. 기여자는 자신의 컴퓨터를 네트워크에 연결하거나 분리할 수 있고, 네트워크에 있는 컴퓨터에서 컴퓨팅 작업을 실행할 수도 있다. ICPC가 있으면 인프라 비용이 너무 커서 불가능했을 중요한 프로젝트(예를 들어 프로그래밍 대회의 온라인 저지 운영)도 실행할 수 있게 된다.

말처럼 좋아 보이지만, 지금 ICPC는 꿈에 불과하다. 이를 실현하려면 빠진 소프트웨어가 하나 있다. 바로 작업 할당기다. 여기서 여러분의 역할이 나온다. 커뮤니티는 여러분이 이 중요하지만(물론 자발적인) 기여를 해 주기를 기대한다.

네트워크는 매우 동적이다. 컴퓨터는 항상 연결되고 분리된다. 작업 할당기는 현재 연결된 컴퓨터와 그 컴퓨터가 공유하는 자원을 추적해야 한다. 자원에는 CPU 코어, GPU, SSD 디스크 등 여러 종류가 있다. 한 컴퓨터는 하나 이상의 자원을 공유할 수 있고, 같은 종류를 여러 개 공유할 수도 있다. 또한 언제든지 사용자가 컴퓨팅 작업을 실행할 컴퓨터를 요청할 수 있다. 이를 위해 사용자는 작업을 실행하는 데 필요한 자원 목록을 지정하고, 작업 할당기는 현재 연결된 컴퓨터 중 요청한 자원을 모두 갖춘 컴퓨터가 몇 대인지 판단해야 한다. 예를 들어 CPU 코어 하나와 GPU 두 개가 필요한 작업이라면, 할당기는 CPU 코어를 하나 이상, GPU를 두 개 이상 가진 컴퓨터가 몇 대인지 세어야 한다.

여러분의 임무는 각 작업의 자원 요구 사항을 만족하는 연결된 컴퓨터가 몇 대인지 세는 것뿐이다. 실제 작업 할당 구현은 다른 자원봉사자가 맡았다. ICPC 커뮤니티 전체가 여러분에게 달려 있다. 도와줄 수 있는가?

첫째 줄에는 두 정수 N (1 ≤ N ≤ 105)과 K (1 ≤ K ≤ 8)가 주어진다. N은 처리해야 하는 네트워크 이벤트의 수이고, K는 ICPC에서 사용할 수 있는 자원 종류의 수이다. 이벤트는 다음 N개 줄에 시간 순서대로 한 줄에 하나씩 주어진다. 이벤트에는 세 가지 종류가 있다.

새 컴퓨터가 네트워크에 연결되는 이벤트라면, 줄에 대문자 “C”가 나오고, 이어서 컴퓨터가 공유하는 자원의 수 R (1 ≤ R ≤ 8)과 R개의 정수 T1, T2, . . . , TR (1 ≤ Ti ≤ K, i = 1, 2, . . . , R)이 주어진다. 이 정수들은 공유하는 각 자원의 종류를 나타낸다. 새 컴퓨터에는 ICPC가 1부터 시작하는 고유한 연속 정수 식별자를 암묵적으로 부여한다.

컴퓨터가 네트워크에서 분리되는 이벤트라면, 줄에 대문자 “D”가 나오고, 이어서 컴퓨터의 식별자를 나타내는 정수가 주어진다. 이 식별자는 유효한 연결된 컴퓨터의 식별자임이 보장된다.

마지막으로 사용자가 작업을 실행하려는 이벤트라면, 줄에 대문자 “J”가 나오고, 이어서 작업이 필요로 하는 자원의 수 R (1 ≤ R ≤ 8)과 R개의 정수 T1, T2, . . . , TR (1 ≤ Ti ≤ K, i = 1, 2, . . . , R)이 주어진다. 이 정수들은 필요한 각 자원의 종류를 나타낸다. 입력에는 이 종류의 이벤트가 적어도 하나 포함됨이 보장된다.

“J” 종류의 이벤트마다 한 줄을 출력한다. 그 줄에는 이벤트가 발생한 순간 네트워크에 연결되어 있고 요청된 자원을 모두 제공하는 컴퓨터의 수를 나타내는 정수가 있어야 한다. 결과는 입력과 같은 순서, 즉 시간 순서대로 출력한다.