class DinnerPlates {
public:
    vector<stack<int>> stacks;
    set <int> non_empty_stacks;
    int capacity_;
    DinnerPlates(int capacity) {
        capacity_ = capacity;
    }

    void push(int val) {
        if (non_empty_stacks.empty()) {
            stack<int> S;
            S.push(val);
            stacks.push_back(S);
            if (capacity_ > 1) {
                non_empty_stacks.insert((int)stacks.size() - 1);
            }
        } else {
            int stack_index = *non_empty_stacks.begin();
            stacks[stack_index].push(val);
            if (stacks[stack_index].size() < capacity_) {
                non_empty_stacks.insert(stack_index);
            } else
                non_empty_stacks.erase(stack_index);
        }
    }

    int pop() {
        if (stacks.empty()) {
            return -1;
        }
        int val = stacks.back().top();
        stacks.back().pop();
        if (stacks.back().empty()) {
            stacks.pop_back();
        } else {
            non_empty_stacks.insert((int)stacks.size() - 1);
        }
        return val;
    }

    int popAtStack(int index) {
        if (stacks[index].empty())
            return -1;
        int val = stacks[index].top();
        stacks[index].pop();
        non_empty_stacks.insert(index);
        return val;
    }
};

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * DinnerPlates* obj = new DinnerPlates(capacity);
 * obj->push(val);
 * int param_2 = obj->pop();
 * int param_3 = obj->popAtStack(index);
 */