#include <bits/stdc++.h>
using namespace std;
#include "happiness.h"
//#define int long long
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sp <<' '<<
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
#define cont(a) for(auto el:a) cout<<el<<' '; cout<<endl;
#define contp(a) for(auto el:a) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef long long ll;
#define endl '\n'
struct Dug{
Dug *l,*r;
//l--> sol çocuğum
//r--> sag cocugum
ll sum; //bas-son aralığının toplamı
ll bas,son;
Dug(ll bas,ll son) : l(nullptr) , r(nullptr), sum(0), bas(bas), son(son) {}
};
Dug *root;
void update(ll pos,ll val,Dug *nd){
nd->sum+=val;
int bas=nd->bas;
int son=nd->son;
if(bas==son) return; //leaf node
ll mid=(bas+son)/2;
//çocuklarım varsa
if(pos<=mid){
if(nd->l==nullptr) nd->l=new Dug(bas,mid);
update(pos,val,nd->l);
}
else{
if(nd->r==nullptr) nd->r=new Dug(mid+1,son);
update(pos,val,nd->r);
}
}
ll query(ll ql,ll qr,Dug *nd){
ll bas=nd->bas;
ll son=nd->son;
if(ql>qr or bas>qr or son<ql) return 0;
if(ql<=bas and son<=qr) return nd->sum;
ll s1,s2;
s1=s2=0;
if(nd->l!=nullptr) s1=query(ql,qr,nd->l);
if(nd->r!=nullptr) s2=query(ql,qr,nd->r);
return s1+s2;
}
bool check(){
ll cur=1;
ll lim=root->sum;
while(cur<=lim){
ll top=query(1,cur,root);
if(top<cur) return false;
cur=top+1;
}
return true;
}
bool init(int n, long long m, long long coins[]) {
root=new Dug(1,m);
FOR(i,n) update(coins[i],coins[i],root);
return check();
}
bool is_happy(int event, int n, long long coins[]) {
FOR(i,n) update(coins[i],event*coins[i],root);
return check();
}
