#include #if __has_include() #include #endif using namespace std; #define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__) #define RDVV(T,n,...) vec__VA_ARGS__;fe(refs(__VA_ARGS__),e)e.get().resizes(n);vin(__VA_ARGS__) #define VV(n,...) RDVV(ll,n,__VA_ARGS__) #define FO(n) for(ll IJK=n;IJK-->0;) #define fo(i,...) for(auto[i,i##stop,i##step]=for_range(0,__VA_ARGS__);i=i##stop;i+=i##step) #define fe(a,e,...) for(auto&&__VA_OPT__([)e __VA_OPT__(,__VA_ARGS__]):a) #define bit_sizeof(T) ll(sizeof(T)*CHAR_BIT) #define defpp void pp(const auto&...a){const char*c="";((cout<sync_with_stdio(0);cout<>...>>a);} void vin(auto&...a){fo(i,(a.size()&...))(cin>>...>>a[i]);} auto ceil(auto x,auto y){if(y<0)x=-x,y=-y;return x<=0?x/y:(x-1)/y+1;} auto lower_bound_modulo(auto k,auto r,auto m){return ceil(k-r,m)*m+r;} constexpr ui64 kth_root_floor(ui64 a,ll k){ if (k==1)return a; auto within=[&](ui32 x){ui64 t=1;FO(k)if(__builtin_mul_overflow(t,x,&t))return false;return t<=a;}; ui64 r=0; of(i,bit_sizeof(ui32))if(within(r|(1u<struct pair{ A a;B b; pair()=default; pair(A aa,B bb):a(aa),b(bb){} auto operator<=>(const pair&)const=default; }; templateusing pack_back_t=tuple_element_t>; } namespace my{ templateconcept vectorial=is_base_of_v::value_type>,remove_cvref_t>; templateconstexpr int depth=0; templateconstexpr int depth =depth+1; templatestruct core_t_helper{using type=T;}; templatestruct core_t_helper{using type=typename core_t_helper::type;}; templateusing core_t=core_t_helper::type; templatestruct vec; templatestruct hvec_helper{using type=vec::type>;}; templatestruct hvec_helper<0,T>{using type=T;}; templateusing hvec=hvec_helper::type; templatestruct vec:vector{ static constexpr int D=depth>; using C=core_t; using vector::vector; vec(const auto&...a)requires(sizeof...(a)>=3){resizes(a...);} void resizes(const auto&...a){if constexpr(sizeof...(a)==D)*this=make(a...,C{});else*this=make(a...);} static auto make(ll n,const auto&...a){ if constexpr(sizeof...(a)==1)return vec(n,array{a...}[0]); else return vec(n,make(a...)); } auto&operator+=(const vec&u){vec&v=*this;assert(v.size()==u.size());fo(i,v.size())v[i]+=u[i];return v;} vec&operator++(){fe(*this,e)++e;return*this;} ll size()const{return vector::size();} auto fold(const auto&f)const{ pairr{}; fe(*this,e){ if constexpr(!vectorial){ if(r.b)f(r.a,e); else r={e,1}; }else { } } return r; } auto max()const{return fold([](auto&a,auto b){if(arequires(sizeof...(A)>=2)vec(const A&...a)->vec>>; } namespace my{entry void main(){ LL(N,Q); VV(N,L,R,X,Y);++R; ll T=sqrt_floor(N); vec cnt(T,R.max(),0LL); vecres(R.max()); fo(i,N){ L[i]=lower_bound_modulo(L[i],Y[i],X[i]); R[i]=lower_bound_modulo(R[i],Y[i],X[i]); if(X[i]