#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
#include <happiness.h>
#endif
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define debug(X) ;
#endif
#define ll long long
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
struct Node {
ll val;
Node *left, *right;
Node() {
val = 0;
left = right = nullptr;
}
};
Node root;
void push_to_sons(Node &v) {
if (v.left == nullptr) {
v.left = new Node();
v.right = new Node();
}
}
void update(ll a, ll x, Node &v, ll l = 0, ll r = ((ll)1<<40)-1) {
// cerr << l << ' ' << r << '\n';
if (r < a || a < l) return;
if (l == r) {
v.val += x;
return;
}
push_to_sons(v);
ll mid = (l+r)/2;
update(a, x, *v.left, l, mid); update(a, x, *v.right, mid+1, r);
v.val = (v.left)->val+(v.right)->val;
}
ll query(ll a, ll b, Node &v, ll l = 0, ll r = ((ll)1<<40)-1) {
if (r < a || b < l) return 0;
if (a <= l && r <= b) return v.val;
push_to_sons(v);
ll mid = (l+r)/2;
return query(a, b, *v.left, l, mid) + query(a, b, *v.right, mid+1, r);
}
bool check() {
ll curr = 1, sum = root.val;
while (curr < sum) {
ll t = query(0, curr, root);
if (t < curr) return false;
curr = t+1;
}
return true;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
REP(i, coinsCount) {
update(coins[i], coins[i], root);
}
return check();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
REP(i, coinsCount) {
update(coins[i], (ll)event*coins[i], root);
}
return check();
}
void clean(Node v) {
if (v.left == nullptr) return;
clean(*v.left); clean(*v.right);
delete v.left; delete v.right;
}
#ifdef LOCAL
int main () {
ll a1[] = {4, 8, 1, 2, 16};
ll a2[] = {2, 8};
ll a3[] = {7, 9, 2};
cout << init(5, 100, a1) << '\n';
cout << is_happy(-1, 2, a2) << '\n';
cout << is_happy(1, 3, a3) << '\n';
clean(root);
}
#endif
