Um_nik

Untitled

Jul 29th, 2021
972
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #ifndef LOCAL
  2. #pragma GCC target("avx,avx2,fma")
  3. #pragma GCC optimize ("-Ofast")
  4. #pragma GCC optimize ("unroll-loops")
  5. #endif
  6.  
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9.  
  10. using ll=long long;
  11. //#define int ll
  12.  
  13. //fast IO by yosupo
  14. //sc.read(string) だと append される
  15. struct Scanner {
  16.     FILE* fp = nullptr;
  17.     char line[(1 << 15) + 1];
  18.     size_t st = 0, ed = 0;
  19.     void reread() {
  20.         memmove(line, line + st, ed - st);
  21.         ed -= st;
  22.         st = 0;
  23.         ed += fread(line + ed, 1, (1 << 15) - ed, fp);
  24.         line[ed] = '\0';
  25.     }
  26.     bool succ() {
  27.         while (true) {
  28.             if (st == ed) {
  29.                 reread();
  30.                 if (st == ed) return false;
  31.             }
  32.             while (st != ed && isspace(line[st])) st++;
  33.             if (st != ed) break;
  34.         }
  35.         if (ed - st <= 50) reread();
  36.         return true;
  37.     }
  38.     template <class T, enable_if_t<is_same<T, string>::value, int> = 0>
  39.     bool read_single(T& ref) {
  40.         if (!succ()) return false;
  41.         while (true) {
  42.             size_t sz = 0;
  43.             while (st + sz < ed && !isspace(line[st + sz])) sz++;
  44.             ref.append(line + st, sz);
  45.             st += sz;
  46.             if (!sz || st != ed) break;
  47.             reread();            
  48.         }
  49.         return true;
  50.     }
  51.     template <class T, enable_if_t<is_integral<T>::value, int> = 0>
  52.     bool read_single(T& ref) {
  53.         if (!succ()) return false;
  54.         bool neg = false;
  55.         if (line[st] == '-') {
  56.             neg = true;
  57.             st++;
  58.         }
  59.         ref = T(0);
  60.         while (isdigit(line[st])) {
  61.             ref = 10 * ref + (line[st++] - '0');
  62.         }
  63.         if (neg) ref = -ref;
  64.         return true;
  65.     }
  66.     template <class T> bool read_single(vector<T>& ref) {
  67.         for (auto& d : ref) {
  68.             if (!read_single(d)) return false;
  69.         }
  70.         return true;
  71.     }
  72.     void read() {}
  73.     template <class H, class... T> void read(H& h, T&... t) {
  74.         bool f = read_single(h);
  75.         assert(f);
  76.         read(t...);
  77.     }
  78.     Scanner(FILE* _fp) : fp(_fp) {}
  79. };
  80.  
  81. struct Printer {
  82.   public:
  83.     template <bool F = false> void write() {}
  84.     template <bool F = false, class H, class... T>
  85.     void write(const H& h, const T&... t) {
  86.         if (F) write_single(' ');
  87.         write_single(h);
  88.         write<true>(t...);
  89.     }
  90.     template <class... T> void writeln(const T&... t) {
  91.         write(t...);
  92.         write_single('\n');
  93.     }
  94.  
  95.     Printer(FILE* _fp) : fp(_fp) {}
  96.     ~Printer() { flush(); }
  97.  
  98.   private:
  99.     static constexpr size_t SIZE = 1 << 15;
  100.     FILE* fp;
  101.     char line[SIZE], small[50];
  102.     size_t pos = 0;
  103.     void flush() {
  104.         fwrite(line, 1, pos, fp);
  105.         pos = 0;
  106.     }
  107.     void write_single(const char& val) {
  108.         if (pos == SIZE) flush();
  109.         line[pos++] = val;
  110.     }
  111.     template <class T, enable_if_t<is_integral<T>::value, int> = 0>
  112.     void write_single(T val) {
  113.         if (pos > (1 << 15) - 50) flush();
  114.         if (val == 0) {
  115.             write_single('0');
  116.             return;
  117.         }
  118.         if (val < 0) {
  119.             write_single('-');
  120.             val = -val;  // todo min
  121.         }
  122.         size_t len = 0;
  123.         while (val) {
  124.             small[len++] = char('0' + (val % 10));
  125.             val /= 10;
  126.         }
  127.         for (size_t i = 0; i < len; i++) {
  128.             line[pos + i] = small[len - 1 - i];
  129.         }
  130.         pos += len;
  131.     }
  132.     void write_single(const string& s) {
  133.         for (char c : s) write_single(c);
  134.     }
  135.     void write_single(const char* s) {
  136.         size_t len = strlen(s);
  137.         for (size_t i = 0; i < len; i++) write_single(s[i]);
  138.     }
  139.     template <class T> void write_single(const vector<T>& val) {
  140.         auto n = val.size();
  141.         for (size_t i = 0; i < n; i++) {
  142.             if (i) write_single(' ');
  143.             write_single(val[i]);
  144.         }
  145.     }
  146.     void write_single(long double d){
  147.         {
  148.             long long v=d;
  149.             write_single(v);
  150.             d-=v;
  151.         }
  152.         write_single('.');
  153.         for(int _=0;_<8;_++){
  154.             d*=10;
  155.             long long v=d;
  156.             write_single(v);
  157.             d-=v;
  158.         }
  159.     }
  160. };
  161.  
  162. Scanner sc(stdin);
  163. Printer pr(stdout);
  164.  
  165. #define rng(i,a,b) for(int i=int(a);i<int(b);i++)
  166. #define rep(i,b) rng(i,0,b)
  167. #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
  168. #define per(i,b) gnr(i,0,b)
  169. #define pb push_back
  170. #define eb emplace_back
  171. #define a first
  172. #define b second
  173. #define bg begin()
  174. #define ed end()
  175. #define all(x) x.bg,x.ed
  176. #define si(x) int(x.size())
  177. #ifdef LOCAL
  178. #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
  179. #else
  180. #define dmp(x) void(0)
  181. #endif
  182.  
  183. template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
  184. template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}
  185.  
  186. template<class t> using vc=vector<t>;
  187. template<class t> using vvc=vc<vc<t>>;
  188.  
  189. using pi=pair<int,int>;
  190. using vi=vc<int>;
  191.  
  192. template<class t,class u>
  193. ostream& operator<<(ostream& os,const pair<t,u>& p){
  194.     return os<<"{"<<p.a<<","<<p.b<<"}";
  195. }
  196.  
  197. template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
  198.     os<<"{";
  199.     for(auto e:v)os<<e<<",";
  200.     return os<<"}";
  201. }
  202.  
  203. #define mp make_pair
  204. #define mt make_tuple
  205. #define one(x) memset(x,-1,sizeof(x))
  206. #define zero(x) memset(x,0,sizeof(x))
  207. #ifdef LOCAL
  208. void dmpr(ostream&os){os<<endl;}
  209. template<class T,class... Args>
  210. void dmpr(ostream&os,const T&t,const Args&... args){
  211.     os<<t<<" ";
  212.     dmpr(os,args...);
  213. }
  214. #define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
  215. #else
  216. #define dmp2(...) void(0)
  217. #endif
  218.  
  219. using uint=unsigned;
  220. using ull=unsigned long long;
  221.  
  222. template<class t,size_t n>
  223. ostream& operator<<(ostream&os,const array<t,n>&a){
  224.     return os<<vc<t>(all(a));
  225. }
  226.  
  227. template<int i,class T>
  228. void print_tuple(ostream&,const T&){
  229. }
  230.  
  231. template<int i,class T,class H,class ...Args>
  232. void print_tuple(ostream&os,const T&t){
  233.     if(i)os<<",";
  234.     os<<get<i>(t);
  235.     print_tuple<i+1,T,Args...>(os,t);
  236. }
  237.  
  238. template<class ...Args>
  239. ostream& operator<<(ostream&os,const tuple<Args...>&t){
  240.     os<<"{";
  241.     print_tuple<0,tuple<Args...>,Args...>(os,t);
  242.     return os<<"}";
  243. }
  244.  
  245. template<class t>
  246. void print(t x,int suc=1){
  247.     cout<<x;
  248.     if(suc==1)
  249.         cout<<"\n";
  250.     if(suc==2)
  251.         cout<<" ";
  252. }
  253.  
  254. ll read(){
  255.     ll i;
  256.     cin>>i;
  257.     return i;
  258. }
  259.  
  260. vi readvi(int n,int off=0){
  261.     vi v(n);
  262.     rep(i,n)v[i]=read()+off;
  263.     return v;
  264. }
  265.  
  266. pi readpi(int off=0){
  267.     int a,b;cin>>a>>b;
  268.     return pi(a+off,b+off);
  269. }
  270.  
  271. template<class t,class u>
  272. void print(const pair<t,u>&p,int suc=1){
  273.     print(p.a,2);
  274.     print(p.b,suc);
  275. }
  276.  
  277. template<class T>
  278. void print(const vector<T>&v,int suc=1){
  279.     rep(i,v.size())
  280.         print(v[i],i==int(v.size())-1?suc:2);
  281. }
  282.  
  283. string readString(){
  284.     string s;
  285.     cin>>s;
  286.     return s;
  287. }
  288.  
  289. template<class T>
  290. T sq(const T& t){
  291.     return t*t;
  292. }
  293.  
  294. //#define CAPITAL
  295. void yes(bool ex=true){
  296.     #ifdef CAPITAL
  297.     cout<<"YES"<<"\n";
  298.     #else
  299.     cout<<"Yes"<<"\n";
  300.     #endif
  301.     if(ex)exit(0);
  302.     #ifdef LOCAL
  303.     cout.flush();
  304.     #endif
  305. }
  306. void no(bool ex=true){
  307.     #ifdef CAPITAL
  308.     cout<<"NO"<<"\n";
  309.     #else
  310.     cout<<"No"<<"\n";
  311.     #endif
  312.     if(ex)exit(0);
  313.     #ifdef LOCAL
  314.     cout.flush();
  315.     #endif
  316. }
  317. void possible(bool ex=true){
  318.     #ifdef CAPITAL
  319.     cout<<"POSSIBLE"<<"\n";
  320.     #else
  321.     cout<<"Possible"<<"\n";
  322.     #endif
  323.     if(ex)exit(0);
  324.     #ifdef LOCAL
  325.     cout.flush();
  326.     #endif
  327. }
  328. void impossible(bool ex=true){
  329.     #ifdef CAPITAL
  330.     cout<<"IMPOSSIBLE"<<"\n";
  331.     #else
  332.     cout<<"Impossible"<<"\n";
  333.     #endif
  334.     if(ex)exit(0);
  335.     #ifdef LOCAL
  336.     cout.flush();
  337.     #endif
  338. }
  339.  
  340. constexpr ll ten(int n){
  341.     return n==0?1:ten(n-1)*10;
  342. }
  343.  
  344. const ll infLL=LLONG_MAX/3;
  345.  
  346. #ifdef int
  347. const int inf=infLL;
  348. #else
  349. const int inf=INT_MAX/2-100;
  350. #endif
  351.  
  352. int topbit(signed t){
  353.     return t==0?-1:31-__builtin_clz(t);
  354. }
  355. int topbit(ll t){
  356.     return t==0?-1:63-__builtin_clzll(t);
  357. }
  358. int botbit(signed a){
  359.     return a==0?32:__builtin_ctz(a);
  360. }
  361. int botbit(ll a){
  362.     return a==0?64:__builtin_ctzll(a);
  363. }
  364. int popcount(signed t){
  365.     return __builtin_popcount(t);
  366. }
  367. int popcount(ll t){
  368.     return __builtin_popcountll(t);
  369. }
  370. bool ispow2(int i){
  371.     return i&&(i&-i)==i;
  372. }
  373. ll mask(int i){
  374.     return (ll(1)<<i)-1;
  375. }
  376.  
  377. bool inc(int a,int b,int c){
  378.     return a<=b&&b<=c;
  379. }
  380.  
  381. template<class t> void mkuni(vc<t>&v){
  382.     sort(all(v));
  383.     v.erase(unique(all(v)),v.ed);
  384. }
  385.  
  386. ll rand_int(ll l, ll r) { //[l, r]
  387.     #ifdef LOCAL
  388.     static mt19937_64 gen;
  389.     #else
  390.     static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  391.     #endif
  392.     return uniform_int_distribution<ll>(l, r)(gen);
  393. }
  394.  
  395. template<class t>
  396. void myshuffle(vc<t>&a){
  397.     rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
  398. }
  399.  
  400. template<class t>
  401. int lwb(const vc<t>&v,const t&a){
  402.     return lower_bound(all(v),a)-v.bg;
  403. }
  404.  
  405. vvc<int> readGraph(int n,int m){
  406.     vvc<int> g(n);
  407.     rep(i,m){
  408.         int a,b;
  409.         cin>>a>>b;
  410.         //sc.read(a,b);
  411.         a--;b--;
  412.         g[a].pb(b);
  413.         g[b].pb(a);
  414.     }
  415.     return g;
  416. }
  417.  
  418. vvc<int> readTree(int n){
  419.     return readGraph(n,n-1);
  420. }
  421.  
  422. /*
  423. //N() が単位元
  424. //VERIFY: yosupo
  425. //CF407E
  426. template<class N>
  427. struct segtree{
  428.     vc<N> x;
  429.     int s;
  430.     segtree(){}
  431.     template<class t>
  432.     segtree(vc<t> a){
  433.         int n=a.size();
  434.         s=1;
  435.         while(s<n){s*=2;}
  436.         x.resize(s*2);
  437.         rep(i,n)
  438.             x[s+i]=N(a[i]);
  439.         gnr(i,1,s)
  440.             x[i]=N::merge(x[i*2],x[i*2+1]);
  441.     }
  442.     void resize(int n){
  443.         s=1;
  444.         while(s<n){s*=2;}
  445.         x.assign(s*2,N());
  446.     }
  447.     void set(int i,const N&t){
  448.         i+=s;
  449.         x[i]=t;
  450.         while(i>>=1)x[i]=N::merge(x[i*2],x[i*2+1]);
  451.     }
  452.     N composite(int b,int e){
  453.         assert(b<=e);
  454.         N lf,rt;
  455.         for(int l=b+s,r=e+s;l<r;l>>=1,r>>=1){
  456.             if (l&1){
  457.                 lf=N::merge(lf,x[l]);
  458.                 l++;
  459.             }
  460.             if (r&1){
  461.                 r--;
  462.                 rt=N::merge(x[r],rt);
  463.             }
  464.         }
  465.         return N::merge(lf,rt);
  466.     }
  467.     N getall(){
  468.         return x[1];
  469.     }
  470.     //UTPC2020E
  471.     //n 超えるかもしれない
  472.     template <class F,class... Args>
  473.     pair<int,N> max_right(int l,F f,Args&&... args){
  474.         assert(0<=l&&l<=s);
  475.         if(l==s)return mp(s,N());
  476.         l+=s;
  477.        
  478.         N sm;
  479.         assert((sm.*f)(forward<Args>(args)...));
  480.         do {
  481.             while (l % 2 == 0) l >>= 1;
  482.             if (!(N::merge(sm,x[l]).*f)(forward<Args>(args)...)){
  483.                 while (l < s) {
  484.                     l = (2 * l);
  485.                     N tmp=N::merge(sm,x[l]);
  486.                     if ((tmp.*f)(forward<Args>(args)...)) {
  487.                         sm = tmp;
  488.                         l++;
  489.                     }
  490.                 }
  491.                 return mp(l - s,sm);
  492.             }
  493.             sm = N::merge(sm, x[l]);
  494.             l++;
  495.         } while ((l & -l) != l);
  496.         return mp(s,sm);
  497.     }
  498.     //UTPC2020E
  499.     template <class F,class... Args>
  500.     pair<int,N> min_left(int r,F f,Args&&... args){
  501.         assert((N().*f)(forward<Args>(args)...));
  502.         assert(0<=r&&r<=s);
  503.         if(r==0)return mp(0,N());
  504.         r+=s;
  505.         N sm;
  506.         do {
  507.             r--;
  508.             while (r > 1 && (r % 2)) r >>= 1;
  509.             if (!(N::merge(x[r],sm).*f)(forward<Args>(args)...)) {
  510.                 while (r < s) {
  511.                     r = (2 * r + 1);
  512.                     N tmp=N::merge(x[r],sm);
  513.                     if ((tmp.*f)(forward<Args>(args)...)) {
  514.                         sm = tmp;
  515.                         r--;
  516.                     }
  517.                 }
  518.                 return mp(r + 1 - s,sm);
  519.             }
  520.             sm = N::merge(x[r], sm);
  521.         } while ((r & -r) != r);
  522.         return mp(0,sm);
  523.     }
  524. };
  525.  
  526. template<class N>
  527. struct Point1D{
  528.     segtree<N> seg;
  529.     vi pos;
  530.     Point1D(){}
  531.     void clear(){
  532.         seg.clear();
  533.         pos.clear();
  534.     }
  535.     void addp(int p){
  536.         pos.pb(p);
  537.     }
  538.     void init(){
  539.         mkuni(pos);
  540.         //seg=segtree<N>(vc<N>(si(pos)));
  541.         seg.resize(si(pos));
  542.     }
  543.     int idx(int p){
  544.         return lwb(pos,p);
  545.     }
  546.     void setv(int p,N v){
  547.         seg.set(idx(p),v);
  548.     }
  549.     N get(int b,int e){
  550.         return seg.composite(idx(b),idx(e));
  551.     }
  552. };
  553.  
  554. struct MaxNode{
  555.     ll v;
  556.     MaxNode(ll vv=-infLL):v(vv){}
  557.     static MaxNode merge(const MaxNode&a,const MaxNode&b){
  558.         return MaxNode(max(a.v,b.v));
  559.     }
  560. };
  561. */
  562.  
  563. const int nmax=110010;
  564.  
  565. vc<pi> t[nmax];
  566. int in[nmax],out[nmax],iohead;
  567. ll dep[nmax];
  568.  
  569. void dfs(int v,int p,ll d){
  570.     dep[v]=d;
  571.     in[v]=iohead++;
  572.     for(auto [to,cost]:t[v])if(to!=p){
  573.         dfs(to,v,d+cost);
  574.     }
  575.     out[v]=iohead;
  576. }
  577.  
  578. /*
  579. struct Unko{
  580.     int s;
  581.     vc<Point1D<MaxNode>> z;
  582.     Unko(int n){
  583.         s=1;
  584.         while(s<n)s*=2;
  585.         z.resize(s*2);
  586.     }
  587.     void addrng(int l,int r,int y){
  588.         for(l+=s,r+=s;l<r;l>>=1,r>>=1){
  589.             if (l&1){
  590.                 //ae(v,y[l],w);
  591.                 z[l].addp(y);
  592.                 l++;
  593.             }
  594.             if (r&1){
  595.                 r--;
  596.                 //ae(v,y[r],w);
  597.                 z[r].addp(y);
  598.             }
  599.         }
  600.     }
  601.     void init(){
  602.         rng(i,1,s*2){
  603.             z[i].init();
  604.         }
  605.     }
  606.     void setval(int l,int r,int y,ll val){
  607.         for(l+=s,r+=s;l<r;l>>=1,r>>=1){
  608.             if (l&1){
  609.                 //ae(v,y[l],w);
  610.                 z[l].setv(y,val);
  611.                 l++;
  612.             }
  613.             if (r&1){
  614.                 r--;
  615.                 //ae(v,y[r],w);
  616.                 z[r].setv(y,val);
  617.             }
  618.         }
  619.     }
  620.     ll getval(int x,int l,int r){
  621.         x+=s;
  622.         ll ans=-infLL;
  623.         while(x){
  624.             chmax(ans,z[x].get(l,r).v);
  625.             x>>=1;
  626.         }
  627.         return ans;
  628.     }
  629. };
  630. */
  631.  
  632. int col[nmax];
  633.  
  634. bool dbg=false;
  635.  
  636. struct Unko{
  637.     int l,r,i;
  638. } pool[nmax*40*2];
  639.  
  640. int phead=0;
  641. Unko* getpool(int len){
  642.     Unko* res=pool+phead;
  643.     phead+=len;
  644.     return res;
  645. }
  646.  
  647. void slv(){
  648.     int n,q;
  649.     if(dbg){
  650.         n=110000;
  651.         q=110000;
  652.     }else{
  653.         sc.read(n,q);
  654.     }
  655.     rep(_,n-1){
  656.         int u,v,w;
  657.         if(dbg){
  658.             u=rand_int(0,_);
  659.             v=_;
  660.             w=rand_int(1,ten(9));
  661.         }else{
  662.             sc.read(u,v,w);
  663.             u--;v--;
  664.         }
  665.         t[u].eb(v,w);
  666.         t[v].eb(u,w);
  667.     }
  668.     dfs(0,-1,0);
  669.     /*
  670.     rep(i,q){
  671.         int kind;
  672.         if(dbg){
  673.             kind=rand_int(0,1);
  674.         }else{
  675.             sc.read(kind);
  676.         }
  677.         if(kind==0){
  678.             int u,x;
  679.             if(dbg){
  680.                 u=rand_int(0,n-1);
  681.                 x=rand_int(1,n);
  682.             }else{
  683.                 sc.read(u,x);u--;
  684.             }
  685.             col[u]=x;
  686.         }else if(kind==1){
  687.             int u,l,r,x;
  688.             if(dbg){
  689.                 u=rand_int(0,n-1);
  690.                 l=rand_int(1,n);
  691.                 r=rand_int(l,n);
  692.                 x=rand_int(1,n);
  693.             }else{
  694.                 sc.read(u,l,r,x);u--;
  695.             }
  696.             ll minus=-infLL;
  697.             rep(v,n)if(in[v]<=in[u]&&in[u]<=out[v]&&l<=col[v]&&col[v]<=r&&col[v]%x==0)
  698.                 chmax(minus,dep[v]);
  699.             if(minus<0){
  700.                 pr.writeln("Impossible!");
  701.             }else{
  702.                 pr.writeln(dep[u]-minus);
  703.             }
  704.         }else assert(false);
  705.     }*/
  706.     vvc<pi> add(n+1);
  707.     using Q=tuple<int,int,int,int>;
  708.     vvc<Q> ask(n+1);
  709.     vc<bool> isask(q);
  710.     vc<ll> ansbase(q),ansminus(q,-infLL);
  711.     rep(_,q){
  712.         int kind;
  713.         if(dbg){
  714.             kind=rand_int(0,1);
  715.         }else{
  716.             sc.read(kind);
  717.         }
  718.         if(kind==0){
  719.             int u,x;
  720.             if(dbg){
  721.                 u=rand_int(0,n-1);
  722.                 x=rand_int(1,n);
  723.             }else{
  724.                 sc.read(u,x);u--;
  725.             }
  726.             add[x].eb(_,u);
  727.         }else if(kind==1){
  728.             isask[_]=true;
  729.             int u,l,r,x;
  730.             if(dbg){
  731.                 u=rand_int(0,n-1);
  732.                 l=rand_int(1,n);
  733.                 r=rand_int(l,n);
  734.                 x=rand_int(1,n);
  735.             }else{
  736.                 sc.read(u,l,r,x);u--;
  737.             }
  738.             r++;
  739.             l=(l+x-1)/x*x;
  740.             r=(r+x-1)/x*x;
  741.             if(l<r)ask[x].eb(_,u,l,r);
  742.             ansbase[_]=dep[u];
  743.         }else assert(false);
  744.     }
  745.    
  746.     auto roudou=[&](Unko*p,int len){
  747.         static vi vs;
  748.         static vc<ll> buf;
  749.        
  750.         vs.clear();
  751.         rep(i,len){
  752.             if(p[i].r==-1)vs.pb(p[i].l);
  753.         }
  754.         mkuni(vs);
  755.        
  756.         int s=1;
  757.         while(s<si(vs))s*=2;
  758.        
  759.         buf.assign(s*2,-infLL);
  760.        
  761.         rep(i,len){
  762.             if(p[i].r==-1){
  763.                 for(int x=s+lwb(vs,p[i].l);x;x>>=1)
  764.                     chmax(ansminus[p[i].i],buf[x]);
  765.             }else{
  766.                 for(int l=lwb(vs,p[i].l)+s,r=lwb(vs,p[i].r)+s;l<r;l>>=1,r>>=1){
  767.                     if (l&1){
  768.                         //ae(v,y[l],w);
  769.                         chmax(buf[l],dep[p[i].i]);
  770.                         l++;
  771.                     }
  772.                     if (r&1){
  773.                         r--;
  774.                         //ae(v,y[r],w);
  775.                         chmax(buf[r],dep[p[i].i]);
  776.                     }
  777.                 }
  778.             }
  779.         }
  780.     };
  781.    
  782.     struct Query{
  783.         int _,u,l,r;
  784.         bool operator<(const Query&rhs)const{return _<rhs._;}
  785.     };
  786.     vc<Query> work;
  787.     vi vs,lens;
  788.     vc<Unko*> ps;
  789.     rng(x,1,n+1)if(si(ask[x])){
  790.         vs.clear();
  791.         for(auto [_,u,l,r]:ask[x]){
  792.             vs.pb(l);
  793.             vs.pb(r);
  794.         }
  795.         mkuni(vs);
  796.        
  797.         work.clear();
  798.         for(int y=vs.front();y<vs.back();y+=x){
  799.             for(auto [_,u]:add[y]){
  800.                 work.pb({_,u,int(upper_bound(all(vs),y)-vs.bg-1),-1});
  801.             }
  802.         }
  803.         for(auto [_,u,l,r]:ask[x]){
  804.             work.pb({_,u,lwb(vs,l),lwb(vs,r)});
  805.         }
  806.         sort(all(work));
  807.        
  808.         int s=1;
  809.         while(s<si(vs)-1)s*=2;
  810.         lens.assign(s*2,0);
  811.        
  812.         for(auto w:work){
  813.             if(w.r==-1){
  814.                 for(int i=s+w.l;i;i>>=1){
  815.                     lens[i]++;
  816.                 }
  817.             }else{
  818.                 for(int l=w.l+s,r=w.r+s;l<r;l>>=1,r>>=1){
  819.                     if (l&1){
  820.                         lens[l]++;
  821.                         l++;
  822.                     }
  823.                     if (r&1){
  824.                         r--;
  825.                         lens[r]++;
  826.                     }
  827.                 }
  828.             }
  829.         }
  830.        
  831.         ps.resize(s*2);
  832.         rng(i,1,s*2){
  833.             ps[i]=getpool(lens[i]);
  834.             lens[i]=0;
  835.         }
  836.        
  837.         for(auto w:work){
  838.             if(w.r==-1){
  839.                 for(int i=s+w.l;i;i>>=1){
  840.                     ps[i][lens[i]++]={in[w.u],out[w.u],w.u};
  841.                 }
  842.             }else{
  843.                 for(int l=w.l+s,r=w.r+s;l<r;l>>=1,r>>=1){
  844.                     if (l&1){
  845.                         ps[l][lens[l]++]={in[w.u],-1,w._};
  846.                         l++;
  847.                     }
  848.                     if (r&1){
  849.                         r--;
  850.                         ps[r][lens[r]++]={in[w.u],-1,w._};
  851.                     }
  852.                 }
  853.             }
  854.         }
  855.        
  856.         rng(i,1,s*2)roudou(ps[i],lens[i]);
  857.     }
  858.    
  859.     rep(i,q)if(isask[i]){
  860.         if(ansminus[i]<0){
  861.             pr.writeln("Impossible!");
  862.         }else{
  863.             pr.writeln(ansbase[i]-ansminus[i]);
  864.         }
  865.     }
  866. }
  867.  
  868. signed main(){
  869.     cin.tie(0);
  870.     ios::sync_with_stdio(0);
  871.     cout<<fixed<<setprecision(20);
  872.    
  873.     //int t;cin>>t;rep(_,t)
  874.     slv();
  875. }
  876.  
RAW Paste Data