#include <bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define ll long long
#define ld long double
#define ui __int128_t
#define pb push_back
#define fi first
#define se second
const ll MOD2 = 1e9 + 7;
const ll MOD = 998244353;
const ll MOD3 = 10007;
const ll inf = 1e18;
/********* DEBUG *********/
template<typename T>
struct is_vector : false_type {};
template<typename T, typename A>
struct is_vector<vector<T, A>> : true_type {};
template<typename T>
void print_one(const T& x) {
if constexpr (is_vector<T>::value) {
for (size_t i = 0; i < x.size(); i++) {
cout << x[i];
if (i + 1 < x.size()) cout << ' ';
}
} else {
cout << x;
}
}
template<typename... Args>
void out(const Args&... args) {
bool first = true;
auto print_arg = [&](const auto& v) {
if (!first) cout << ' ';
first = false;
print_one(v);
};
(print_arg(args), ...);
cout << endl;
}
/********* DEBUG *********/
/********* TEMPS *********/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
using i128 = __int128;
template<class T>
constexpr T power(T a, u64 b, T res = 1) {
for (; b != 0; b /= 2, a *= a) {
if (b & 1) {
res *= a;
}
}
return res;
}
template<u32 P>
constexpr u32 mulMod(u32 a, u32 b) {
return u64(a) * b % P;
}
template<u64 P>
constexpr u64 mulMod(u64 a, u64 b) {
u64 res = a * b - u64(1.L * a * b / P - 0.5L) * P;
res %= P;
return res;
}
constexpr i64 safeMod(i64 x, i64 m) {
x %= m;
if (x < 0) {
x += m;
}
return x;
}
constexpr std::pair<i64, i64> invGcd(i64 a, i64 b) {
a = safeMod(a, b);
if (a == 0) {
return {b, 0};
}
i64 s = b, t = a;
i64 m0 = 0, m1 = 1;
while (t) {
i64 u = s / t;
s -= t * u;
m0 -= m1 * u;
std::swap(s, t);
std::swap(m0, m1);
}
if (m0 < 0) {
m0 += b / s;
}
return {s, m0};
}
template<std::unsigned_integral U, U P>
struct ModIntBase {
public:
constexpr ModIntBase() : x(0) {}
template<std::unsigned_integral T>
constexpr ModIntBase(T x_) : x(x_ % mod()) {}
template<std::signed_integral T>
constexpr ModIntBase(T x_) {
using S = std::make_signed_t<U>;
S v = x_ % S(mod());
if (v < 0) {
v += mod();
}
x = v;
}
constexpr static U mod() {
return P;
}
constexpr U val() const {
return x;
}
constexpr ModIntBase operator-() const {
ModIntBase res;
res.x = (x == 0 ? 0 : mod() - x);
return res;
}
constexpr ModIntBase inv() const {
auto v = invGcd(x, mod());
assert(v.first == 1);
return v.second;
}
constexpr ModIntBase &operator*=(const ModIntBase &rhs) & {
x = mulMod<mod()>(x, rhs.val());
return *this;
}
constexpr ModIntBase &operator+=(const ModIntBase &rhs) & {
x += rhs.val();
if (x >= mod()) {
x -= mod();
}
return *this;
}
constexpr ModIntBase &operator-=(const ModIntBase &rhs) & {
x -= rhs.val();
if (x >= mod()) {
x += mod();
}
return *this;
}
constexpr ModIntBase &operator/=(const ModIntBase &rhs) & {
return *this *= rhs.inv();
}
friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs) {
lhs *= rhs;
return lhs;
}
friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs) {
lhs += rhs;
return lhs;
}
friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs) {
lhs -= rhs;
return lhs;
}
friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs) {
lhs /= rhs;
return lhs;
}
friend constexpr std::istream &operator>>(std::istream &is, ModIntBase &a) {
i64 i;
is >> i;
a = i;
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const ModIntBase &a) {
return os << a.val();
}
friend constexpr bool operator==(const ModIntBase &lhs, const ModIntBase &rhs) {
return lhs.val() == rhs.val();
}
friend constexpr std::strong_ordering operator<=>(const ModIntBase &lhs, const ModIntBase &rhs) {
return lhs.val() <=> rhs.val();
}
private:
U x;
};
template<u32 P>
using ModInt = ModIntBase<u32, P>;
template<u64 P>
using ModInt64 = ModIntBase<u64, P>;
struct Barrett {
public:
Barrett(u32 m_) : m(m_), im((u64)(-1) / m_ + 1) {}
constexpr u32 mod() const {
return m;
}
constexpr u32 mul(u32 a, u32 b) const {
u64 z = a;
z *= b;
u64 x = u64((u128(z) * im) >> 64);
u32 v = u32(z - x * m);
if (m <= v) {
v += m;
}
return v;
}
private:
u32 m;
u64 im;
};
template<u32 Id>
struct DynModInt {
public:
constexpr DynModInt() : x(0) {}
template<std::unsigned_integral T>
constexpr DynModInt(T x_) : x(x_ % mod()) {}
template<std::signed_integral T>
constexpr DynModInt(T x_) {
int v = x_ % int(mod());
if (v < 0) {
v += mod();
}
x = v;
}
constexpr static void setMod(u32 m) {
bt = Barrett(m);
}
static u32 mod() {
return bt.mod();
}
constexpr u32 val() const {
return x;
}
constexpr DynModInt operator-() const {
DynModInt res;
res.x = (x == 0 ? 0 : mod() - x);
return res;
}
constexpr DynModInt inv() const {
auto v = invGcd(x, mod());
assert(v.first == 1);
return v.second;
}
constexpr DynModInt &operator*=(const DynModInt &rhs) & {
x = bt.mul(x, rhs.val());
return *this;
}
constexpr DynModInt &operator+=(const DynModInt &rhs) & {
x += rhs.val();
if (x >= mod()) {
x -= mod();
}
return *this;
}
constexpr DynModInt &operator-=(const DynModInt &rhs) & {
x -= rhs.val();
if (x >= mod()) {
x += mod();
}
return *this;
}
constexpr DynModInt &operator/=(const DynModInt &rhs) & {
return *this *= rhs.inv();
}
friend constexpr DynModInt operator*(DynModInt lhs, const DynModInt &rhs) {
lhs *= rhs;
return lhs;
}
friend constexpr DynModInt operator+(DynModInt lhs, const DynModInt &rhs) {
lhs += rhs;
return lhs;
}
friend constexpr DynModInt operator-(DynModInt lhs, const DynModInt &rhs) {
lhs -= rhs;
return lhs;
}
friend constexpr DynModInt operator/(DynModInt lhs, const DynModInt &rhs) {
lhs /= rhs;
return lhs;
}
friend constexpr std::istream &operator>>(std::istream &is, DynModInt &a) {
i64 i;
is >> i;
a = i;
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const DynModInt &a) {
return os << a.val();
}
friend constexpr bool operator==(const DynModInt &lhs, const DynModInt &rhs) {
return lhs.val() == rhs.val();
}
friend constexpr std::strong_ordering operator<=>(const DynModInt &lhs, const DynModInt &rhs) {
return lhs.val() <=> rhs.val();
}
private:
u32 x;
static Barrett bt;
};
using DMint = DynModInt<0>;
constexpr u32 DEFAULT_MOD = MOD;
template<u32 Id>
Barrett DynModInt<Id>::bt = Barrett(DEFAULT_MOD);
using Mint = ModInt<DEFAULT_MOD>;
struct Comb {
int n;
std::vector<Mint> _fac;
std::vector<Mint> _invfac;
std::vector<Mint> _inv;
Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
Comb(int n) : Comb() {
init(n);
}
void init(int m) {
if (m <= n) return;
_fac.resize(m + 1);
_invfac.resize(m + 1);
_inv.resize(m + 1);
for (int i = n + 1; i <= m; i++) {
_fac[i] = _fac[i - 1] * i;
}
_invfac[m] = _fac[m].inv();
for (int i = m; i > n; i--) {
_invfac[i - 1] = _invfac[i] * i;
_inv[i] = _invfac[i] * _fac[i - 1];
}
n = m;
}
Mint fac(int m) {
if (m > n) init(2 * m);
return _fac[m];
}
Mint invfac(int m) {
if (m > n) init(2 * m);
return _invfac[m];
}
Mint inv(int m) {
if (m > n) init(2 * m);
return _inv[m];
}
Mint binom(int n, int m) {
if (n < m || m < 0) return 0;
return fac(n) * invfac(m) * invfac(n - m);
}
Mint binom_big(ll n, ll k) {
if (k < 0 || k > n) return 0;
Mint res = 1;
int p = DEFAULT_MOD;
while (n > 0 || k > 0) {
int ni = (int)(n % p);
int ki = (int)(k % p);
if (ki > ni) return 0;
res *= binom(ni, ki);
n /= p;
k /= p;
}
return res;
}
} comb;
template<class T, class U> inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return true; } return false; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
static inline ll splix(ll x) {
x += 0x9e3779b97f4a7c15ULL;
ll z = x;
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9ULL;
z = (z ^ (z >> 27)) * 0x94d049bb133111ebULL;
return z ^ (z >> 31);
}
/********* TEMPS *********/
#include "festival.h"
// t[i] <= 2
vector<int> max_coupons(int A, vector<int> P, vector<int> T) {
ll n = P.size();
vector<int> ans;
vector<pair<ll,ll>> a, b;
for (int i = 0; i < n; i++) {
if (T[i] == 1)
a.pb({P[i], i});
else
b.pb({P[i], i});
}
sort(all(a));
sort(all(b));
ll m = a.size();
vector<ll> pref(m + 1);
for (int i = 0; i < m; i++) {
pref[i + 1] = pref[i] + a[i].fi;
}
ll cnt = upper_bound(all(pref), A) - pref.begin() - 1;
for (int i = 0; i < cnt; i++) {
ans.pb(a[i].se);
}
ll cur = A, idx = - 1;
for (int i = 0; i < b.size(); i++) {
if (b[i].fi > cur) break;
cur -= b[i].fi;
cur *= 2;
chmin(cur, 1e9 * n);
if (chmax(cnt, upper_bound(all(pref), cur) - pref.begin() + i))
idx = i;
}
if (idx != -1) {
ans.clear();
for (int i = 0; i <= idx; i++) {
ans.pb(b[i].se);
}
for (int i = 0; i < cnt - idx - 1; i++) {
ans.pb(a[i].se);
}
}
return ans;
}
