#include using namespace std; #if __has_include() #include using namespace atcoder; templateistream &operator>>(istream &is,static_modint &a){long long b;is>>b;a=b;return is;} templateostream &operator<<(ostream &os,const static_modint &a){os<>(istream &is,modint &a){long long b;cin>>b;a=b;return is;} ostream &operator<<(ostream &os,const modint &a){os<; templateusing minque=priority_queue,greater>; templatebool chmax(T &a,const T &b){return (abool chmin(T &a,const T &b){return (a>b?(a=b,true):false);} templateostream &operator<<(ostream &os,const pair&p){os<istream &operator>>(istream &is,pair&p){is>>p.first>>p.second;return is;} template ostream &operator<<(ostream &os,const vector &a){cout<<'{';for(int i=0;iistream &operator>>(istream &is,vector &a){for(auto &i:a)is>>i;return is;} templatevoid operator++(pair&a,int n){a.first++,a.second++;} templatevoid operator--(pair&a,int n){a.first--,a.second--;} templatevoid operator++(vector&a,int n){for(auto &i:a)i++;} templatevoid operator--(vector&a,int n){for(auto &i:a)i--;} #define reps(i,a,n) for(int i=(a);i<(n);i++) #define rep(i,n) reps(i,0,n) #define all(x) x.begin(),x.end() #define pcnt(x) __builtin_popcount(x) ll myceil(ll a,ll b){return (a+b-1)/b;} #ifdef LOCAL template void debug(const T1& x,const T2& ...y){ cout<(0) #endif void SOLVE(); int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); #ifdef LOCAL clock_t start=clock(); #endif int testcase=1; //cin>>testcase; for(int i=0;i struct convex_hull_trick{ private: struct node{ node *left,*right; static const T inf=numeric_limits::max(); T a,b; node():node(0,inf){} node(const T a,const T b):left(nullptr),right(nullptr),a(a),b(b){} T f(const T x)const{return a*x+b;} }; static void swap(node *x,node *y){ std::swap(x->a,y->a),std::swap(x->b,y->b); } void add(node *cu,node *nw,T l,T r){ while(true){ if(nw->f(l)f(l))swap(cu,nw); if(cu->f(r-1)<=nw->f(r-1))return; T mid=(l+r)/2; if(cu->f(mid)<=nw->f(mid)){ if(!cu->right){ cu->right=new node(*nw); return; } else{ cu=cu->right,l=mid; } } else{ swap(cu,nw); if(!cu->left){ cu->left=new node(*nw); return; } else{ cu=cu->left,r=mid; } } } } T query(node *cu,T k,T l,T r)const{ T ans=numeric_limits::max(); while(cu){ chmin(ans,cu->f(k)); T mid=(l+r)/2; if(kleft,r=mid; } else{ cu=cu->right,l=mid; } } return ans; } void clear(node *cu){ if(cu->left)clear(cu->left); if(cu->right)clear(cu->right); delete cu; } const T l,r; node *root; public: convex_hull_trick(const T l,const T r):l(l),r(r),root(new node()){ assert(l>a>>q; convex_hull_trickcht(-10,1e8+10); while(q--){ int op; cin>>op; if(op==1){ ll s,t; cin>>s>>t; cht.add(-s-t,s*t); } else{ ll s; cin>>s; cout<