//////////////////////////////////////////////////////////////////////////////// // Give me AC!!! // //////////////////////////////////////////////////////////////////////////////// #include #include #include #include #include #include #include using namespace std; namespace mp = boost::multiprecision; using namespace mp; using ull = __int128; using ll = long long; using cll = cpp_int; using ld = long double; using Graph = vector>; #define REP(i,n) for(ll i=0;i<(ll)(n);i++) #define REPD(i,n) for(ll i=n-1;i>=0;i--) #define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++) #define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--) //xにはvectorなどのコンテナ #define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい #define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく #define MAX(x) *max_element(ALL(x)) //最大値を求める #define MIN(x) *min_element(ALL(x)) //最小値を求める #define PQ priority_queue,vector>,greater>> #define PB push_back //vectorヘの挿入 #define MP make_pair //pairのコンストラクタ #define F first //pairの一つ目の要素 #define S second //pairの二つ目の要素 #define coutY cout<<"YES"< a(b) #define vl(a,b) vector a(b) #define vs(a,b) vector a(b) #define vll(a,b,c) vector> a(b, vector(c)); #define intque(a) queue a; #define llque(a) queue a; #define intque2(a) priority_queue, greater> a; #define llque2(a) priority_queue, greater> a; #define pushback(a,b) a.push_back(b) #define mapii(M1) map M1; #define cou(v,x) count(v.begin(), v.end(), x) #define mapll(M1) map M1; #define mapls(M1) map M1; #define mapsl(M1) map M1; #define twolook(a,l,r,x) lower_bound(a+l, a+r, x) - a #define sor(a) sort(a.begin(), a.end()) #define rever(a) reverse(a.begin(),a.end()) #define rep(i,a) for(ll i=0;i>n[i] #define vcout(n) for(ll i=0;i>n[i][j] const ll mod = 998244353; const ll MOD = 998244353; //const ll MOD = 1000000007; //const ll mod = 1000000007; constexpr ll MAX = 5000000; //const ll _max = 9223372036854775807; const ll _max = 1223372036854775807; const ll INF = 2000000000000000000; ll fac[MAX],finv[MAX],inv[MAX]; // テーブルを作る前処理 void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } // 二項係数計算 long long COM(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } int modPow(long long a, long long n, long long p) { if (n == 0) return 1; // 0乗にも対応する場合 if (n == 1) return a % p; if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p; long long t = modPow(a, n / 2, p); return (t * t) % p; } ll clocks(ll a,ll b,ll c){ return a*3600+b*60+c; } ll divup(ll b,ll d){ if(b%d==0){ return b/d; } else{ return b/d+1; } } struct Edge { int to; // 辺の行き先 int weight; // 辺の重み Edge(int t, int w) : to(t), weight(w) { } }; using Graphw = vector>; ll zero(ll a){ return max(ll(0),a); } template< typename T > struct FormalPowerSeries : vector< T > { using vector< T >::vector; using P = FormalPowerSeries; using MULT = function< P(P, P) >; static MULT &get_mult() { static MULT mult = nullptr; return mult; } static void set_fft(MULT f) { get_mult() = f; } void shrink() { while(this->size() && this->back() == T(0)) this->pop_back(); } P operator+(const P &r) const { return P(*this) += r; } P operator+(const T &v) const { return P(*this) += v; } P operator-(const P &r) const { return P(*this) -= r; } P operator-(const T &v) const { return P(*this) -= v; } P operator*(const P &r) const { return P(*this) *= r; } P operator*(const T &v) const { return P(*this) *= v; } P operator/(const P &r) const { return P(*this) /= r; } P operator%(const P &r) const { return P(*this) %= r; } P &operator+=(const P &r) { if(r.size() > this->size()) this->resize(r.size()); for(int i = 0; i < r.size(); i++) (*this)[i] += r[i]; return *this; } P &operator+=(const T &r) { if(this->empty()) this->resize(1); (*this)[0] += r; return *this; } P &operator-=(const P &r) { if(r.size() > this->size()) this->resize(r.size()); for(int i = 0; i < r.size(); i++) (*this)[i] -= r[i]; shrink(); return *this; } P &operator-=(const T &r) { if(this->empty()) this->resize(1); (*this)[0] -= r; shrink(); return *this; } P &operator*=(const T &v) { const int n = (int) this->size(); for(int k = 0; k < n; k++) (*this)[k] *= v; return *this; } P &operator*=(const P &r) { if(this->empty() || r.empty()) { this->clear(); return *this; } assert(get_mult() != nullptr); return *this = get_mult()(*this, r); } P &operator%=(const P &r) { return *this -= *this / r * r; } P operator-() const { P ret(this->size()); for(int i = 0; i < this->size(); i++) ret[i] = -(*this)[i]; return ret; } P &operator/=(const P &r) { if(this->size() < r.size()) { this->clear(); return *this; } int n = this->size() - r.size() + 1; return *this = (rev().pre(n) * r.rev().inv(n)).pre(n).rev(n); } P pre(int sz) const { return P(begin(*this), begin(*this) + min((int) this->size(), sz)); } P operator>>(int sz) const { if(this->size() <= sz) return {}; P ret(*this); ret.erase(ret.begin(), ret.begin() + sz); return ret; } P operator<<(int sz) const { P ret(*this); ret.insert(ret.begin(), sz, T(0)); return ret; } P rev(int deg = -1) const { P ret(*this); if(deg != -1) ret.resize(deg, T(0)); reverse(begin(ret), end(ret)); return ret; } P diff() const { const int n = (int) this->size(); P ret(max(0, n - 1)); for(int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * T(i); return ret; } P integral() const { const int n = (int) this->size(); P ret(n + 1); ret[0] = T(0); for(int i = 0; i < n; i++) ret[i + 1] = (*this)[i] / T(i + 1); return ret; } // F(0) must not be 0 P inv(int deg = -1) const { assert(((*this)[0]) != T(0)); const int n = (int) this->size(); if(deg == -1) deg = n; P ret({T(1) / (*this)[0]}); for(int i = 1; i < deg; i <<= 1) { ret = (ret + ret - ret * ret * pre(i << 1)).pre(i << 1); } return ret.pre(deg); } // F(0) must be 1 P log(int deg = -1) const { assert((*this)[0] == 1); const int n = (int) this->size(); if(deg == -1) deg = n; return (this->diff() * this->inv(deg)).pre(deg - 1).integral(); } P sqrt(int deg = -1) const { const int n = (int) this->size(); if(deg == -1) deg = n; if((*this)[0] == T(0)) { for(int i = 1; i < n; i++) { if((*this)[i] != T(0)) { if(i & 1) return {}; if(deg - i / 2 <= 0) break; auto ret = (*this >> i).sqrt(deg - i / 2) << (i / 2); if(ret.size() < deg) ret.resize(deg, T(0)); return ret; } } return P(deg, 0); } P ret({T(1)}); T inv2 = T(1) / T(2); for(int i = 1; i < deg; i <<= 1) { ret = (ret + pre(i << 1) * ret.inv(i << 1)) * inv2; } return ret.pre(deg); } // F(0) must be 0 P exp(int deg = -1) const { assert((*this)[0] == T(0)); const int n = (int) this->size(); if(deg == -1) deg = n; P ret({T(1)}); for(int i = 1; i < deg; i <<= 1) { ret = (ret * (pre(i << 1) + T(1) - ret.log(i << 1))).pre(i << 1); } return ret.pre(deg); } P pow(int64_t k, int deg = -1) const { const int n = (int) this->size(); if(deg == -1) deg = n; for(int i = 0; i < n; i++) { if((*this)[i] != T(0)) { T rev = T(1) / (*this)[i]; P C(*this * rev); P D(n - i); for(int j = i; j < n; j++) D[j - i] = C[j]; D = (D.log() * k).exp() * (*this)[i].pow(k); P E(deg); if(i * k > deg) return E; auto S = i * k; for(int j = 0; j + S < deg && j < D.size(); j++) E[j + S] = D[j]; return E; } } return *this; } T eval(T x) const { T r = 0, w = 1; for(auto &v : *this) { r += w * v; w *= x; } return r; } }; //aはbの何乗以下かを満たす数の内最大の物,(a,10)はaの桁数 ll expless(ll a,ll b){ ll k=0; ll o=1; while(a>=o){ k++; o=o*b; } return k; } //aをb進法で表す //b進法のaを10進法に直す ll tenbase(ll a,ll b){ ll c=expless(a,10); ll ans=0; ll k=1; for(int i=0;i > prime_factorize(long long N) { vector > res; for (long long a = 2; a * a <= N; ++a) { if (N % a != 0) continue; long long ex = 0; // 指数 // 割れる限り割り続ける while (N % a == 0) { ++ex; N /= a; } // その結果を push res.push_back({a, ex}); } // 最後に残った数について if (N != 1) res.push_back({N, 1}); return res; } ll atll(ll a,ll b){ b++; ll c=expless(a,10); ll d=c-b; ll f=1; for(int i=0;i vector smallest_prime_factors(T n) { vector spf(n + 1); for (int i = 0; i <= n; i++) spf[i] = i; for (T i = 2; i * i <= n; i++) { // 素数だったら if (spf[i] == i) { for (T j = i * i; j <= n; j += i) { // iを持つ整数かつまだ素数が決まっていないなら if (spf[j] == j) { spf[j] = i; } } } } return spf; } vector> factolization(ll x, vector &spf) { vector> ret; ll p; ll z; while (x != 1) { p=(spf[x]); z=0; while(x%p==0){ z++; x /= p; } ret.push_back({p, z}); } return ret; } vector is; vector prime_(ll n){ is.resize(n+1, true); is[0] = false; is[1] = false; vector primes; for (int i=2; i<=n; i++) { if (is[i] == true){ primes.push_back(i); for (int j=i*2; j<=n; j+=i){ is[j] = false; } } } return primes; } vector dijkstra(ll f,ll n,vector>>& edge){ //最短経路としてどの頂点が確定済みかをチェックする配列 vector confirm(n,false); //それぞれの頂点への最短距離を保存する配列 //始点は0,始点以外はINFで最短距離を初期化する vector mincost(n,INF);mincost[f]=0; //確定済みの頂点の集合から伸びる辺を伝ってたどり着く頂点の始点からの距離を短い順に保存するPriority queue PQ mincand;mincand.push({mincost[f],f}); //mincandの要素がゼロの時、最短距離を更新できる頂点がないことを示す while(!mincand.empty()){ //最短距離でたどり着くと思われる頂点を取り出す vector next=mincand.top();mincand.pop(); //すでにその頂点への最短距離が確定済みの場合は飛ばす if(confirm[next[1]]) continue; //確定済みではない場合は確定済みにする confirm[next[1]]=true; //その確定済みの頂点から伸びる辺の情報をとってくる(参照の方が速い)、lは辺の本数 vector>& v=edge[next[1]];ll l=SIZE(v); REP(i,l){ //辺の先が確定済みなら更新する必要がない((✳︎2)があれば十分なので(✳︎1)は実はいらない) if(confirm[v[i][0]]) continue; //(✳︎1) //辺の先のmincost以上の場合は更新する必要がない(辺の先が確定済みの時は満たす) if(mincost[v[i][0]]<=next[0]+v[i][1]) continue; //(✳︎2) //更新 mincost[v[i][0]]=next[0]+v[i][1]; //更新した場合はその頂点が(確定済みでない頂点の中で)最短距離になる可能性があるのでmincandに挿入 mincand.push({mincost[v[i][0]],v[i][0]}); } } return mincost; } ll so(ll a){ ll ans=0; if(a==0){ return 0; } while(a%2==0){ a/=2; ans++; } return ans; } ll HOM(ll n,ll r){ return COM(n+r-1,r); } ll binary(ll bina){ ll ans = 0; for (ll i = 0; bina>0 ; i++) { ans = ans+(bina%2)*pow(10,i); bina = bina/2; } return ans; } class UnionFind { public: vector parent; //parent[i]はiの親 vector siz; //素集合のサイズを表す配列(1で初期化) map> group;//素集合ごとに管理する連想配列(keyはそれぞれの素集合の親、valueはその素集合の要素の配列) //コンストラクタ UnionFind(ll n):parent(n),siz(n,1){ //全ての要素の根が自身であるとして初期化 for(ll i=0;i enum_divisors(long long N) { vector res; for (long long i = 1; i * i <= N; ++i) { if (N % i == 0) { res.push_back(i); // 重複しないならば i の相方である N/i も push if (N/i != i) res.push_back(N/i); } } // 小さい順に並び替える sort(res.begin(), res.end()); return res; } vector zaatu(vector a,ll n){ map mp; for (int i = 0; i < n; i++) { cin >> a[i]; mp[a[i]] = 0; } // 小さい値から順に番号を付けていく ll num = 0; for (auto x : mp) { mp[x.first] = num; num++; } vector ans; for(int i=0;i t,ll key){ auto iter = lower_bound(ALL(t), key); auto iter2 = upper_bound(ALL(t), key); if((iter-t.begin())!=(iter2-t.begin())){ return 1; } else{ return 0; } } ll mygcd(ll x, ll y) { if(x n){ if(int(n.size())==0){ return 0; } ll ans=0; ll tmp=0; ll tmp2=0; ll tmp3=0; ll tmp4=0; ll t=1; for(int i=0;i=0;j--){ if(n.at(j)==2||n.at(j)==-2){ break; } if(t*n.at(j)==1){ tmp+=modPow(2,j-1,mod); tmp%=mod; } else{ tmp2+=modPow(2,j-1,mod); tmp2%=mod; } t=t*n.at(j); } for(int j=i+1;j>n; vector a(n); vcin(a); vector tmp; vector q; ll o=0; ll s=0; ll l=0; for(int i=0;i