Money Sharing

Time limit1sMemory limit512 MB

Summary
Given a sequence of resupplies and loan requests, decide which requests to approve so that the balance never goes negative while declining as few as possible.
Level

Medium6 of 10

Topics
Greedy, Heap, Prefix sum, Implementation
Solved
No attempts yet

Problem

Sharing something instead of buying it is becoming more and more popular.

One of the promising sharing systems is money sharing. There are numerous approaches to it, but here we deal with the one where there is a single public entry point at which money may be borrowed or returned free of charge. It goes without saying that the system quickly became extremely popular.

Because of this popularity, keeping the system stable is hard, so one has to request borrowing money several days in advance. You are to develop an automatic managing system for money sharing. Consider a single day. During the day there are n requests to borrow money, and m resupplies are also scheduled. Both are described by a nonzero integer x. Initially the entry point has no money. When an event described by x occurs:

  • If x > 0, it is a resupply, so the amount of money at the entry point increases by x.
  • If x < 0, it is a request to borrow |x| money. If the request is approved, the amount of money at the entry point decreases by |x|. Otherwise it does not change.

Unfortunately, it is not always possible to satisfy all requests, because the entry point may eventually not have enough money to lend, so some requests may have to be declined. Given the description of all requests and resupplies, your task is to choose for each request whether to accept or decline it so that the entry point always has enough money to satisfy the accepted requests. If there are multiple possible answers, choose one with the minimum possible number of declined requests. If there are still multiple possible answers, find any one of them.

Input

The first line of input contains two integers n and m (1 ≤ n, m ≤ 105).

Each of the next n + m lines contains a single integer x (1 ≤ |x| ≤ 109) and describes an event.

Events are given in the order they occur, and no two events occur at the same moment in time.

Output

Output your answer in n + m lines.

For each resupply event, output "resupplied".

For each request, output "approved" or "declined" depending on your decision.

Examples1

  1. Example 1

    Input
    4 1
+5
-3
-2
-1
-1
    Expected output
    resupplied
declined
approved
approved
approved