#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, lazy;
ll start, end;
Node *left, *right;
Node() {
val = lazy = 0;
start = 0; end = (ll)((ll)1<<40)-1;
left = right = nullptr;
}
Node(ll l, ll r) {
val = lazy = 0;
start = l, end = r;
left = right = nullptr;
}
};
Node root;
void push_to_sons(Node &v) {
ll x = v.lazy;
if (v.left == nullptr) {
ll mid = (v.start+v.end)/2;
v.left = new Node(v.start, mid);
v.right = new Node(mid+1, v.end);
}
if (x == 0) return;
(v.left)->val += x;
(v.right)->val += x;
(v.left)->lazy += x;
(v.right)->lazy += x;
v.lazy = 0;
}
void update(ll a, ll x, Node &v) {
ll l = v.start, r = v.end;
// cerr << l << ' ' << r << '\n';
if (r < a || a < l) return;
if (l == r) {
v.val += x;
return;
}
push_to_sons(v);
update(a, x, *v.left); update(a, x, *v.right);
v.val = (v.left)->val+(v.right)->val;
}
ll query(ll a, ll b, Node &v) {
ll l = v.start, r = v.end;
if (r < a || b < l) return 0;
if (a <= l && r <= b) return v.val;
push_to_sons(v);
return query(a, b, *v.left) + query(a, b, *v.right);
}
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
