항공권 예약 원장

문제

항공권 판매 백엔드는 여러 항공편의 남은 좌석과 예약별 결제 상태를 관리한다. 요청은 입력된 순서대로 하나씩 처리한다. 항공편마다 처음 판매할 수 있는 좌석 수와 좌석 한 개당 취소 수수료가 정해져 있다. 예약은 대기, 결제, 취소 중 하나의 상태를 가지며, 예약 식별자로 구별한다. B id f k p는 항공편 f의 좌석 k개를 개당 p원에 예약하는 요청이다. 식별자 id로 성공한 예약이 과거에 한 번도 없고, 해당 항공편의 남은 좌석이 k개 이상일 때만 성공한다. 성공하면 좌석 k개를 즉시 차감하고 대기 상태의 예약을 만든다. 실패한 요청은 식별자를 사용한 것으로 간주하지 않으므로 같은 식별자로 다시 예약을 시도할 수 있다. 한 번 성공한 식별자는 이후 예약이 취소되어도 다시 사용할 수 없다. P id는 결제 요청이다. 해당 식별자의 예약이 대기 상태일 때만 성공한다. 성공하면 결제 상태로 바꾸고 예약 당시의 k와 p를 곱한 금액을 누적 순수입에 더한다. 좌석 수는 변하지 않는다. C id는 취소 요청이다. 예약이 대기 또는 결제 상태일 때만 성공하며, 좌석 k개를 돌려주고 취소 상태로 바꾼다. 대기 상태를 취소하면 금액 변동은 없다. 결제 상태를 취소하면 좌석 한 개당 max(p-h, 0)원을 환불하여 그 합계를 누적 순수입에서 뺀다. 여기서 h는 해당 항공편의 취소 수수료다. 존재하지 않는 예약에 대한 결제나 취소, 이미 결제한 예약에 대한 재결제, 취소된 예약에 대한 모든 결제와 취소는 실패한다. 실패한 요청은 어떤 값도 바꾸지 않는다. 처음 누적 순수입은 0원이다. 모든 요청을 처리한 뒤 성공한 예약·결제·취소 요청의 수와 누적 순수입, 항공편별 남은 좌석 수를 보고해야 한다.

입력

첫째 줄에 항공편 수 F와 요청 수 Q가 주어진다. 다음 F개 줄의 f번째 줄에 최초 좌석 수 S_f와 취소 수수료 H_f가 주어진다. 다음 Q개 줄에 B id f k p, P id, C id 중 하나가 주어진다.
모든 수는 정수이다. 1≤F≤2,000, 1≤Q≤20,000, 0≤S_f≤1,000, 0≤H_f≤9,999, 1≤f≤F, 1≤k≤1,000, 0≤p≤9,999이다. id는 길이 1 이상 8 이하인 영문 소문자와 숫자로 이루어진 문자열이며 첫 글자는 영문 소문자다. 식별자는 문자열 전체가 같을 때만 같은 것으로 취급한다.

출력

첫째 줄에 성공한 예약 요청 수, 성공한 결제 요청 수, 성공한 취소 요청 수, 최종 누적 순수입을 공백으로 구분하여 출력한다. 둘째 줄에 1번부터 F번 항공편까지 남은 좌석 수를 공백으로 구분하여 출력한다. 성공한 요청이 없으면 해당 횟수는 0이다.

2 10
3 20
1 80
B a 1 2 100
P a
B b 1 2 50
C a
B b 1 2 50
P b
C b
B a 2 1 90
P ghost
C a

2 2 2 80
3 1

1 8
1 80
B x 1 1 30
C x
P x
B x 1 1 30
B y 1 1 30
P y
C y
C y

2 1 2 30
1

1 3
0 0
B a 1 1 0
P a
C a

0 0 0 0
0

출처: Devin.KR 자체 제작