주차 예약권의 요금 전환

문제

한 주차장은 방문 전에 구매할 수 있는 주차 예약권을 판매한다. 예약권 한 장은 주차 공간 하나를 확보하며, 동시에 유효한 예약권은 최대 K장이다. 백엔드 담당자는 구매, 취소, 요금 전환 요청이 도착한 순서대로 기록을 처리하여 예약권 재고와 정산 금액을 확인하려고 한다. 처음에는 유효한 예약권이 없고 정산 금액은 0이다. 각 고객은 1 이상 9,999 이하의 정수 번호로 구분하며, 한 고객이 동시에 보유할 수 있는 유효한 예약권은 한 장이다. 판매 요금에는 기본 요금 P와 전환 요금 Q가 있다. 처음에는 기본 요금이 적용된다. 기록의 값이 0이면 이후 구매에 적용할 요금을 다른 종류로 바꾼다. 기본 요금 상태에서는 전환 요금 상태가 되고, 전환 요금 상태에서는 기본 요금 상태가 된다. 두 요금의 금액이 같더라도 상태는 바뀐다. 요금 전환 자체는 예약권 수량이나 정산 금액에 영향을 주지 않는다. 기록의 값이 양수 x이면 x번 고객의 구매 요청이다. 그 고객에게 유효한 예약권이 없고 현재 유효한 예약권 수가 K보다 작으면 구매가 성공한다. 이때 예약권 한 장을 발급하고, 현재 적용 중인 요금을 정산 금액에 더한다. 이미 예약권이 있거나 판매 가능한 재고가 없으면 구매는 실패하며 어떤 정보도 바꾸지 않는다. 기록의 값이 음수 -x이면 x번 고객의 취소 요청이다. 그 고객에게 유효한 예약권이 있으면 이를 없애고, 해당 예약권을 구매할 때 실제로 낸 금액 전부를 정산 금액에서 뺀다. 취소된 예약권 한 장은 즉시 다시 판매할 수 있다. 환불액은 취소 시점의 요금이 아니라 구매 시점의 요금이다. 유효한 예약권이 없는 고객의 취소 요청은 실패한다. 취소한 고객은 이후에 다시 구매할 수 있으며, 다시 구매할 때의 요금으로 새 예약권을 받는다. 모든 기록을 처리한 뒤 유효한 예약권 수, 정산 금액, 실패한 요청 수를 구해야 한다. 실패한 구매와 실패한 취소는 각각 한 번씩 세며, 요금 전환은 항상 성공한다.

입력

첫째 줄에 정수 N, K, P, Q가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 60,000, 1 ≤ K ≤ 9,999, 1 ≤ P, Q ≤ 1,000,000이다.
둘째 줄에 요청을 나타내는 정수 N개가 공백으로 구분되어 주어진다. 각 정수는 -9,999 이상 9,999 이하이다. 양수 x는 x번 고객의 구매, 음수 -x는 x번 고객의 취소, 0은 적용 요금의 전환을 뜻한다.

출력

모든 요청을 처리한 뒤 유효한 예약권 수, 정산 금액, 실패한 요청 수를 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 해당 수량이나 금액이 없으면 그 자리에 0을 출력한다.

9 2 3000 5000
7 0 8 -7 9 8 -8 -7 0

1 5000 2

8 1 1200 700
4 5 0 -4 5 -5 -5 0

0 0 2

6 3 100 250
0 0 2 0 -2 3

1 250 0

출처: Devin.KR 자체 제작