When processing queries, the length of \(A\) can become up to \(2 \times 10^{14}\), so it is difficult to naively maintain \(A\) as an array.

However, one can manage \(A\) as a sequence of pairs \((c,x)\) for each appending query. In other words, we store \(A\) in run-length compressed form.

How can we perform a removal query against \(A\)? We inspect the pairs \((c,x)\) in \(A\) from its beginning. If \(c \leq k\), we remove the pair from the array and keep going; if \( c > k\), we update the initial element to \((c-k,x)\) and stop removing.

This procedure yields events like “integer \(x\) has been removed \(i\) times,” allowing us to find the sum of the integers removed.

Every appending query inserts one pair, and any inserted pair is removed at most once by a removal query throughout the process. Also, every removal query modifies at most one integer pair. Therefore, the problem has been solved in a total of \(\mathrm{O}(Q)\) time.

On implementation, beware that the integer to be printed can become up to \(10^{18}\), which causes an overflow if you use a \(32\)-bit integer type.

Sample code (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int q;
    cin >> q;
    // Manage appending queries in `que`
    queue<pair<ll, ll>> que;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            ll c, x;
            cin >> c >> x;
            que.emplace(c, x); // Append (c,x)
        } else {
            ll k;
            cin >> k;
            ll ans = 0;
            // Inspect (c,x) from its beginning
            while (!que.empty() && que.front().first <= k) {
                // Remove the frontmost element and find the sum
                ans += que.front().first * que.front().second;
                k -= que.front().first;
                que.pop();
            }
            if (k != 0) {
                // The frontmost (c,x) satisfies c>k; update it to (c-k,x)
                que.front().first -= k;
                ans += k * que.front().second;
            }
            cout << ans << '\n';
        }
    }
}