Submission #6234737

---

Source Code Expand

#pragma GCC optimize ("O3,Ofast,inline,fast-math,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define INIT IOS;OUT_DOUBLE
#define IOS ios_base::sync_with_stdio(0);cin.tie(0)
#define OUT_DOUBLE cout<<fixed<<setprecision(10)
using namespace std;
#define int int64_t
#define double long double
#define MAXT numeric_limits<T>::max()
#define MINT numeric_limits<T>::min()
const int MAX=numeric_limits<int>::max();const int MIN=numeric_limits<int>::min();
const double EPS=1e-7;
const int MOD=1e9+7;
// typedef VVVPIDCS
#define vdef(t,T) typedef vector<t> V##T;typedef vector<V##T> VV##T;typedef vector<VV##T> VVV##T;
#define vdef_same(T) vdef(T,T)
#define defall(xdef) xdef(int,I)xdef(double,D)xdef(char,C)xdef(string,S)xdef(bool,B)
#define pdef0(t1,T1,t2,T2,t3,T3,t4,T4,t5,T5) typedef pair<t1,t2>P##T1##T2;vdef_same(P##T1##T2)typedef pair<t1,pair<t2,t3>>P##T1##T2##T3;vdef_same(P##T1##T2##T3)typedef pair<t1,pair<t2,pair<t3,t4>>>P##T1##T2##T3##T4;vdef_same(P##T1##T2##T3##T4)typedef pair<t1,pair<t2,pair<t3,pair<t4,t5>>>>P##T1##T2##T3##T4##T5;vdef_same(P##T1##T2##T3##T4##T5)
#define pdef1(...) pdef0(int,I,__VA_ARGS__)pdef0(double,D,__VA_ARGS__)pdef0(char,C,__VA_ARGS__)pdef0(string,S,__VA_ARGS__)pdef0(bool,B,__VA_ARGS__)
#define pdef2(...) pdef1(int,I,__VA_ARGS__)pdef1(double,D,__VA_ARGS__)pdef1(char,C,__VA_ARGS__)pdef1(string,S,__VA_ARGS__)pdef1(bool,B,__VA_ARGS__)
#define pdef3(...) pdef2(int,I,__VA_ARGS__)pdef2(double,D,__VA_ARGS__)pdef2(char,C,__VA_ARGS__)pdef2(string,S,__VA_ARGS__)pdef2(bool,B,__VA_ARGS__)
#define pdef4(...) pdef3(int,I,__VA_ARGS__)pdef3(double,D,__VA_ARGS__)pdef3(char,C,__VA_ARGS__)pdef3(string,S,__VA_ARGS__)pdef3(bool,B,__VA_ARGS__)
defall(vdef)defall(pdef4)
// template
#define TTT template<typename T>
#define TT2(T1,T2) template<typename T1,typename T2>
#define TT3(T1,T2,T3) template<typename T1,typename T2, typename T3>
#define VT vector<T>
#define VVT vector<VT>
#define PTT pair<T1,T2>
#define GT graph<T>
#define DGT digraph<T>
#define UGT undigraph<T>
// use frequently
#define emb emplace_back
#define pub push_back
#define pob pop_back
#define fou(i,a,n) for(int i=a;i<n;i++)
#define fod(i,a,n) for(int i=n-1;i>=a;i--)
#define tra(a,x) for(auto&a:x)
#define elif(c) else if(c)
#define si(vec) ((int)(vec).size())
#define all(vec) vec.begin(),vec.end()
#define lla(vec) vec.rbegin(),vec.rend()
#define range(vec,x,y) vec.begin()+x,vec.begin()+y
// make_pair
TT2(T1,T2)auto mp(const T1&a,const T2&b){return make_pair(a,b);}TT3(T1,T2,...Tail) auto mp(const T1&a,const T2&b,const Tail&...tail){return mp(a,mp(b,tail...));}
#define fi first
#define se second
#define fir fi
#define sec se.fi
#define thi se.se
#define firs fi
#define seco sec
#define thir thi.fi
#define four thi.se
#define secon sec
#define third thir
#define fourt four.fi
#define fifth four.se
// make_pair,vector calculation
#define opall(calc) calc(+)calc(-)calc(*)calc(/)calc(%)calc(<<)calc(>>)calc(&)calc(|)calc(^)
#define opeq(op) TT2(T1,T2)T1 operator op##=(T1&l,const T2&r){return l=l op r;}
#define pair_vec_calc(op) TT3(T1,T2,TT)PTT operator op(const PTT&p,const TT&c){return mp(p.fi op c,p.se op c);}TT3(T1,T2,TT)PTT operator op(const TT&c,const PTT&p){return mp(c op p.fi,c op p.se);}TT2(T1,T2)PTT operator op(const PTT l,const PTT&r){return mp(l.fi op r.fi,l.se op r.se);}TT2(T,TT)VT operator op(VT vec,const TT&c){tra(v,vec)v=v op c;return vec;}TT2(T,TT)VT operator op(const TT&c,VT vec){tra(v,vec)v=c op v;return vec;}TTT VT operator op(VT l,const VT&r){fou(i,0,min(si(l),si(r)))l[i]=l[i] op r[i];return l;}
opall(opeq)opall(pair_vec_calc)
// iostream
#define in(T,...) T __VA_ARGS__;_in(__VA_ARGS__)
void _in(){}TT2(Head,...Tail)void _in(Head&head,Tail&&...tail){cin>>head;_in(forward<Tail>(tail)...);}
TTT void out(const T&a){cout<<a<<"\n";}TT2(Head,...Tail)void out(const Head&head,Tail...tail){cout<<head<<" ";out(forward<Tail>(tail)...);}TTT void vout(const VT&vec){tra(v,vec)out(v);}TT2(T1,T2)istream&operator>>(istream&is,PTT&p){return is>>p.fi>>p.se;}TTT istream&operator>>(istream&is,VT&vec){tra(v,vec)is>>v;return is;}TT2(T1,T2)ostream&operator<<(ostream&os,const PTT&p){os<<p.fi<<" "<<p.se;return os;}TTT ostream&operator<<(ostream&os,const VT&vec){if(vec.empty())return os;fou(i,0,si(vec)-1)os<<vec[i]<<" ";os<<vec[si(vec)-1];return os;}
// min,max
#define argxxx_chxxx_xxximum(xxx,comp) TTT int arg##xxx(VT&vec){T m=0;fou(i,1,si(vec))if(vec[i] comp vec[m])m=i;return m;}TTT void ch##xxx(T&a,const T&b){a=xxx(a,b);}TTT T xxx##imum(const T&a){return a;}TTT T xxx##imum(const T&a,const T&b){return xxx(a,b);}TT2(T,...Tail)T xxx##imum(const T&a,const Tail&...tail){return xxx##imum(a,xxx##imum(tail...));}TTT T xxx##imum(const VT&vec){T m=vec[0];tra(v,vec)ch##xxx(m,v);return m;}TTT T xxx##imum(const VVT&mat){T m=mat[0][0];tra(vec,mat)tra(v,vec)ch##xxx(m,v);return m;}TT2(T1,T2)T1 xxx##imum(const PTT&p){return xxx(p.fi,xxx##imum(p.se));}
argxxx_chxxx_xxximum(min,<)argxxx_chxxx_xxximum(max,>)
// math basic
TTT T sign(T a){return (a>0)-(a<0);}
int gcd(const int&a,const int&b,const int&c){return b?gcd(b,a%b,0):a;}int gcd(const int&a,const int&b){return gcd(max(a,b),min(a,b),0);}int lcm(const int&a,const int&b){return a/gcd(a,b)*b;}
int fact(const int&n){int r=1;fou(i,1,n+1)r*=i;return r;}
int comb(const int&m,int n){int r=1;chmin(n,m-n);fou(i,0,n){r*=m-i;r/=i+1;}return r;}
int parm(const int&m,int n){int r=1;fou(i,0,n)r*=m-i;return r;}
int homo(const int&m,int n){return comb(m+n-1,min(m-1,n));}
VB prime_table(const int&n){VB prime(n+1,true);if(n>=0)prime[0]=false;if(n>=1)prime[1]=false;fou(i,2,n){if(!prime[i])continue;for(int j=i*2;j<=n;j+=i)prime[j]=false;}return prime;}
bool is_prime(int n){if(n<2)return false;int m=sqrt(n-1)+1;fou(i,2,m+1)if(n%i==0)return false;return true;}
// mod
int modnum(const int&a){return a%MOD+(a<0?MOD:0);}
int modinv(int a){a=modnum(a);int b=MOD,u=0,v=1;while(a>1){u-=b/a*v;b%=a;swap(a,b);swap(u,v);}return modnum(v);}
#define modcalc(opstr,op) int mod##opstr(const int&a,const int&b){return modnum(modnum(a) op modnum(b));}
modcalc(add,+)modcalc(sub,-)modcalc(mul,*)
int modfact(const int&n){int r=1;fou(i,1,n+1)r=r*i%MOD;return r;}
int moddiv(const int&a,const int&b){return a*modinv(b)%MOD;}
int modpow(int a,int b){int r=1;while(b>0){if(b&1)r=r*a%MOD;a=a*a%MOD;b>>=1;}return r;}
int modcomb(const int&m,int n){int p=1,q=1;chmin(n,m-n);fou(i,0,n){p=p*(m-i)%MOD;q=q*(i+1)%MOD;}return moddiv(p,q);}
VI modfact_table(const int&n){VI r(n+1,1);fou(i,2,n+1)r[i]=i*r[i-1]%MOD;return r;}
VI modinv_table(const int&a){VI inv(a+1),f=modfact_table(a+1),invf(a+1,modinv(f[a]));fod(i,1,a)invf[i]=invf[i+1]*(i+1)%MOD;fou(i,1,a+1)inv[i]=invf[i]*f[i-1]%MOD;return inv;}
VI modpow_table(const int&a,const int&b){VI r(b+1,1);fou(i,1,b+1)r[i]=a*r[i-1]%MOD;return r;}
VVI modcomb_table(const int&m,int n=MAX){if(m<n)n=m;VVI r(m+1,VI(n+1));r[0][0]=1;fou(i,0,m+1){r[i][0]=1;fou(j,1,min(i,n)+1){r[i][j]=(r[i-1][j-1]+r[i-1][j])%MOD;}}return r;}
// cumulated sum
TTT void cumsum(VT&vec){fou(i,1,si(vec))vec[i]+=vec[i-1];}TTT void cumsum(VVT&vec){fou(i,1,si(vec))vec[i]+=vec[i-1];fou(i,0,si(vec))cumsum(vec[i]);}
TTT T partsum(VT&vec,const int&l,const int&r){return (l==0)?vec[r-1]:vec[r-1]-vec[l-1];}TTT T partsum(VVT&vec,const int&l1,const int&r1,const int&l2,const int&r2){return (vec[r1-1][r2-1])-((l1==0)?0:vec[l1-1][r2-1])-((l2==0)?0:vec[r1-1][l2-1])+((l1==0||l2==0)?0:vec[l1-1][l2-1]);}
TTT void decumsum(VT&vec){fod(i,1,si(vec))vec[i]-=vec[i-1];}TTT void decumsum(VVT&vec){fod(i,1,si(vec))vec[i]-=vec[i-1];fod(i,0,si(vec))decumsum(vec[i]);}
// vector,matrix
TTT T vecsum(const VT&vec,const int&l=0,int r=-1){if(r==-1)r=si(vec);T sum=0;fou(i,l,r)sum+=vec[i];return sum;}
TTT T partof(T vec){return vec;}TT2(T,...Tail) T partof(T vec,const int&r,const int&l,const Tail&...tail){fou(i,0,l-r)vec[i]=vec[r+i];vec.erase(range(vec,l-r,si(vec)));fou(i,0,l-r)vec[i]=partof(vec[i],tail...);return vec;}
TTT T dot(const VT&vec1,const VT&vec2){int sum=0;fou(i,0,min(si(vec1),si(vec2)))sum+=vec1[i]*vec2[i];return sum;}TTT VVT dot(const VVT&mat1,const VVT&mat2){int h=si(mat1),w=si(mat2[0]);VVT mat(h,VI(w));fou(i,0,h)fou(j,0,w)fou(k,0,min(si(mat1[0]),si(mat2)))mat[i][j]+=mat1[i][k]*mat2[k][j];return mat;}
TTT VVT matpow(VVT mat,int n){VVT r(si(mat),VT(si(mat)));fou(i,0,si(mat))r[i][i]=1;while(n>0){if(n&1)r=dot(r,mat);mat=dot(mat,mat);n>>=1;}return r;}
#define sortcomp(vec,compXY) function<bool(decltype(vec[0]),decltype(vec[0]))>([&](auto&X,auto&Y){return compXY;})
TTT void sortup(VT&vec,function<bool(T&,T&)>f=[](T&x,T&y){return x<y;}){sort(all(vec),f);}
TTT void sortdown(VT&vec,function<bool(T&,T&)>f=[](T&x,T&y){return x<y;}){sort(lla(vec),f);}
void bucket_sort(VI&vec,const int&m,const int&M){VI bucket(M-m+1);tra(v,vec)bucket[v-m]++;cumsum(bucket);fou(i,0,si(bucket))fou(j,i==0?0:bucket[i-1],bucket[i])vec[j]=m+i;}
TTT void erase_unique(VT&vec){vec.erase(unique(all(vec)),vec.end());}
TTT void rotation(VT&vec,const int&n){if(n>0)rotate(vec.begin(),vec.begin()+n,vec.end());if(n<0)rotate(vec.rbegin(),vec.rbegin()-n,vec.rend());}
// string
int leven(string str1,string str2,int insert=1,int erase=1,int replace=1){int s1=si(str1),s2=si(str2);VVI d(s1+1,VI(s2+1));fou(i,0,s1+1)d[i][0]=i*insert;fou(j,0,s2+1)d[0][j]=j*erase;fou(i,1,s1+1)fou(j,1,s2+1){int diff=((str1[i-1]==str2[j-1])?0:1);d[i][j]=min({d[i-1][j]+insert,d[i][j-1]+erase,d[i-1][j-1]+replace*diff});}return d[s1][s2];}
int lcs(string str1,string str2){int s1=si(str1),s2=si(str2);VVI dp(s1+1,VI(s2+1));fou(i,0,s1)fou(j,0,s2){if(str1[i]==str2[j])dp[i+1][j+1]=dp[i][j]+1;else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);}return dp[s1][s2];}
// algorithm
TTT class BIT{VT tree;int n;public:BIT(int _n):n(_n){tree.resize(n);}void add(int x,T v){while(x<n){tree[x]+=v;x|=(x+1);}}T sum(int x){T v=0;while(x>=0){v+=tree[x];x=(x&(x+1))-1;}return v;}T part(int x,int y){return sum(y-1)-sum(x-1);}T get(int x){return part(x,x+1);}void set(int x,int y){add(x,-get(x)+y);}};
TTT class unionfind{public:VI par;VT wei;int n;unionfind(int _n):n(_n){par.resize(n);iota(all(par),1);wei.resize(n);}int get(const int&x){if(par[x]==(x+1))return x+1;else{int parent=sign(par[x])*get(abs(par[x])-1);wei[x]+=wei[abs(par[x])-1];return par[x]=parent;}}void get(int&x,int&y){x=get(x);y=get(y);}int weight(int x){get(x);return wei[x];}void unite(int x,int y,T w=0){w+=weight(x)-weight(y);get(x,y);if(abs(x)!=abs(y)){par[abs(y)-1]=x*sign(y);wei[abs(y)-1]=w;}}void separate(int x,int y,T w=0){w+=weight(x)-weight(y);get(x,y);if(abs(x)!=abs(y)){par[abs(y)-1]=-x*sign(y);wei[abs(y)-1]=w;}}int same(int x,int y){get(x,y);return (x==y)-(x==-y);}T diff(int x,int y){return weight(y)-weight(x);}};
TTT int binarysearch(const VT&vec,const T&n,const char&c){
  int left=-1;int right=si(vec);bool outleft=(c=='d'||c=='U');int getmin=(c=='u'||c=='d')?1:-1;
  while(right-left>1){
    int mid=left+(right-left)/2;
    bool OK=vec[mid]*getmin>=n*getmin;
    if(outleft==OK) left=mid;else right=mid;
  }
  return outleft?left:right;
}

// graph class
TTT class graph{public:struct edge{int from,to;T cost;};int n;vector<edge>edges;VVI g;function<bool(int)>ignore;graph(int _n):n(_n){g.resize(n);ignore=nullptr;}virtual int add(int from,int to,T cost)=0;void clear(){edges.clear();g=VVI(n);};virtual void set_ignore_edge_rule(const function<bool(int)> &f){ignore=f;}virtual void reset_ignore_edge_rule(){ignore = nullptr;}};
TTT class undigraph:public GT{public:VI bridge,crunode;using GT::edges;using GT::g;using GT::n;undigraph(int n):GT(n){}int add(int from,int to,T cost=1){int id=si(edges);g[from].emb(id);g[to].emb(id);edges.pub({from,to,cost});return id;}int lowlink_dfs(const int&from,int&k,const int&par,VI&ord,VI&low){ord[from]=low[from]=k++;bool is_crunode=false;int cnt=0;tra(id,g[from]){auto e=edges[id];int to=e.from^e.to^from;if(ord[to]==-1){cnt++;k=lowlink_dfs(to,k,from,ord,low);chmin(low[from],low[to]);is_crunode|=par!=-1&&low[to]>=ord[from];if(ord[from]<low[to])bridge.emb(id);}elif(to!=par)chmin(low[from],ord[to]);}is_crunode|=par==-1&&cnt>1;if(is_crunode)crunode.emb(from);return k;}void lowlink(){VI ord(n,-1),low(n,-1);int k=0;fou(i,0,n)if(ord[i]==-1)k=lowlink_dfs(i,k,-1,ord,low);}};
TTT class digraph:public GT{public:VVI strong_nodes,strong_edgeid;VI weak_edgeid,strong_id;using GT::edges;using GT::g;using GT::n;using GT::ignore;digraph(int _n):GT(_n){}int add(int from,int to,T cost=1){int id=si(edges);g[from].emb(id);edges.pub({from,to,cost});return id;}DGT revgraph()const{DGT rev(n);tra(e,edges)rev.add(e.to,e.from,e.cost);if(ignore!=nullptr){rev.set_ignore_edge_rule([&](int id){return ignore(id);});}return rev;}
  void scc_dfs(const int&from,VI&ord,VI&strong_id){
    if(strong_id[from]==-1)return;
    strong_id[from]=-1;
    tra(id,g[from]){
      auto&e=edges[id];int to=e.from^e.to^from;
      scc_dfs(to,ord,strong_id);
    }
    ord.emb(from);
  }
  void scc_rdfs(const int&from,const int&cnt,const DGT&revg){
    if(strong_id[from]!=-1)return;
    strong_id[from]=cnt;
    strong_nodes[cnt].emb(from);
    tra(id,revg.g[from]){
      auto&e=revg.edges[id];int to=e.from^e.to^from;
      if(strong_id[to]==-1){strong_edgeid[cnt].emb(id);scc_rdfs(to,cnt,revg);}
      elif(strong_id[to]==cnt){strong_edgeid[cnt].emb(id);}
      elif(strong_id[to]<cnt)weak_edgeid.emb(id);
    }
  }
  void scc(){
    VI ord(n);
    strong_id.assign(n,0);
    DGT revg=revgraph();
    fou(from,0,n)scc_dfs(from,ord,strong_id);
    reverse(all(ord));
    int cnt=0;tra(from,ord)if(strong_id[from]==-1){strong_edgeid.emb();strong_nodes.emb();scc_rdfs(from,cnt,revg);cnt++;}
  }
};
// shortest path
TTT VT dijkstra(const GT&g,const int&start){VT d(g.n,MAXT);priority_queue<pair<T,int>,vector<pair<T,int>>,greater<pair<T,int>>>s;d[start]=0;s.emplace(d[start],start);while(!s.empty()){T expected=s.top().fi;int from=s.top().se;s.pop();if(d[from]<expected)continue;tra(id,g.g[from]){auto e=g.edges[id];int to=e.from^e.to^from;if(d[from]+e.cost<d[to]){d[to]=d[from]+e.cost;s.emplace(d[to],to);}}}return d;}
TTT VT bellman(const GT&g,const int&start){VT d(g.n,MAXT);d[start]=0;bool nl=false;VI upd_b(1,start);int i=0;while(!upd_b.empty()&&i<g.n){VI upd;tra(from,upd_b){tra(id,g.g[from]){auto e=g.edges[id];int to=e.from^e.to^from;if(d[to]>d[from]+e.cost){d[to]=d[from]+e.cost;upd.emb(to);if(i==g.n-1){d[to]=MINT;nl=true;}}}}upd_b=upd;i++;}if(nl){i=0;while(!upd_b.empty()&&i<g.n-1){VI upd;tra(from,upd_b){tra(id,g.g[from]){auto e=g.edges[id];int to=e.from^e.to^from;if(d[to]!=MINT){d[to]=MINT;upd.emb(to);}}}upd_b=upd;i++;}}return d;}
// matrix graph
TTT VVT matrix_of_graph(const GT&g){VVT mat(g.n,VT(g.n,MAXT));fou(from,0,g.n){tra(id,g.g[from]){auto e=g.edges[id];int to=e.from^e.to^from;mat[from][to]=e.cost;}}return mat;}
TTT VVT warshall(VVT mat){fou(k,0,si(mat))fou(i,0,si(mat))fou(j,0,si(mat))mat[i][j]=(mat[i][k]==MAXT||mat[k][j]==MAXT)?mat[i][j]:min(mat[i][j],mat[i][k]+mat[k][j]);return mat;}
// minimum spanning tree
TTT T prim(GT&g,const int&start=0){vector<pair<T,PII>> cft;T total = 0;VI used(g.n,0);priority_queue<pair<T,PII>,vector<pair<T,PII>>,greater<pair<T,PII>>>s;s.emplace(mp(0,-1,start));while(!s.empty()){T cost=s.top().fi;int fromfrom=s.top().se.fi,from=s.top().se.se;s.pop();if(used[from])continue;used[from]=true;total+=cost;if(fromfrom>-1)cft.emb(mp(cost,fromfrom,from));tra(id,g.g[from]){auto e=g.edges[id];int to=e.from^e.to^from;s.emplace(mp(e.cost,from,to));}}g.clear();tra(a,cft)g.add(a.sec,a.thi,a.fir);return total;}
//  topological sort
TTT VI topsort(const DGT&g){
  VI to_node(g.n,0);
  fou(id,0,si(g.edges)){
    if(g.ignore!=nullptr&&g.ignore(id))continue;to_node[g.edges[id].to]++;}
    VI sorted;fou(i,0,g.n)if(to_node[i]==0)sorted.emb(i);
    fou(i,0,si(sorted)){
      tra(id,g.g[sorted[i]]){
        if(g.ignore!=nullptr&&g.ignore(id))continue;
        if(--to_node[g.edges[id].to]==0)sorted.emb(g.edges[id].to);
      }
    }
    if(si(sorted)!=g.n)return VI();
    return sorted;}



template<typename T>class forest:public UGT{public:using UGT::edges;using UGT::g;using UGT::n;VI root,parent,treesize,depth;VT dist;forest(int _n):UGT(_n){init();}void init(){root=VI(n,-1);parent=VI(n,-1);treesize=VI(n,1);depth=VI(n);dist=VT(n);}void dfs(int from){tra(id,g[from]){auto&e=edges[id];if(from==e.from)swap(e.from,e.to);int to=e.from;if(root[to]!=-1){continue;}parent[to]=from;dist[to]=dist[from]+e.cost;depth[to]=depth[from]+1;root[to]=root[from];dfs(to);treesize[from]+=treesize[to];}}void set_root(int v){if(root[v]==-1){root[v]=v;dfs(v);}}void search_all(){init();fou(v,0,n)set_root(v);}T diameter(){init();set_root(0);int end=maxe(dist);init();set_root(end);return dist[maxe(dist)];}};


TTT class flow_graph {public:
  static constexpr T eps = (T) 1e-9;struct edge{int from;int to;T c;T f;};
  VVI g;vector<edge> edges;VI ptr,d,q;int n,start,goal;T flow;
  flow_graph(int _n,int start,int goal):n(_n),start(start),goal(goal),flow(0){g.resize(_n);ptr.resize(_n);d.resize(_n);q.resize(_n);}
  void clear_flow(){tra(e,edges)e.f=0;flow=0;}
  void add(const int&from,const int&to,const T&for_cap,const T&back_cap){g[from].emb(si(edges));edges.pub({from,to,for_cap,0});g[to].emb(si(edges));edges.pub({to,from,back_cap,0});}
  bool expath(){
    fill(all(d),-1);q[0]=goal;d[goal]=0;int beg=0,end=1;
    while(beg<end) {
      int i=q[beg++];
      tra(id,g[i]){
        edge&e=edges[id];
        if(edges[id^1].c-edges[id^1].f>eps&&d[e.to]==-1) {
          d[e.to]=d[i]+1;
          if(e.to==start)return true;
          q[end++]=e.to;
        }
      }
    }
    return false;
  }
  T dfs(int v,T w){
    if(v==goal)return w;
    while(ptr[v]>=0){
      int id=g[v][ptr[v]];edge&e=edges[id];
      if(e.c-e.f>eps&&d[e.to]==d[v]-1){
        T t=dfs(e.to,min(e.c-e.f,w));if(t>eps){edges[id].f+=t;edges[id^1].f-=t;return t;}
      }
      ptr[v]--;
    }
    return 0;
  }
  T max_flow(){
    while(expath()){
      fou(i,0,n)ptr[i]=si(g[i])-1;
      T big_add=0;
      while(true){
        T add=dfs(start,MAXT);if(add<=eps)break;big_add+=add;
      }
      if(big_add<=eps)break;flow+=big_add;
    }
    return flow;
  }
  vector<bool>min_cut(){
    max_flow();vector<bool>ret(n);fou(i,0,n)ret[i]=(d[i]!=-1);return ret;
  }
};




const int FFTMOD=924844033;
const int FFTGEN=5;
int fftmodpow(int a,int b){int r=1;while(b>0){if(b&1)r=r*a%FFTMOD;a=a*a%FFTMOD;b>>=1;}return r;}
void fft(VI&a) {
  int n=si(a);
  fou(i,0,n){
    int j=0,x=i,y=n-1;
    while(y>0){
      j=(j<<1)+(x&1);
      x>>=1;y>>=1;
    }
    if(i<j)swap(a[i],a[j]);
  }
  for(int len=1;len<n;len*=2) {
    int root=fftmodpow(FFTGEN,(FFTMOD-1)/(2*len));
    for(int i=0;i<n;i+=2*len) {
      int w=1;
      for(int j=0;j<len;j++) {
        int u=a[i+j],v=a[i+j+len]*w%FFTMOD;
        a[i+j]=(u+v)%FFTMOD;a[i+j+len]=(u-v+FFTMOD)%FFTMOD;
        w=w*root%FFTMOD;
      }
    }
  }
}
 
 
VI multiply(VI a,VI b) {
  int abn=max(si(a),si(b)),need=si(a)+si(b)-1,nn=1;
  while(nn<2*abn)nn<<=1;
  a.resize(nn);b.resize(nn);
  fft(a);fft(b);
  fou(i,0,nn)a[i]=a[i]*b[i]%FFTMOD;
  reverse(++a.begin(), a.end());
  fft(a);
  int inv=fftmodpow(nn,FFTMOD-2);
  fou(i,0,nn)a[i]=a[i]*inv%FFTMOD;
  a.resize(need);
  return a;
}



class time_measure{chrono::system_clock::time_point start;public:time_measure():start(chrono::system_clock::now()){}void time(){out(chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now()-start).count(),"ms");}};
// ifstream ifs("ifile.txt");ifs>>a;
// ofstream ofs("ofile.txt");ofs<<a;





// todo
// ナップザック問題（制約）
// 区間加算bit
// 高速フーりえ



signed main(){INIT;
  in(int,n);
  VI a(n),b(n);
  fou(i,0,n){
    cin>>a[i]>>b[i];
  }
  out(0);
  vout(multiply(a,b));
}

Submission Info

Judge Result