<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

311. Ice-cream Tycoon
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



You've recently started an ice-cream business in a local school. During a day you have many suppliers delivering the ice-cream for you, and many students buying it from you. You are not allowed to set the prices, as you are told the price for each piece of ice-cream by the suppliers.

The day is described with a sequence of queries. Each query can be either ARRIVE n c, meaning that a supplier has delivered n pieces of ice-cream priced c each to you, or BUY n t, meaning that a student wants to buy n pieces of ice-cream, having a total of t money. The latter is processed as follows: in case n cheapest pieces of ice-cream you have cost no more than t (together), you sell those n cheapest pieces to the student; in case they cost more, she gets nothing. You start the day with no ice-cream.

For each student, output HAPPY if she gets her ice-cream, and UNHAPPYif she doesn't.

Input
The input file contains between 1 and 105 queries (inclusive), each on a separate line. The queries are formatted as described above, either ARRIVE n c or BUY n t, 1 ≤ n, c ≤ 106, 1 ≤ t ≤ 1012.

Output
For each BUY-query output one line, containing either the word HAPPY or the word UNHAPPY (answers should be in the same order as the corresponding queries).

Example(s)
sample input
sample output
ARRIVE 1 1
ARRIVE 10 200
BUY 5 900
BUY 5 900
BUY 5 1000
HAPPY
UNHAPPY
HAPPY

<|response|>
1. Abridged Problem Statement  
You start with no ice-cream. You process up to 10^5 queries of two types:  
• ARRIVE n c: A supplier delivers n pieces, each costing c.  
• BUY n t: A student wants to buy the n cheapest pieces and has t money.  
  – If the total cost of those n cheapest pieces ≤ t, you remove them from stock and print “HAPPY”.  
  – Otherwise, you leave your stock unchanged and print “UNHAPPY”.  

Prices c range from 1 to 10^6, n up to 10^6 per ARRIVE, total t up to 10^12.

2. Key Observations
- We need to maintain a multiset of prices with fast:
  1. Insert n copies of price c.
  2. Query the total cost of the k smallest prices.
  3. If affordable, delete exactly those k smallest.
- An ordered balanced BST keyed by price gives this directly: the k cheapest pieces are always the leftmost ones in key order.
- The embedded C++ uses a treap. Each node represents one ARRIVE batch at a price `key`, storing its own `data = {count, count*price}` and a subtree aggregate `subtree = {total count, total cost}` (componentwise sum), recomputed in `pull()`.
- With these aggregates we can perform an order-statistics split `split_by_count(root, k)`: walk down using the per-subtree counts to cut off exactly the k cheapest pieces. If k lands inside a batch, split that batch into two nodes (one with exactly k pieces, one with the rest).
- After the split, the left part's aggregate immediately gives both the piece count (must equal k) and the total cost (must be ≤ t).

3. Full Solution Approach
1. Maintain an empty treap keyed by price, with each node holding `{count, count*price}` and the subtree aggregate `{total count, total cost}`.
2. For ARRIVE(n, c): insert a node with key c and data `{n, n*c}`. Equal prices may coexist as separate nodes; we never query by exact key, so no special merging is needed.
3. For BUY(k, t):
   a) Call `split_by_count(root, k)` to split the treap into `t1` (the k cheapest pieces) and `t2` (the rest). The split descends left while the left subtree already holds ≥ k pieces; otherwise it subtracts that count and, if the boundary falls inside the current node's batch, creates a new node with exactly k pieces at this price and shrinks the current one; otherwise it recurses right.
   b) If `t1` is empty, or `t1`'s total cost exceeds t, or `t1` does not actually contain k pieces (not enough stock), then merge `t1` and `t2` back and print “UNHAPPY”.
   c) Otherwise drop `t1`, set `root = t2`, and print “HAPPY”.
4. Each operation costs O(log N) where N is the current number of batches in the treap, comfortably within the limits for up to 10^5 queries.
4. C++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

template<class KeyT, class T, T (*merge_func)(T, T), uint64_t (*rng)()>
struct TreapNode {
    KeyT key;
    T data, subtree;
    uint64_t prior;
    size_t size;
    TreapNode *left, *right;

    TreapNode(KeyT key, T data)
        : key(key), data(data), left(nullptr), right(nullptr), size(1) {
        prior = rng();
    }

    void pull() {
        subtree = data;
        size = 1;
        if(left) {
            subtree = merge_func(left->subtree, subtree);
            size += left->size;
        }
        if(right) {
            subtree = merge_func(subtree, right->subtree);
            size += right->size;
        }
    }

    friend pair<TreapNode*, TreapNode*> split(TreapNode* t, KeyT key) {
        if(!t) {
            return {nullptr, nullptr};
        }
        if(key < t->key) {
            auto [left, t_left] = split(t->left, key);
            t->left = t_left;
            t->pull();
            return {left, t};
        } else {
            auto [t_right, right] = split(t->right, key);
            t->right = t_right;
            t->pull();
            return {t, right};
        }
    }

    friend pair<TreapNode*, TreapNode*> split_by_size(
        TreapNode* t, size_t size
    ) {
        if(!t) {
            return {nullptr, nullptr};
        }
        if(t->left && t->left->size >= size) {
            auto [left, t_left] = split_by_size(t->left, size);
            t->left = t_left;
            t->pull();
            return {left, t};
        } else {
            auto [t_right, right] = split_by_size(
                t->right, size - 1 - (t->left ? t->left->size : 0)
            );
            t->right = t_right;
            t->pull();
            return {t, right};
        }
    }

    friend TreapNode* merge(TreapNode* l, TreapNode* r) {
        if(!l || !r) {
            return l ? l : r;
        } else if(l->prior > r->prior) {
            l->right = merge(l->right, r);
            l->pull();
            return l;
        } else {
            r->left = merge(l, r->left);
            r->pull();
            return r;
        }
    }

    friend TreapNode* unordered_merge(TreapNode* l, TreapNode* r) {
        if(!l) {
            return r;
        }
        if(!r) {
            return l;
        }
        if(l->prior < r->prior) {
            swap(l, r);
        }
        auto [t1, t2] = split(r, l->key);
        l->left = unordered_merge(l->left, t1);
        l->right = unordered_merge(l->right, t2);
        l->pull();
        return l;
    }

    friend void insert_in(TreapNode*& t, TreapNode* it) {
        if(!t) {
            t = it;
        } else if(it->prior > t->prior) {
            auto [t1, t2] = split(t, it->key);
            it->left = t1;
            it->right = t2;
            t = it;
        } else {
            insert_in(it->key < t->key ? t->left : t->right, it);
        }
        t->pull();
    }

    friend TreapNode* erase_from(
        TreapNode*& t, KeyT key, bool delete_node = false
    ) {
        T return_data;
        if(t->key == key) {
            auto tmp = t;
            t = merge(t->left, t->right);

            return_data = tmp->data;
            if(delete_node) {
                delete tmp;
            }
        } else {
            return_data =
                erase_from(key < t->key ? t->left : t->right, key, delete_node);
        }
        if(t) {
            t->pull();
        }
        return return_data;
    }
};

template<class KeyT, class T, T (*merge_func)(T, T)>
class Treap {
  public:
    static uint64_t rng() {
        static mt19937_64 static_rng(random_device{}());
        return static_rng();
    }

    using Node = TreapNode<KeyT, T, merge_func, Treap::rng>;

    void _pull_all(Node* t) {
        if(t) {
            _pull_all(t->left);
            _pull_all(t->right);
            t->pull();
        }
    }

    Node* root;

    Treap() { root = nullptr; }
    Treap(const vector<KeyT, T>& a) { build_cartesian_tree(a); }

    void build_cartesian_tree(const vector<pair<KeyT, T>>& a) {
        root = nullptr;
        vector<Node*> st;
        for(const auto& [key, val]: a) {
            Node* new_node = new Node(key, val);
            Node* last = nullptr;
            while(!st.empty() && st.back()->prior < new_node->prior) {
                last = st.back();
                st.pop_back();
            }

            if(last) {
                new_node->left = last->right;
            }

            if(st.empty()) {
                root = new_node;
            } else {
                if(new_node->val < st.back()->val) {
                    st.back()->left = new_node;
                } else {
                    st.back()->right = new_node;
                }
            }
            st.push_back(new_node);
        }

        _pull_all(root);
    }

    void insert(KeyT key, T data) {
        Node* new_node = new Node(key, data);
        insert_in(root, new_node);
    }

    void erase(KeyT key) { return erase_from(root, key); }

    friend Treap<KeyT, T, merge_func> merge_treaps(
        Treap<KeyT, T, merge_func> l, Treap<KeyT, T, merge_func> r
    ) {
        Treap<KeyT, T, merge_func> res;
        res.root = unordered_merge(l.root, r.root);
        return res;
    }
};

pair<int64_t, int64_t> plus_func(
    pair<int64_t, int64_t> a, pair<int64_t, int64_t> b
) {
    return {a.first + b.first, a.second + b.second};
}

using TreapWithCount = Treap<int64_t, pair<int64_t, int64_t>, plus_func>;
using Node = TreapWithCount::Node;

pair<Node*, Node*> split_by_count(Node* t, int64_t k) {
    if(!t) {
        return {nullptr, nullptr};
    }
    if(t->left && t->left->subtree.first >= k) {
        auto [left, t_left] = split_by_count(t->left, k);
        t->left = t_left;
        t->pull();
        return {left, t};
    } else {
        k -= (t->left ? t->left->subtree.first : 0);
        if(k < t->data.first) {
            Node* new_left = new Node(t->key, {k, k * t->key});
            t->data.first -= k;
            t->data.second = t->data.first * t->key;

            insert_in(t->left, new_left);
            new_left = t->left;
            t->left = nullptr;
            t->pull();
            return {new_left, t};
        }

        auto [t_right, new_right] = split_by_count(t->right, k - t->data.first);
        t->right = t_right;
        t->pull();
        return {t, new_right};
    }
}

void solve() {
    // Keep the available ice-cream in a treap keyed by price. A node groups all
    // pieces at one price as data = {count, count * price}; each subtree
    // aggregates subtree = {total count, total cost} via plus_func, so the
    // cheapest k pieces always live in the leftmost part by key order.
    //
    // ARRIVE n c inserts a node for price c (insert_in merges equal keys is not
    // needed because we never query by exact key; duplicate prices simply
    // coexist as separate nodes). BUY n t calls split_by_count, which peels off
    // exactly the n cheapest pieces, splitting a price bucket in two when the
    // boundary falls inside it. If that left part has exactly n pieces and its
    // total cost is at most t we keep the split (student buys, HAPPY) and the
    // remaining treap becomes t2; otherwise we merge the pieces back and report
    // UNHAPPY.

    TreapWithCount t;

    string type;
    int64_t arg1, arg2;
    while(cin >> type >> arg1 >> arg2) {
        if(type == "ARRIVE") {
            t.insert(arg2, {arg1, arg1 * arg2});
        } else {
            auto [t1, t2] = split_by_count(t.root, arg1);
            if(!t1 || t1->subtree.second > arg2 || t1->subtree.first != arg1) {
                t.root = merge(t1, t2);
                cout << "UNHAPPY\n";
            } else {
                t.root = t2;
                cout << "HAPPY\n";
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
input = sys.stdin.readline

class Fenwick:
    def __init__(self, n):
        self.n = n
        self.f = [0] * (n+1)
    # add v at index i
    def update(self, i, v):
        while i <= self.n:
            self.f[i] += v
            i += i & -i
    # sum of [1..i]
    def query(self, i):
        s = 0
        while i > 0:
            s += self.f[i]
            i -= i & -i
        return s
    # find smallest index p with prefix sum >= target
    def lower_bound(self, target):
        pos = 0
        bit_mask = 1 << (self.n.bit_length())
        while bit_mask:
            nxt = pos + bit_mask
            if nxt <= self.n and self.f[nxt] < target:
                target -= self.f[nxt]
                pos = nxt
            bit_mask >>= 1
        return pos + 1

CMAX = 10**6
bitCount = Fenwick(CMAX)
bitSum   = Fenwick(CMAX)

for line in sys.stdin:
    parts = line.split()
    if not parts:
        continue
    op, a, b = parts[0], int(parts[1]), int(parts[2])
    if op == "ARRIVE":
        # add a pieces priced b
        bitCount.update(b, a)
        bitSum.update(b, a * b)
    else:  # BUY a pieces with budget b
        k, t = a, b
        total = bitCount.query(CMAX)
        if total < k:
            print("UNHAPPY")
            continue
        # find the price p of the k-th cheapest piece
        p = bitCount.lower_bound(k)
        cntBelow = bitCount.query(p - 1)
        needAtP = k - cntBelow
        costBelow = bitSum.query(p - 1)
        totalCost = costBelow + needAtP * p

        if totalCost > t:
            # too expensive
            print("UNHAPPY")
        else:
            # delete all pieces priced < p
            rem = cntBelow
            while rem > 0:
                q = bitCount.lower_bound(rem)
                cntAtQ = bitCount.query(q) - bitCount.query(q - 1)
                r = min(cntAtQ, rem)
                bitCount.update(q, -r)
                bitSum.update(q,   -r * q)
                rem -= r
            # delete the needed at price p
            bitCount.update(p, -needAtP)
            bitSum.update(p, -needAtP * p)
            print("HAPPY")
```