공유 자전거 운영 기록

문제

공유 자전거 운영 시스템에는 N개의 대여소와 U명의 이용자가 등록되어 있다. 대여소마다 자전거를 세울 수 있는 최대 대수와 처음 보관 중인 자전거 수가 주어진다. 처음에는 모든 이용자가 자전거를 빌리지 않은 상태이다. 자전거의 개별 번호는 구분하지 않으며, 대여소에 있는 자전거와 이용자가 빌린 자전거의 수만 관리한다. 시스템에 도착한 M개의 요청을 입력 순서대로 하나씩 처리한다. 대여 요청 R u s는 이용자 u가 대여소 s에서 자전거 한 대를 빌리려는 요청이다. 해당 이용자가 현재 빌린 자전거가 없고, 해당 대여소에 자전거가 한 대 이상 있을 때만 성공한다. 성공하면 대여소의 자전거 수가 한 대 줄고 이용자는 자전거를 빌린 상태가 된다. 이미 자전거를 빌린 이용자는 추가로 빌릴 수 없다. 반납 요청 D u s는 이용자 u가 빌린 자전거를 대여소 s에 반납하려는 요청이다. 이용자가 현재 자전거를 빌린 상태이고, 해당 대여소의 자전거 수가 최대 대수보다 작을 때만 성공한다. 성공하면 대여소의 자전거 수가 한 대 늘고 이용자는 빌린 자전거가 없는 상태가 된다. 빌렸던 대여소와 다른 대여소에 반납해도 된다. 재배치 요청 M a b k는 운영 차량이 대여소 a의 자전거 k대를 대여소 b로 옮기려는 요청이다. 출발 대여소에 k대 이상이 있고 도착 대여소에 k대를 모두 세울 자리가 있을 때만 성공한다. 성공하면 출발 대여소에서는 k대가 줄고 도착 대여소에서는 k대가 늘어난다. 일부만 옮기는 처리는 하지 않으며, 재배치는 이용자의 대여 상태에 영향을 주지 않는다. 어떤 요청이든 성공 조건을 만족하지 못하면 실패하며 모든 상태를 그대로 유지한다. 앞선 요청의 처리 결과는 바로 다음 요청에 반영된다. 입력에는 실패하는 요청이 포함될 수 있고, 모든 요청이 실패할 수도 있다. 전체 성공 횟수와 실패 횟수, 마지막 대여소별 자전거 수, 마지막에 자전거를 빌리고 있는 이용자 수를 구한다.

입력

첫째 줄에 대여소 수 N, 이용자 수 U, 요청 수 M이 공백으로 주어진다. 2 ≤ N ≤ 1,000, 1 ≤ U ≤ 10,000, 1 ≤ M ≤ 10,000이다.
다음 N개 줄에는 대여소 번호 순서대로 최대 대수 c와 초기 자전거 수 b가 주어진다. 1 ≤ c ≤ 1,000,000, 0 ≤ b ≤ c이다.
다음 M개 줄에는 R u s, D u s, M a b k 중 하나의 형식으로 요청이 주어진다. 1 ≤ u ≤ U, 1 ≤ s, a, b ≤ N, a ≠ b, 1 ≤ k ≤ 1,000,000이다. 명령 문자는 영문 대문자이며 모든 수는 정수이다.

출력

첫째 줄에 성공한 요청 수와 실패한 요청 수를 공백으로 구분하여 출력한다. 둘째 줄에 1번부터 N번 대여소까지의 최종 자전거 수를 공백으로 구분하여 출력한다. 셋째 줄에 최종적으로 자전거를 빌리고 있는 이용자 수를 출력한다. 각 개수가 없으면 0을 출력한다.

3 2 7
3 2
2 0
2 1
R 1 1
R 1 3
D 2 2
M 1 2 1
D 1 2
M 3 2 1
R 2 2

4 3
0 1 1
1

2 1 4
1 0
1 1
R 1 1
D 1 2
M 1 2 1
M 2 1 2

0 4
0 1
0

2 1 4
2 2
1 0
R 1 1
D 1 2
M 2 1 1
R 1 1

4 0
1 0
1

출처: Devin.KR 자체 제작