#line 1 "library/Template/template.hpp" #include using namespace std; #define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define ALL(v) (v).begin(),(v).end() #define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end()) #define SZ(v) (int)v.size() #define MIN(v) *min_element(ALL(v)) #define MAX(v) *max_element(ALL(v)) #define LB(v,x) int(lower_bound(ALL(v),(x))-(v).begin()) #define UB(v,x) int(upper_bound(ALL(v),(x))-(v).begin()) using ll=long long int; using ull=unsigned long long; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; templateinline bool chmax(T& a,T b){if(ainline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;} templateT ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);} templateT floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);} templateint popcnt(T x){return __builtin_popcountll(x);} templateint topbit(T x){return (x==0?-1:63-__builtin_clzll(x));} templateint lowbit(T x){return (x==0?-1:__builtin_ctzll(x));} #line 2 "library/Utility/fastio.hpp" #include class FastIO{ static constexpr int L=1<<16; char rdbuf[L]; int rdLeft=0,rdRight=0; inline void reload(){ int len=rdRight-rdLeft; memmove(rdbuf,rdbuf+rdLeft,len); rdLeft=0,rdRight=len; rdRight+=fread(rdbuf+len,1,L-len,stdin); } inline bool skip(){ for(;;){ while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++; if(rdLeft==rdRight){ reload(); if(rdLeft==rdRight)return false; } else break; } return true; } template::value,int> =0>inline bool _read(T& x){ if(!skip())return false; if(rdLeft+20>=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdLeft=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdLeft=rdRight)reload(); x=0; while(rdbuf[rdLeft]>='0' and rdLeft::value,int> =0>inline bool _read(T& x){ if(!skip())return false; if(rdLeft+20>=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft='0' and rdbuf[rdLeft]<='9' and rdLeft=rdRight)reload(); x=rdbuf[rdLeft++]; return true; } inline bool _read(string& x){ if(!skip())return false; for(;;){ int pos=rdLeft; while(pos' ')pos++; x.append(rdbuf+rdLeft,pos-rdLeft); if(rdLeft==pos)break; rdLeft=pos; if(rdLeft==rdRight)reload(); else break; } return true; } templateinline bool _read(vector& v){ for(auto& x:v){ if(!_read(x))return false; } return true; } char wtbuf[L],tmp[50]; int wtRight=0; inline void _write(const char& x){ if(wtRight>L-32)flush(); wtbuf[wtRight++]=x; } inline void _write(const string& x){ for(auto& c:x)_write(c); } template::value,int> =0>inline void _write(T x){ if(wtRight>L-32)flush(); if(x==0){ _write('0'); return; } else if(x<0){ _write('-'); if (__builtin_expect(x == std::numeric_limits::min(), 0)) { switch (sizeof(x)) { case 2: _write("32768"); return; case 4: _write("2147483648"); return; case 8: _write("9223372036854775808"); return; } } x=-x; } int pos=0; while(x!=0){ tmp[pos++]=char((x%10)|48); x/=10; } rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i]; wtRight+=pos; } inline void _write(__int128_t x){ if(wtRight>L-40)flush(); if(x==0){ _write('0'); return; } else if(x<0){ _write('-'); x=-x; } int pos=0; while(x!=0){ tmp[pos++]=char((x%10)|48); x/=10; } rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i]; wtRight+=pos; } inline void _write(__uint128_t x){ if(wtRight>L-40)flush(); if(x==0){ _write('0'); return; } int pos=0; while(x!=0){ tmp[pos++]=char((x%10)|48); x/=10; } rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i]; wtRight+=pos; } inline void _write(double x){ ostringstream oss; oss << fixed << setprecision(15) << double(x); string s = oss.str(); _write(s); } templateinline void _write(const vector& v){ rep(i,0,v.size()){ if(i)_write(' '); _write(v[i]); } } public: FastIO(){} ~FastIO(){flush();} inline void read(){} template inline void read(Head& head,Tail&... tail){ assert(_read(head)); read(tail...); } templateinline void write(){if(ln)_write('\n');} template inline void write(const Head& head,const Tail&... tail){ _write(head); write(tail...); if(space)_write(' '); } inline void flush(){ fwrite(wtbuf,1,wtRight,stdout); wtRight=0; } }; /** * @brief Fast IO */ #line 3 "sol.cpp" #line 2 "library/DataStructure/disjointsparsetable.hpp" templatestruct DisjointSparseTable{ vector> buf; vector height; DisjointSparseTable(const vector& a){ int n=a.size(),LG=0; while((1<(n)); height.assign(1<>1]+1; rep(i,0,n)buf[0][i]=a[i]; rep(lg,1,LG){ int add=1<=j;k--)buf[lg][k]=f(a[k],buf[lg][k+1]); if(n<=pos)break; buf[lg][pos]=a[pos]; for(int k=pos+1;k=--R)return buf[0][L]; return f(buf[height[L^R]][L],buf[height[L^R]][R]); } }; /** * @brief Disjoint Sparse Table */ #line 2 "library/Math/fastdiv.hpp" struct FastDiv{ using u64=uint64_t; using u128=__uint128_t; constexpr FastDiv():m(),s(),x(){} constexpr FastDiv(int _m) :m(_m),s(__lg(m-1)),x(((u128(1)<<(s+64))+m-1)/m){} constexpr int get(){return m;} constexpr friend u64 operator/(u64 n,const FastDiv& d){ return (u128(n)*d.x>>d.s)>>64; } constexpr friend int operator%(u64 n,const FastDiv& d){ return n-n/d*d.m; } constexpr pair divmod(u64 n)const{ u64 q=n/(*this); return {q,n-q*m}; } int m,s; u64 x; }; /** * @brief Fast Division */ #line 3 "library/Math/dynamic.hpp" struct Fp{ using u64=uint64_t; int v; static int get_mod(){return _getmod();} static void set_mod(int _m){bar=FastDiv(_m);} Fp inv() const{ int tmp,a=v,b=get_mod(),x=1,y=0; while(b){ tmp=a/b,a-=tmp*b; swap(a,b); x-=tmp*y; swap(x,y); } if(x<0){x+=get_mod();} return x; } Fp():v(0){} Fp(ll x){ v=x%get_mod(); if(v<0)v+=get_mod(); } Fp operator-()const{return Fp()-*this;} Fp pow(ll t){ assert(t>=0); Fp res=1,b=*this; while(t){ if(t&1)res*=b; b*=b; t>>=1; } return res; } Fp& operator+=(const Fp& x){ v+=x.v; if(v>=get_mod())v-=get_mod(); return *this; } Fp& operator-=(const Fp& x){ v+=get_mod()-x.v; if(v>=get_mod())v-=get_mod(); return *this; } Fp& operator*=(const Fp& x){ v=(u64(v)*x.v)%bar; return *this; } Fp& operator/=(const Fp& x){ (*this)*=x.inv(); return *this; } Fp operator+(const Fp& x)const{return Fp(*this)+=x;} Fp operator-(const Fp& x)const{return Fp(*this)-=x;} Fp operator*(const Fp& x)const{return Fp(*this)*=x;} Fp operator/(const Fp& x)const{return Fp(*this)/=x;} bool operator==(const Fp& x)const{return v==x.v;} bool operator!=(const Fp& x)const{return v!=x.v;} private: static FastDiv bar; static int _getmod(){return bar.get();} }; FastDiv Fp::bar(998244353); /** * @brief Dynamic Modint */ #line 2 "library/Math/miller.hpp" struct m64 { using i64 = int64_t; using u64 = uint64_t; using u128 = __uint128_t; static u64 mod; static u64 r; static u64 n2; static u64 get_r() { u64 ret = mod; rep(_,0,5) ret *= 2 - mod * ret; return ret; } static void set_mod(u64 m) { assert(m < (1LL << 62)); assert((m & 1) == 1); mod = m; n2 = -u128(m) % m; r = get_r(); assert(r * mod == 1); } static u64 get_mod() { return mod; } u64 a; m64() : a(0) {} m64(const int64_t &b) : a(reduce((u128(b) + mod) * n2)){}; static u64 reduce(const u128 &b) { return (b + u128(u64(b) * u64(-r)) * mod) >> 64; } u64 get() const { u64 ret = reduce(a); return ret >= mod ? ret - mod : ret; } m64 &operator*=(const m64 &b) { a = reduce(u128(a) * b.a); return *this; } m64 operator*(const m64 &b) const { return m64(*this) *= b; } bool operator==(const m64 &b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); } bool operator!=(const m64 &b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); } m64 pow(u128 n) const { m64 ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } }; typename m64::u64 m64::mod, m64::r, m64::n2; bool Miller(ll n){ if(n<2 or (n&1)==0)return (n==2); m64::set_mod(n); ll d=n-1; while((d&1)==0)d>>=1; vector seeds; if(n<(1<<30))seeds={2, 7, 61}; else seeds={2, 325, 9375, 28178, 450775, 9780504}; for(auto& x:seeds){ if(n<=x)break; ll t=d; m64 y=m64(x).pow(t); while(t!=n-1 and y!=1 and y!=n-1){ y*=y; t<<=1; } if(y!=n-1 and (t&1)==0)return 0; } return 1; } /** * @brief Miller-Rabin */ #line 2 "library/Utility/random.hpp" namespace Random{ mt19937_64 randgen(chrono::steady_clock::now().time_since_epoch().count()); using u64=unsigned long long; u64 get(){ return randgen(); } templateT get(T L){ return get()%(L+1); } templateT get(T L,T R){ return get(R-L)+L; } double uniform(){ return double(get(1000000000))/1000000000; } string str(int n){ string ret; rep(i,0,n)ret+=get('a','z'); return ret; } templatevoid shuffle(Iter first,Iter last){ if(first==last)return; int len=1; for(auto it=first+1;it!=last;it++){ len++; int j=get(0,len-1); if(j!=len-1)iter_swap(it,first+j); } } templatevector select(int n,T L,T R){ set ret; while(ret.size(); vector pw; P f(P a, P b) { a.second += b.second * pw[a.first]; a.first += b.first; return a; } FastIO io; int main() { int n, q; ll K; io.read(n, q, K); int p = 1; while (!Miller(p)) { p = Random::get(101010101, 1010101010); } Fp::set_mod(p); pw.resize(n + 1, 1); rep(i, 0, n) pw[i + 1] = pw[i] * K; vector

buf(n); rep(i, 0, n) { int x; io.read(x); buf[i] = {1, x}; } DisjointSparseTable dst(buf); while (q--) { int L, R; io.read(L, R); L--; auto [_, x] = dst.query(L, R); io.write(x == 0 ? "No" : "Yes"); } return 0; }