#include<bits/stdc++.h>
#include<happiness.h>
using namespace std;
// define
#define execute cerr << " Time: " << fixed << setprecision(6) << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
#define ll long long
#define ld double
#define ii pair<int,int>
#define se second
#define fi first
#define iii pair<int,ii>
#define all(v) v.begin(),v.end()
#define bit(x,i) (((x)>>(i))&1LL)
#define flip(x,i) ((x)^(1LL<<(i)))
#define ms(d,x) memset(d,x,sizeof(d))
#define sitingfake 1
#define orz 1
//constant
const ll mod = 1e9 + 7;
const long long linf = 4557430888798830399;
const int inf = 1061109567;
const int maxarr = 1e6 + 5;
const int dx[] = {0,1,-1,0};
const int dy[] = {1,0,0,-1};
template<typename T> bool maximize(T &a, const T &b)
{
if(a < b) {a = b; return 1;}
return 0;
}
template<typename T> bool minimize(T &a, const T &b)
{
if(a > b) {a = b; return 1;}
return 0;
}
inline void Plus(ll & a ,ll b)
{
b %= mod;
a += b;
if(a >= mod) a -= mod;
if(a < 0) a += mod;
return;
}
inline void Mul(ll & a, ll b)
{
a %= mod; b %= mod;
a *= b;
a %= mod;
return;
}
//code
struct DynamicSeg
{
struct Node
{
ll Min;
ll lazy;
Node *left;
Node *right;
Node (ll r)
{
Min = -r + 1;
lazy = 0;
left = right = nullptr;
}
};
ll n;
DynamicSeg (ll n) : n(n) {}
Node *root = new Node (n);
void Resize(ll sz)
{
n = sz;
root -> Min = -sz + 1;
}
void ApplyAdd(Node * cur , ll val)
{
cur -> Min += val;
cur -> lazy += val;
}
void Push(Node * cur , ll l ,ll r ,ll mid)
{
if(cur -> left == nullptr) cur -> left = new Node(mid);
if(cur -> right == nullptr) cur -> right = new Node(r);
if(cur -> lazy)
{
ApplyAdd(cur -> left , cur -> lazy);
ApplyAdd(cur -> right , cur -> lazy);
cur -> lazy = 0;
}
}
void UpdateRange(Node *cur , ll l ,ll r ,ll u ,ll v , ll val)
{
if(u > r || v < l) return;
if(u <= l && r <= v)
{
ApplyAdd(cur , val);
return;
}
ll mid = (r + l) >> 1;
Push(cur, l , r , mid);
UpdateRange(cur -> left , l , mid , u , v , val);
UpdateRange(cur -> right , mid + 1 , r, u , v , val);
cur -> Min = min(cur -> left -> Min , cur -> right -> Min);
}
ll get(Node * cur ,ll l ,ll r, ll pos)
{
if(pos < l) return linf;
if(r <= pos) return cur -> Min;
ll mid = (r + l) >> 1;
Push(cur , l , r , mid);
return min(get(cur -> left , l , mid , pos) , get(cur -> right, mid + 1 , r , pos));
}
void up(ll val)
{
UpdateRange(root ,1 , n, abs(val) + 1 , n , val);
}
bool Query(ll M)
{
return get(root , 1 , n , M) >= 0;
}
}st(1e18);
int cnt1 = 0;
ll Sum = 0;
bool init(int n , ll M , ll coins [])
{
ll Lim = M * (1ll * (n + 5e5));
st.Resize(Lim);
for(int i = 0 ; i < n; i++)
{
if(coins[i] == 1) ++cnt1;
st.up(coins[i]);
Sum += coins[i];
}
return st.Query(Sum) && cnt1 >= 1;
}
bool is_happy(int type , int k , ll coins[])
{
if(type == -1)
{
for(int i = 0; i < k ; i++)
{
if(coins[i] == 1) cnt1--;
st.up(-coins[i]);
Sum -= coins[i];
}
}
else
{
for(int i = 0; i < k; i++)
{
if(coins[i] == 1) cnt1++;
Sum += coins[i];
st.up(coins[i]);
}
}
return st.Query(Sum) && cnt1 >= 1;
}
//void solve(void)
//{
// int n , q;
// ll M;
// cin >> n >> M;
// ll coins[n + 1];
//
// for(int i = 0; i < n ; i++) cin >>coins[i];
// cin >> q;
// cout << init(n , M , coins) << "\n";
// while(q--)
// {
// int type;
// cin >> type;
// int k;
// cin >> k;
// ll coins[k + 1];
// for(int i = 0; i < k;i++) cin >> coins[i];
// cout << is_happy(type , k , coins) << "\n";
// }
//}
//**
//2 5
//1 3
//0
//**/
//signed main()
//{
// ios_base::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
//
// #define task ""
//
// if(fopen(task".inp","r"))
// {
// freopen(task".inp","r",stdin);
// freopen(task".out","w",stdout);
// }
//
// int tc; tc = 1;
//
// while(tc--) solve();
//
// //execute;
//}
