Let us an integer sequence \((P _ 1,P _ 2,\ldots,P _ M)\) represent a sequence of presents where the \(i\)-th present to receive has a value \(P_i\). For a present sequence \(P\), let \(t _ P(T)\) denote the final mood when Takahashi starts with mood \(T\) and receives presents in \(P\) in order.

Let us say a present sequence \((P _ 1,P _ 2,\ldots,P _ M)\) is good when \(P _ i+A\le P _ {i+1}\) for all integers \(i\) with \(1\le i\lt M\). When he is given a good sequence, there exists an integer \(i _ {\mathrm C}\) such that, when he receives the \(i\)-th present, he is disappointed for all \(1\le i\lt i _ {\mathrm C}\) and delighted for all \(i _ {\mathrm C}\le i\le M\). This property allows us to, for a good sequence \(P\), find \(t _ P(T)\) in \(O(\log M)\) for every given \(T\).

Define that two sequences of presents \(P\) and \(Q\) are equivalent when \(t _ P(T)=t _ Q(T)\) for all \(T\). Since \(\displaystyle\lim _ {T\to+\infty}t _ P(T)-T=-B\times|P|\), any pair of equivalent sequences have an equal length.

We claim that any present sequence has an equivalent good sequence. We will present an algorithm to construct a good sequence equivalent to a given present sequence, and solve the problem using it.

Suppose that a length-\(2\) present sequence \((p,q)\) is not good. Then we can see that \((q-A,\max\lbrace q,p-B\rbrace)\) is a good sequence equivalent to \((p,q)\).

For a concatenation \(P\mathop{+\!\!+}Q\) of good sequences \(P\) and \(Q\), an equivalent good sequence can obtained by taking one element by one from the beginning of \(Q\) to execute the aforementioned procedure. Naively running it requires \(O(|P||Q|)\) operations, but one can determine the elements of the resulting sequence iteratively from the first element, in the same manner as the merge sort algorithm, allowing us to obtain an equivalent good sequence in \(O(|P|+|Q|)\) time.

Let \(M\) be the number of presents that Takahashi is going to receive, and represent \(M\) as the sum of pairwise distinct powers of two, \(2 ^ {e _ 0}\gt2 ^ {e _ 1}\gt\cdots\gt2 ^ {e _ k}\). We maintain a good sequence equivalent to each of the subarrays formed by the \(\left( \displaystyle\sum _ {0\le i\lt j}2 ^ {e _ i} \right)\)-th through \(\left( \displaystyle\sum _ {0\le i\le j}2 ^ {e _ j} \right)\)-th elements (0-based indexing).

Then, a question query can be answered by finding the mood value resulting from receiving \(k=O(\log M)\) good sequences, which can be done in \(O\bigl((\log M) ^ 2\bigr)\) time; an addition query can be handled by merging \(0\) or sequences, possible in amortized \(O(\log M)\) time. Hence, the problem has been solved.

The following is sample code.

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>

int main() {
    using namespace std;
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    unsigned N;
    long A, B;
    cin >> N >> A >> B;
    vector<long> P(N);
    for (auto&& p : P)
        cin >> p;

    // Sequence of good sequences
    vector<vector<long>> seq;

    // Sufficiently small value
    static constexpr long min_sentinel{-800000000000000};

    // Merge two good sequences to obtain an equivalent good sequence
    const auto merge{[N, A, B](auto&& lhs, auto&& rhs) -> vector<long> {
        const long L(size(lhs)), R(size(rhs));
        vector<long> result;
        result.emplace_back(min_sentinel); // sentinel
        result.reserve(L + R + 1);
        for (long l{}, r{}; l < L || r < R; )
            // Fill the elements from the beginning
            result.emplace_back(l == L || (r < R && lhs[l] - r * B > rhs[r] - (L - l) * A) ?
                                rhs[r++] - (L - l) * A :
                                max(result.back() + A, lhs[l++] - r * B));
        result.erase(begin(result)); // Remove the sentinel
        return result;
    }};

    // Append a new sequence
    // If it has the same length as the last, take it out and merge it
    const auto append_seq{[&seq, &merge](const auto& rec, vector<long>&& p) -> void {
        if (empty(seq) || size(seq.back()) != size(p))
            seq.emplace_back(move(p));
        else {
            auto lhs{move(seq.back())};
            seq.pop_back();
            rec(rec, merge(move(lhs), move(p)));
        }
    }};

    for (const auto p : P)
        append_seq(append_seq, vector{p});

    unsigned Q;
    cin >> Q;

    for (unsigned i{}; i < Q; ++i) {
        unsigned T;
        long X;
        cin >> T >> X;
        if (T == 1)
            append_seq(append_seq, vector{X});
        else {
            for (const auto& s : seq) // For each good sequence
                // Do binary search to find mood delta
                X += A * size(s) - (A + B) * *ranges::partition_point(views::iota(0UL, size(s)), [X, &s, B](const long i){
                    return X > s[i] + i * B;
                });
            cout << X << '\n';
        }
    }
    cout << flush;

    return 0;
}