#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)
#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__)
#define pdef2(...) pdef1(int,I,__VA_ARGS__)pdef1(double,D,__VA_ARGS__)pdef1(char,C,__VA_ARGS__)pdef1(string,S,__VA_ARGS__)
#define pdef3(...) pdef2(int,I,__VA_ARGS__)pdef2(double,D,__VA_ARGS__)pdef2(char,C,__VA_ARGS__)pdef2(string,S,__VA_ARGS__)
#define pdef4(...) pdef3(int,I,__VA_ARGS__)pdef3(double,D,__VA_ARGS__)pdef3(char,C,__VA_ARGS__)pdef3(string,S,__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
// easy 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;}
opall(opeq)
// make_pair,vector calculation
#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(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<<endl;}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;}
// 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;}
PII comb(const int&m,const int&n,const PII&nd){return (n==0)?nd:comb(m-1,n-1,mp(m,n)*nd);}int comb(const int&m,const int&n){PII p=comb(m,min(n,m-n),mp((int)1,(int)1));return p.fi/p.se;}
TTT void chmin(T&a,const T&b){a=min(a,b);}
TTT void chmax(T&a,const T&b){a=max(a,b);}
// 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 moddiv(const int&a,const int&b){return modmul(a,modinv(b));}
int modpow(int a,int b){int r=1;while(b>0){if(b&1)r=modmul(r,a);a=modmul(a,a);b>>=1;}return r;}
// vector,matrix
TTT T vecsum(const VT&vec,const int&l,const int&r){T sum=0;fou(i,l,r)sum+=vec[i];return sum;}TTT T vecsum(const VT&vec){return vecsum(vec,0,si(vec));}
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;}
VVI eye(const int&n){VVI e(n,VI(n));fou(i,0,n)e[i][i]=1;return e;}
TTT VVT matpow(VVT mat,int n){int s=si(mat);VVT r=eye(s);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);}
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());}
TTT int argmin(VT&vec){T m=0;fou(i,1,si(vec))if(vec[i]<vec[m])m=i;return m;}
TTT int argmax(VT&vec){T m=0;fou(i,1,si(vec))if(vec[i]>vec[m])m=i;return m;}
#define xxximum(xxx) 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));}
xxximum(min)xxximum(max)
// 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){int s=si(vec);fod(i,1,s)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]);}
// 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;}
TTT T kruskal(UGT&g){vector<pair<T,PII>> cft;T total=0;sortup(g.edges,sortcomp(g.edges,X.cost<Y.cost));unionfind<int>uf(g.n);tra(e,g.edges)if(uf.same(e.from,e.to)==0){total+=e.cost;uf.unite(e.from,e.to);cft.emb(mp(e.cost,e.from,e.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;
  }
};





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");}};


// todo
// ナップザック問題（制約）
// 区間加算bit
// 高速フーりえ
// 最大フロー、２部グラフ



signed main(){INIT;
  in(int,a,b,c,d);
  int cd=lcm(c,d);
  a--;
  int ansa=a-(a/c+a/d-a/cd);
  int ansb=b-(b/c+b/d-b/cd);
  out(ansb-ansa);
}

Measured memory_bytes: 256