#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
struct Item {
ll P;
int idx;
};
static inline long long clamp_inf(i128 x) {
const long long INF = (long long)9e18;
if (x > (i128)INF) return INF;
if (x < 0) return 0;
return (long long)x;
}
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
const int N = (int)P.size();
array<vector<Item>, 5> buckets;
for (int i = 0; i < N; ++i) {
int t = T[i];
if (t < 1 || t > 4) continue;
buckets[t].push_back({(ll)P[i], i});
}
for (int t = 1; t <= 4; ++t) {
sort(buckets[t].begin(), buckets[t].end(),
[](const Item& a, const Item& b){
if (a.P != b.P) return a.P < b.P;
return a.idx < b.idx;
});
}
// Ready queues: affordable items for each T, ordered by smallest P first.
using Node = pair<ll,int>; // (P, idx)
array<priority_queue<Node, vector<Node>, greater<Node>>, 5> ready;
array<int, 5> ptr{}; // next not-yet-pushed position in each bucket
auto push_affordable = [&](long long X) {
for (int t = 1; t <= 4; ++t) {
auto &b = buckets[t];
while (ptr[t] < (int)b.size() && b[ptr[t]].P <= X) {
ready[t].push({b[ptr[t]].P, b[ptr[t]].idx});
++ptr[t];
}
}
};
long long X = A;
vector<int> ans; ans.reserve(N);
push_affordable(X);
while (true) {
int pickT = -1;
for (int t = 4; t >= 1; --t) {
if (!ready[t].empty()) { pickT = t; break; }
}
if (pickT == -1) break;
auto [p, idx] = ready[pickT].top(); ready[pickT].pop();
// Update tokens X' = T*(X - P), using 128-bit then clamp.
i128 nextX = (i128)pickT * ((i128)X - (i128)p);
X = clamp_inf(nextX);
ans.push_back(idx);
// New items may have become affordable.
push_affordable(X);
}
return ans;
}
