공유 자전거 단체 요청

문제

어느 마을은 N개의 공유 자전거 대여소를 운영한다. 대여소에는 1번부터 N번까지 번호가 붙어 있으며, 모든 대여소에는 자전거를 최대 C대까지 보관할 수 있다. 하루의 업무가 시작될 때 각 대여소에 보관된 자전거 수가 주어진다. 관리 프로그램은 이후 도착하는 단체 대여 요청과 단체 반납 요청을 입력에 적힌 순서대로 처리해야 한다. 단체 대여 요청은 한 대여소에서 자전거 x대를 한꺼번에 빌리려는 요청이다. 해당 대여소에 자전거가 x대 이상 있으면 요청이 성공하며, 보관된 자전거 수가 x만큼 줄어든다. 자전거가 부족하면 요청 전체가 실패한다. 이때 일부 자전거만 빌려주지는 않으며 보관된 자전거 수 역시 바뀌지 않는다. 단체 반납 요청은 한 대여소에 자전거 x대를 한꺼번에 돌려놓으려는 요청이다. 자전거 x대를 모두 추가해도 보관된 자전거 수가 C를 넘지 않으면 요청이 성공한다. 빈자리가 부족하면 요청 전체가 실패하며, 일부 자전거만 받지는 않는다. 반납을 요청하는 자전거는 대여소 밖에서 도착하므로 이전 대여 기록을 확인할 필요가 없다. 각 요청의 성공 여부는 그 요청을 처리하기 직전의 자전거 수만으로 결정한다. 요청 사이에 자전거가 저절로 이동하거나 사라지는 일은 없다. 관리인은 업무가 끝난 뒤 실패한 요청의 총개수와 각 대여소에 남은 자전거 수를 기록하려 한다. 모든 요청을 처리한 결과를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N, C, Q가 주어진다. 1 ≤ N ≤ 100, 1 ≤ C ≤ 9, 1 ≤ Q ≤ 30,000이다.
둘째 줄에 각 대여소의 초기 자전거 수를 나타내는 정수 B_1, ..., B_N이 주어진다. 0 ≤ B_i ≤ C이다.
다음 Q개 줄에는 요청이 하나씩 주어진다. 각 요청은 R s x 또는 T s x 형식이다. R은 대여 요청, T는 반납 요청을 뜻한다. s와 x는 정수이며 1 ≤ s ≤ N, 1 ≤ x ≤ 9이다.

출력

첫째 줄에 실패한 요청의 총개수를 출력한다. 둘째 줄에 모든 요청을 처리한 뒤 각 대여소에 남은 자전거 수를 1번 대여소부터 순서대로 공백으로 구분하여 출력한다.

3 5 6
2 5 0
R 1 3
T 3 4
R 2 2
T 2 3
R 3 4
T 1 3

2
5 3 0

1 1 4
0
R 1 1
T 1 1
T 1 1
R 1 1

2
0

출처: Devin.KR 자체 제작