#include #include #include #include #include #include #include #include template constexpr std::enable_if_t::digits<=32,int>msb(T n){return n==0?-1:31-__builtin_clz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>msb(T n){return n==0?-1:63-__builtin_clzll(n);} template constexpr std::enable_if_t::digits<=32,int>lsb(T n){return n==0?-1:__builtin_ctz(n);} template constexpr std::enable_if_t<(std::numeric_limits::digits>32),int>lsb(T n){return n==0?-1:__builtin_ctzll(n);} template constexpr std::enable_if_t,T>floor_pow2(T n){return n==0?0:T(1)< constexpr std::enable_if_t,T>ceil_pow2(T n){return n<=1?1:T(1)<<(msb(n-1)+1);} template constexpr T safe_div(T a,T b){return a/b-(a%b&&(a^b)<0);} template constexpr T safe_ceil(T a,T b){return a/b+(a%b&&(a^b)>0);} struct VanEmdeBoasTree{ private: int n; int l,r; int s,sl; int mask; using u64=uint64_t; struct veb3{ u64 aux=0; inline void insert(int x){aux|=u64(1)<>x; return sh==0?64:x+__builtin_ctzll(sh); } inline bool contains(int x)const{return aux>>x&1;} }; struct veb2{ int l,r; int s,sl; int mask; int mn,mx; std::vectorchild; veb3 aux; veb2(){} veb2(int log2n):l(log2n/2),r((log2n+1)/2),s(1<=mx)return; } else if(x>=mx){ if(x==mx)return; std::swap(x,mx); if(x<=mn)return; } int nx=x>>r; if(child[nx].empty())aux.insert(nx); child[nx].insert(x&mask); } void erase(int x){ if(x<=mn){ if(x=mx){ if(x>mx)mx=-1; return; } } else if(x>=mx){ if(x>mx)return; x=mx=predecessor(mx-1); if(x<=mn)return; } int nx=x>>r; child[nx].erase(x&mask); if(child[nx].empty())aux.erase(nx); } bool empty()const{return mx=mx)return mx; if(x>r; int res=child[nx].predecessor(x&mask); if(res>=0)return (nx<mx)return s; int nx=x>>r; int res=child[nx].successor(x&mask); if(res<=mask)return (nx<=sl?mx:((nx<child; veb2 aux; int mn,mx; int N; public: VanEmdeBoasTree():mn(0),mx(-1){} VanEmdeBoasTree(int n):N(n){ if(n<16)n=16; n=ceil_pow2(n); int log2n=msb(n); assert(n<=(1<<24)); mn=-1; mx=n; l=log2n/2,r=(log2n+1)/2; s=1<=mx)return; } else if(x>=mx){ if(x==mx)return; std::swap(x,mx); if(x<=mn)return; } int nx=x>>r; if(child[nx].empty())aux.insert(nx); child[nx].insert(x&mask); } void erase(int x){ if(x<=mn){ if(x=mx){ if(x>mx)mx=-1; return; } } else if(x>=mx){ if(x>mx)return; x=mx=predecessor(mx-1); if(x<=mn)return; } int nx=x>>r; child[nx].erase(x&mask); if(child[nx].empty())aux.erase(nx); } void clear(){ mn=s,mx=-1; for(int i=0;i=mx)return mx; if(x>r; int res=child[nx].predecessor(x&mask); if(res>=0)return (nx<mx)return N; int nx=x>>r; int res=child[nx].successor(x&mask); if(res<=mask)return std::min(N,(nx<=sl?mx:((nx<>n>>q; string s; cin>>s; vectorveb(10,VanEmdeBoasTree(n+1)); for(int i=0;i<10;i++)veb[i].insert(0); for(int i=0;iint { if(ssize(x)==1)return (x[0]-'0')%8==0?0:-1; assert(ssize(x)==2); int now=(x[0]-'0')*10+x[1]-'0'; if(now%8==0)return 0; now=(x[1]-'0')*10+x[0]-'0'; if(now%8==0)return 1; return -1; }; auto solve=[&](int l,int r,int a,int b,int c)->int { l++,r++; int cpos=veb[c].predecessor(r-1); if(cposcpos)bpos--; if(apos>cpos)apos--; res+=r-2-bpos; if(apos>bpos)apos--; res+=r-3-apos; return res; }; while(q--){ int l,r; cin>>l>>r; l--; if(r-l<=2)cout<now)ans=now; } if(ans==(int)1e9)ans=-1; cout<