Print Queue

Lab C++ Intermediate 20 points

Simulate a printer queue: commands add DOC PAGES and print P (print up to P pages: finish documents from the front, printing done DOC for each completed one; a partly printed document keeps its remaining pages at the front).

Input

n, then n commands.

Output

One line per finished document.

Example

Input

5
add a 3
add b 5
print 4
add c 1
print 10

Output

done a
done b
done c

Sample input available Sample output available

Editor

C++

Hints

Modify the front element through a reference to keep partial progress.

Solution explanation

A FIFO queue processes jobs in arrival order.

Show solution

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    queue<pair<string, int>> q;
    for (int i = 0; i < n; i++) {
        string cmd;
        cin >> cmd;
        if (cmd == "add") {
            string doc;
            int pages;
            cin >> doc >> pages;
            q.push({doc, pages});
        } else {
            int budget;
            cin >> budget;
            while (budget > 0 && !q.empty()) {
                auto &front = q.front();
                int used = min(budget, front.second);
                front.second -= used;
                budget -= used;
                if (front.second == 0) {
                    cout << "done " << front.first << "\n";
                    q.pop();
                }
            }
        }
    }
    return 0;
}

Output

Answer