28124번 - 할래 갈래

할래 갈래는 최대 $P$ 명이 즐길 수 있는 보드게임으로, $K$ 종류의 그림 $d_1, d_2, \cdots, d_K$ 중 하나가 $1$ 개 이상 그려진 카드들을 사용한다.

플레이어들에게는 $1$ 번부터 $P$ 번까지 번호가 붙어 있으며, 이들은 시계방향으로 둥글게 번호의 오름차순으로 앉아 있다. 플레이어들은 처음에 각각 $N$ 장의 카드 뭉치를 가지고 있고, 첫 게임은 $1$ 번 플레이어부터 시작한다.

새 게임을 시작하면, 카드 뭉치가 빈 플레이어가 있는 경우 해당 플레이어를 현재 게임과 앞으로의 모든 게임에서 제외한다. 그다음 시계방향으로 차례를 돌아가며 게임을 진행한다. 게임이 진행되는 매 순간 할래가 일어나거나 갈래를 외칠 수 있다. 할래가 일어나는 동안에는 갈래를 외칠 수 없고, 제외된 플레이어는 할래와 갈래에 참여할 수 없다.

할래가 일어나면, 현재 차례 플레이어의 카드 뭉치에서 카드를 뽑아 자신의 할래 칸 위에 뽑은 카드를 놓고 차례를 넘긴다. 이미 자신의 할래 칸에 카드가 놓여 있다면 기존 카드가 보이지 않게 새 카드를 올려놓는다. 카드를 뽑는 과정이기 때문에 카드 뭉치가 빈 플레이어의 차례는 건너뛰며, 모든 플레이어의 카드 뭉치가 비어있는 경우 할래는 일어날 수 없다.

어떤 플레이어가 갈래를 외치면, 모든 할래 칸에 보이는 카드들에서 각 그림이 그려진 개수의 합을 구한다. 그림 $d_i$의 개수 합이 $S_i$인 $i$가 존재한다면, 갈래를 외친 플레이어는 할래 칸에 놓인 모든 카드의 개수만큼 자신의 카드 뭉치에 카드를 추가하고, 할래 칸에 놓인 모든 카드를 버린다. 직후 게임을 새로 시작하고, 갈래를 외친 플레이어 차례가 된다.

갈래를 외쳤지만 그림의 개수가 맞지 않는 경우, 갈래를 외친 플레이어는 자신의 카드 뭉치에서 아직 게임에서 제외되지 않은 플레이어 수만큼 카드를 버린다. 버릴 카드가 부족한 경우 가진 카드를 모두 버린다.

$H$ 번의 할래가 일어나고 $G$ 번 갈래를 외친 기록이 시간 순으로 주어질 때 게임의 최종 결과를 출력하는 프로그램을 작성하라.

첫째 줄에 $P, N, K, H, G$가 공백으로 구분되어 주어진다.

둘째 줄에 $S_1, S_2, S_3, \cdots, S_K$가 공백으로 구분되어 주어진다.

셋째 줄부터 $H+G$ 개의 줄에 게임의 기록이 주어진다. 각 줄마다 다음 두 가지 형식 중 하나로 주어진다.

• i x: 할래가 일어났으며, 그림 $d_i$가 $x$ 개 그려진 카드가 할래 칸에 놓였다.
• 0 p: $p$ 번 플레이어가 갈래를 외쳤다.

항상 올바른 게임 기록이 주어진다.

첫째 줄에 현재 게임에서 제외되지 않은 플레이어의 수 $Q$를 출력한다.

둘째 줄부터 $Q$ 개의 줄에, 현재 차례 플레이어부터 시계방향으로 돌아가며 아직 제외되지 않은 플레이어의 정보를 출력한다.

각 줄마다 $j$번 플레이어의 카드 뭉치에 있는 카드의 개수 $a_j$, 할래 칸에 보이는 카드의 그림 번호 $b_j$, 할래 칸에 보이는 카드의 그림 개수 $c_j$를 출력한다. 단, 할래 칸에 카드가 놓여 있지 않은 경우 $b_j = 0$, $c_j = 0$이다.

• $2 \le P \le 100\,000$
• $1 \le N \le 1\,000\,000$
• $1 \le K \le 100\,000$
• $1 \le H, G \le 500\,000$
• $1 \le S_1, S_2, S_3, \cdots, S_K \le 1\,000\,000$
• $1 \le i \le K$
• $1 \le x \le 100\,000$
• $1 \le p \le P$
• 입력되는 모든 수는 정수이다.