머니 셰어링

물건을 사는 대신 공유하는 일이 점점 흔해지고 있다.

유망한 공유 시스템 중 하나는 머니 셰어링이다. 접근 방식은 여러 가지지만, 여기서는 돈을 무료로 빌리거나 반납할 수 있는 공용 거점이 하나 있는 방식을 다룬다. 이 시스템이 곧바로 큰 인기를 끌었다는 것은 말할 필요도 없다.

인기가 이렇게 높다 보니 시스템을 안정적으로 유지하기 어려워서, 돈을 빌리려면 며칠 전에 미리 신청해야 한다. 당신은 머니 셰어링을 자동으로 관리하는 시스템을 개발해야 한다. 하루를 생각해 보자. 그날 동안 돈을 빌려 달라는 요청이 n개 있고, 자금 보충도 m번 예정되어 있다. 둘 다 0이 아닌 정수 x로 나타낼 수 있다. 처음에 거점에는 돈이 없다. x로 나타나는 사건이 일어나면:

• x > 0이면 자금 보충이므로 거점의 돈이 x만큼 늘어난다.
• x < 0이면 |x|만큼의 돈을 빌려 달라는 요청이다. 요청이 승인되면 거점의 돈이 |x|만큼 줄어든다. 그렇지 않으면 변하지 않는다.

안타깝게도 모든 요청을 들어줄 수 있는 것은 아니다. 거점에 결국 돈이 부족해질 수 있으므로 일부 요청은 거절해야 할 수도 있다. 모든 요청과 자금 보충에 대한 설명이 주어졌을 때, 거점이 승인된 요청을 항상 처리할 만큼의 돈을 갖도록 각 요청을 승인할지 거절할지 정하는 것이 과제이다. 가능한 답이 여러 개라면 거절하는 요청의 수가 최소가 되는 답을 골라야 한다. 그래도 답이 여러 개라면 그중 아무거나 하나를 찾으면 된다.

첫째 줄에 두 정수 n과 m이 주어진다. (1 ≤ n, m ≤ 105)

다음 n + m개의 줄에는 각각 정수 x가 하나씩 주어지며 사건을 나타낸다. (1 ≤ |x| ≤ 109)

사건은 일어나는 순서대로 주어지며, 두 사건이 같은 시각에 일어나지 않는다.

답을 n + m개의 줄에 출력한다.

자금 보충 사건마다 “resupplied”를 출력한다.

요청마다 결정에 따라 “approved” 또는 “declined”를 출력한다.