Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Author : Naveen
- // Program Start
- // Libraries and Namespace Start
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- // Libraries and Namespace End
- //------------------------------------------------------------------------------------------
- // Important Shortcuts Start
- // Macros Start
- #define F first
- #define S second
- #define pb push_back
- #define yes cout << "yes\n"
- #define no cout << "no\n"
- #define Yes cout << "Yes\n"
- #define No cout << "No\n"
- #define YES cout << "YES\n"
- #define NO cout << "NO\n"
- #define fri(i, s, e) for (ll i = s; i < e; ++i)
- #define frd(i, e, s) for(ll i = e; i > s; --i)
- #define all(v) v.begin(), v.end()
- // Macros End
- // Custom Hash Function Start
- struct custom_hash {
- static uint64_t splitMix64(uint64_t x) {
- x += 0x9e3779b97f4a7c15;
- x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
- x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
- return x ^ (x >> 31);
- }
- size_t operator()(uint64_t x) const {
- static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
- return splitMix64(x + FIXED_RANDOM);
- }
- };
- // Custom Hash Function End
- // Declarations Start
- typedef bool bl;
- typedef long long int ll;
- typedef unsigned long long int ull;
- typedef long double ld;
- typedef string str;
- typedef pair<ll, ll> prll;
- typedef tuple<ll, ll, ll> tupll;
- typedef stack<ll> stkll;
- typedef queue<ll> quell;
- typedef vector<bl> vecbl;
- typedef vector<ll> vecll;
- typedef vector<prll> vecprll;
- typedef vector<tupll> vectupll;
- typedef vector<ld> vecld;
- typedef set<ll> setll;
- typedef multiset<ll> mltsetll;
- typedef map<ll, ll> mapll;
- typedef multimap<ll, ll> mltmapll;
- // Declarations End
- // Using Declarations Start
- template <typename T>
- using unord_set = unordered_set<T, custom_hash>;
- typedef unord_set<ll> unsetll;
- template <typename T>
- using unord_multiset = unordered_multiset<T, custom_hash>;
- typedef unord_multiset<ll> unmltsetll;
- template <typename T1, typename T2>
- using unord_map = unordered_map<T1, T2, custom_hash>;
- typedef unord_map<ll, ll> unmapll;
- template <typename T1, typename T2>
- using unord_multimap = unordered_multimap<T1, T2, custom_hash>;
- typedef unord_multimap<ll, ll> unmltmapll;
- template <typename T, typename Compare = greater<T>>
- using heap = priority_queue<T, vector<T>, Compare>;
- typedef heap<ll> minheapll;
- typedef heap<prll> minheapprll;
- typedef heap<ll, less<ll>> maxheapll;
- typedef heap<prll, less<prll>> maxheapprll;
- template <typename T, typename Compare = less<T>>
- using pbds_tree = tree<T, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;
- typedef pbds_tree<ll> pbdssetll;
- typedef pbds_tree<ll, less_equal<ll>> pbdsmltsetll;
- typedef pbds_tree<prll> pbdsmapll;
- typedef pbds_tree<prll, less_equal<prll>> pbdsmltmapll;
- // Using Declarations End
- // Important Shortcuts End
- //------------------------------------------------------------------------------------------
- // Important Functions Start
- // Constants Start
- const ll inf = 9223372036854775807ll;
- const ll neg_inf = -9223372036854775807ll - 1ll;
- const ll mod1 = 1000000007ll;
- const ll mod2 = 998244353ll;
- const ll max_if = 200000ll;
- const ll one = 1ll;
- const ll zero = 0ll;
- const str spc = " ";
- const str emp = "";
- const str newl = "\n";
- // Constants End
- // Input and Output Functions Start
- template <class U, class T>
- U& operator>>(U& is, vector<T>& a) {
- for (T& x : a) {
- is >> x;
- }
- return is;
- }
- template <class U, class T>
- U& operator<<(U& os, vector<T>& a) {
- for (ll i = 0;i < a.size();++i) {
- os << a[i] << (i != a.size() - 1 ? spc : emp);
- }
- return os;
- }
- inline void yn(const bool con) {
- cout << (con ? "yes" : "no") << '\n';
- }
- inline void Yn(const bool con) {
- cout << (con ? "Yes" : "No") << '\n';
- }
- inline void YN(const bool con) {
- cout << (con ? "YES" : "NO") << '\n';
- }
- // Input and Output Functions End
- // Debug Functions Start
- template<class T>
- void debug(const T v) {
- cerr << v;
- }
- template <class T, class V>
- void debug(const pair<T, V>& p) {
- cerr << "(" << p.first << ", " << p.second << ")";
- }
- template <size_t Index, typename... lls>
- typename enable_if<Index == sizeof...(lls)>::type
- print_tuple(ostream& os, const tuple<lls...>&) {}
- template <size_t Index, typename... lls>
- typename enable_if < Index<sizeof...(lls)>::type
- print_tuple(ostream& os, const tuple<lls...>& t) {
- os << get<Index>(t);
- if (Index + 1 < sizeof...(lls)) os << ", ";
- print_tuple<Index + 1>(os, t);
- }
- template <typename... lls>
- void debug(const tuple<lls...>& t) {
- cerr << "(";
- print_tuple<0>(cerr, t);
- cerr << ")";
- }
- template <class T>
- void debug(const vector<T>& vec) {
- size_t c = 0;
- const size_t n = vec.size();
- cerr << "[";
- for (T i : vec) {
- debug(i);
- cerr << (++c < n ? ", " : "");
- }
- cerr << "]\n";
- }
- template <class T>
- void debug(const set<T>& set_v) {
- size_t c = 0;
- const size_t n = set_v.size();
- cerr << "{";
- for (T i : set_v) {
- debug(i);
- cerr << (++c < n ? ", " : "");
- }
- cerr << "}";
- }
- template <class T>
- void debug(const unordered_set<T>& set_v) {
- size_t c = 0;
- const size_t n = set_v.size();
- cerr << "{";
- for (T i : set_v) {
- debug(i);
- cerr << (++c < n ? ", " : "");
- }
- cerr << "}";
- }
- template <class T>
- void debug(const multiset<T>& set_v) {
- size_t c = 0;
- const size_t n = set_v.size();
- cerr << "{";
- for (T i : set_v) {
- debug(i);
- cerr << (++c < n ? ", " : "");
- }
- cerr << "}";
- }
- template <class T>
- void debug(const unordered_multiset<T>& set_v) {
- size_t c = 0;
- const size_t n = set_v.size();
- cerr << "{";
- for (T i : set_v) {
- debug(i);
- cerr << (++c < n ? ", " : "");
- }
- cerr << "}";
- }
- template <typename T, typename Compare = less<T>>
- void debug(const pbds_tree<T, Compare>& set_v) {
- size_t c = 0;
- const size_t n = set_v.size();
- cerr << "{";
- for (T i : set_v) {
- debug(i);
- cerr << (++c < n ? ", " : "");
- }
- cerr << "}";
- }
- template <class T, class V>
- void debug(const map<T, V>& dict) {
- size_t c = 0;
- const size_t n = dict.size();
- cerr << "{";
- for (auto it : dict) {
- debug(it.first);
- cerr << ": ";
- debug(it.second);
- cerr << (++c < n ? ", " : "");
- }
- cerr << "}";
- }
- template <class T, class V>
- void debug(const multimap<T, V>& dict) {
- size_t c = 0;
- const size_t n = dict.size();
- cerr << "{";
- for (auto it : dict) {
- debug(it.first);
- cerr << ": ";
- debug(it.second);
- cerr << (++c < n ? ", " : "");
- }
- cerr << "}";
- }
- template <class T, class V>
- void debug(const unordered_map<T, V>& dict) {
- size_t c = 0;
- const size_t n = dict.size();
- cerr << "{";
- for (auto it : dict) {
- debug(it.first);
- cerr << ": ";
- debug(it.second);
- cerr << (++c < n ? ", " : "");
- }
- cerr << "}";
- }
- template <class T, class V>
- void debug(const unordered_multimap<T, V>& dict) {
- size_t c = 0;
- const size_t n = dict.size();
- cerr << "{";
- for (auto it : dict) {
- debug(it.first);
- cerr << ": ";
- debug(it.second);
- cerr << (++c < n ? ", " : "");
- }
- cerr << "}";
- }
- template <typename T, typename... Args>
- void debug(const T& v, const Args&... args) {
- debug(v);
- debug(args...);
- }
- // Debug Functions End
- // Important Functions End
- //------------------------------------------------------------------------------------------
- // Basic Functions Start
- // String Operator Overload Start
- template <class T>
- str operator*(const str& s, const T& n) {
- str res;
- res.reserve(s.size() * n);
- for (ll i = 0; i < n; ++i) res += s;
- return res;
- }
- // String Operator Overload End
- //Binary Search Start
- template <typename T>
- inline ll bin_search(const vector<T>& v, T x) {
- auto it = lower_bound(v.begin(), v.end(), x);
- if (it != v.end() && *it == x) return distance(v.begin(), it);
- return -1;
- }
- // Binary Search End
- // Min Function Start
- template <class T>
- inline T min(const vector<T>& vec) {
- assert(vec.size() >= 1 && "Cannot find minimum of an empty vector.");
- return *min_element(vec.begin(), vec.end());
- }
- // Min Function End
- // Max Function Start
- template <class T>
- inline T max(const vector<T>& vec) {
- assert(vec.size() >= 1 && "Cannot find minimum of an empty vector.");
- return *max_element(vec.begin(), vec.end());
- }
- // Max Function End
- // Sum Function Start
- template <class T>
- inline T sum(T v) {
- return v;
- }
- template <class T>
- inline T sum(T v1, T v2) {
- return v1 + v2;
- }
- template <class T>
- T sum(const initializer_list<T>& ilist) {
- T sumi = T();
- for (const T& val : ilist) sumi += val;
- return sumi;
- }
- template <class T>
- T sum(const vector<T>& vec) {
- T sumi = T();
- for (auto i : vec) sumi += sum(i);
- return sumi;
- }
- template <class T>
- T sum(const set<T>& seti) {
- T sumi = T();
- for (auto i : seti) sumi += sum(i);
- return sumi;
- }
- template <class T>
- T sum(const multiset<T>& seti) {
- T sumi = T();
- for (auto i : seti) sumi += sum(i);
- return sumi;
- }
- template <typename T, typename Compare = less<T>>
- T sum(const pbds_tree<T, Compare>& seti) {
- T sumi = T();
- for (auto i : seti) sumi += sum(i);
- return sumi;
- }
- // Sum Function End
- // Binary Start
- template <class T>
- str bin(const T& dn) {
- str bin_str = bitset<64>(dn).to_string();
- ll firstOne = bin_str.find('1');
- if (firstOne != str::npos) {
- bin_str = bin_str.substr(firstOne);
- return bin_str;
- }
- return "0";
- }
- ll int2(const str& bin_str) {
- bitset<64> bits(bin_str);
- ll dn = static_cast<ll>(bits.to_ulong());
- return dn;
- }
- // Binary End
- // Square Root Start
- inline ll sqrt_int(ll n) {
- assert(n >= 0 && "The number can't be negative.");
- return static_cast<ll>(sqrt(n));
- }
- ll sqrt_int_u(ll n) {
- assert(n >= 0 && "The number can't be negative.");
- ll k = sqrt(n);
- return k * k == n ? k : k + 1;
- }
- // Square Root End
- // Map Computation Start
- template <class T>
- void map_com(map<T, ll>& ma, const vector<T>& vec) {
- for (T i : vec) ma[i]++;
- }
- // Map Computation End
- // Basic Functions End
- //------------------------------------------------------------------------------------------
- // Algorithms Start
- // Power Function Start
- ll power(ll a, ll b, const ll mod = mod1) {
- assert(b >= 0 && "Power cannot be negative.");
- ll ans = 1;
- a %= mod;
- while (b) {
- if (b & 1) ans = (ans * a) % mod;
- a = (a * a) % mod;
- b >>= 1;
- }
- return ans;
- }
- // Power Function End
- // Modular Inverse Start
- inline ll mod_inv(ll a, const ll mod = mod1) {
- assert(a >= 0 && "The number must be non-negative.");
- return power(a, mod - 2, mod);
- }
- // Modular Inverse End
- // Fast Fib Start
- ll fast_fib(ll n, const ll mod = mod1, const bl is_mod = true) {
- assert(n >= 0 && "The numbers can't be negative.");
- ll a0 = 0, a1 = 1, f2, f21, t;
- for (ll i = 61; i >= 0; --i) {
- f2 = a0 * (2 * a1 - a0);
- f21 = a0 * a0 + a1 * a1;
- if (is_mod) {
- f2 %= mod;
- f21 %= mod;
- }
- if (n & (one << i)) {
- a0 = f21;
- a1 = f2 + f21;
- if (is_mod) a1 %= mod;
- }
- else {
- a0 = f2;
- a1 = f21;
- }
- }
- return is_mod ? a0 % mod : a0;
- }
- // Fast Fib End
- // KMP Algorithm Start
- ll substr_is_in(const str& text, const str& pattern) {
- const size_t m = pattern.size();
- const size_t n = text.size();
- vecll lps(m, 0);
- ll len = 0, i = 1, j;
- while (i < m) {
- if (pattern[i] == pattern[len]) lps[i++] = ++len;
- else {
- if (len != 0) len = lps[len - 1];
- else lps[i++] = 0;
- }
- }
- i = 0, j = 0;
- while (i < n) {
- if (pattern[j] == text[i]) {
- ++i;
- ++j;
- }
- if (j == m) return i - j;
- else if (i < n && pattern[j] != text[i]) {
- if (j != 0) j = lps[j - 1];
- else ++i;
- }
- }
- return -1;
- }
- // KMP Algorithm End
- // Algorithms End
- //------------------------------------------------------------------------------------------
- // Classes Start
- // Big Int Start
- namespace fft {
- const ll mod = -1;
- class cpx {
- public:
- double r, i;
- cpx(double _r = 0, double _i = 0) : r(_r), i(_i) {}
- cpx operator+(cpx b) { return { r + b.r, i + b.i }; }
- cpx operator-(cpx b) { return { r - b.r, i - b.i }; }
- cpx operator*(cpx b) { return { r * b.r - i * b.i, r * b.i + i * b.r }; }
- cpx operator/(double b) { return { r / b, i / b }; }
- inline cpx conj() { return { r, -i }; }
- };
- const double PI = acos(-1);
- vector<ll> rev(1, 0);
- vector<cpx> roots;
- ll base = 0;
- void precompute(ll nbase) {
- if (nbase <= base)
- return;
- rev.resize(1 << nbase);
- for (ll i = 0; i < (1 << nbase); ++i) {
- rev[i] = rev[i >> 1] >> 1 | ((i & 1) << (nbase - 1));
- }
- roots.resize(1 << nbase);
- for (; base < nbase; ++base) {
- ll len = 1 << base;
- double angle = 2 * PI / (1 << (base + 1));
- for (ll i = 0; i < len; ++i) {
- double cur = angle * i;
- roots[len + i] = cpx(cos(cur), sin(cur));
- }
- }
- }
- void fft(vector<cpx>& a, ll n = -1) {
- if (n == -1)
- n = a.size();
- assert((n & (n - 1)) == 0);
- ll zeros = __builtin_ctz(n);
- precompute(zeros);
- ll shift = base - zeros;
- for (ll i = 0; i < n; ++i) {
- if (i < (rev[i] >> shift))
- swap(a[i], a[rev[i] >> shift]);
- }
- for (ll len = 1; len < n; len <<= 1)
- for (ll i = 0; i < n; i += 2 * len)
- for (ll j = 0; j < len; ++j) {
- cpx u = a[i + j], v = a[i + j + len] * roots[len + j];
- a[i + j] = u + v;
- a[i + j + len] = u - v;
- }
- }
- vector<cpx> fa, fb;
- vector<ll> multiply(const vector<ll>& a, const vector<ll>& b) {
- if (a.empty() || b.empty()) return {};
- ll sz = a.size() + b.size() - 1;
- ll n = sz == 1 ? 1 : 1 << (32 - __builtin_clz(sz - 1));
- if (n > fa.size()) fa.resize(n);
- for (ll i = 0; i < n; ++i) {
- ll x = i < a.size() ? a[i] : 0;
- ll y = i < b.size() ? b[i] : 0;
- fa[i] = cpx(x, y);
- }
- fft(fa, n);
- cpx r(0, -0.5 / n);
- for (ll i = 0; i <= (n >> 1); ++i) {
- ll j = (n - i) & (n - 1);
- cpx x = (fa[i] + fa[j].conj()) / 2;
- cpx y = (fa[i] - fa[j].conj()) * r;
- fa[i] = x * y;
- if (i != j) fa[j] = fa[i].conj();
- }
- fft(fa, n);
- reverse(fa.begin() + 1, fa.begin() + n);
- vector<ll> res(sz);
- for (ll i = 0; i < sz; ++i) res[i] = llround(fa[i].r);
- return res;
- }
- }
- const ll BASE = 1000;
- const ll BASE_DIGITS = log10(BASE);
- class BigInt {
- private:
- bool neg = false;
- vecll num;
- public:
- BigInt() {}
- BigInt(const string& s) {
- ll st = 0;
- if (s[0] == '-') {
- neg = true;
- st = 1;
- }
- for (ll i = (ll)s.size() - 1; i >= st; i -= BASE_DIGITS) {
- ll x = 0;
- for (ll j = max(st, i - BASE_DIGITS + 1); j <= i; ++j) x = x * 10 + s[j] - '0';
- num.push_back(x);
- }
- trim();
- }
- BigInt(ll m) {
- if (m < 0) neg = true;
- while (m) {
- num.push_back(abs(m % BASE));
- m /= BASE;
- }
- }
- void trim() {
- while (!num.empty() && !num.back()) num.pop_back();
- if (num.empty()) neg = false;
- }
- bool operator<(const BigInt& v) const {
- if (neg != v.neg) return neg > v.neg;
- if (num.size() != v.num.size()) return neg ? num.size() > v.num.size() : num.size() < v.num.size();
- for (ll i = (ll)num.size() - 1; i >= 0; --i)
- if (num[i] != v.num[i]) return neg ? num[i] > v.num[i] : num[i] < v.num[i];
- return false;
- }
- bool operator>(const BigInt& v) const { return v < *this; }
- bool operator<=(const BigInt& v) const { return !(v < *this); }
- bool operator>=(const BigInt& v) const { return !(*this < v); }
- bool operator==(const BigInt& v) const { return num == v.num && neg == v.neg; }
- bool operator!=(const BigInt& v) const { return !(*this == v); }
- BigInt operator-() const {
- BigInt ret(*this);
- if (!ret.num.empty()) ret.neg = !ret.neg;
- return ret;
- }
- BigInt& operator+=(const BigInt& x) {
- if (neg && !x.neg) return *this = x - (-*this);
- if (!neg && x.neg) return *this -= -x;
- assert(neg == x.neg);
- ll maxs = max(num.size(), x.num.size());
- num.resize(maxs);
- ll carry = 0;
- for (ll i = 0; i < maxs; ++i) {
- ll other = i >= x.num.size() ? 0 : x.num[i];
- num[i] += other + carry;
- carry = num[i] / BASE;
- num[i] %= BASE;
- }
- if (carry) num.push_back(carry);
- return *this;
- }
- BigInt& subtract(const BigInt& x) {
- assert(!neg && !x.neg);
- ll carry = 0;
- for (ll i = 0; i < num.size(); ++i) {
- ll other = i >= x.num.size() ? 0 : x.num[i];
- num[i] -= other + carry;
- carry = num[i] < 0;
- if (carry) num[i] += BASE;
- }
- trim();
- return *this;
- }
- BigInt& operator-=(const BigInt& x) {
- if (neg && !x.neg) return *this = -(-*this + x);
- if (x.neg) return *this += -x;
- assert(!neg && !x.neg);
- if (*this < x) {
- BigInt y = *this;
- *this = x;
- return *this = -subtract(y);
- }
- return subtract(x);
- }
- BigInt& operator*=(ll m) {
- const ll MX = LLONG_MAX / BASE;
- if (m < -MX || m > MX) return *this *= BigInt(m);
- neg ^= m < 0;
- m = abs(m);
- ll carry = 0;
- for (ll i = 0; i < num.size(); ++i) {
- ll v = num[i] * m + carry;
- carry = v / BASE;
- num[i] = v % BASE;
- }
- while (carry) {
- num.push_back(carry % BASE);
- carry /= BASE;
- }
- trim();
- return *this;
- }
- BigInt& operator*=(const BigInt& x) {
- if (num.empty()) return *this;
- neg ^= x.neg;
- auto c = fft::multiply(num, x.num);
- num.resize(c.size());
- ll carry = 0;
- for (ll i = 0; i < c.size(); ++i) {
- c[i] += carry;
- carry = c[i] / BASE;
- num[i] = c[i] % BASE;
- }
- if (carry) num.push_back(carry);
- trim();
- return *this;
- }
- ll divide_and_remainder(ll d) {
- assert(d != 0);
- const ll MX = LLONG_MAX / BASE;
- if (d < -MX || d > MX) return static_cast<ll>(divide_and_remainder(BigInt(d)));
- bool wasNeg = neg;
- neg ^= d < 0;
- d = abs(d);
- ll cur = 0;
- vector<ll> ret(num.size());
- for (ll i = (ll)num.size() - 1; i >= 0; --i) {
- cur *= BASE;
- cur += num[i];
- ret[i] = cur / d;
- cur %= d;
- }
- swap(num, ret);
- trim();
- return wasNeg ? -cur : cur;
- }
- BigInt& operator/=(ll v) {
- divide_and_remainder(v);
- return *this;
- }
- BigInt& operator%=(ll v) {
- ll remainder = divide_and_remainder(v);
- return *this = BigInt(remainder);
- }
- BigInt divide_and_remainder(BigInt b) {
- assert(!b.num.empty());
- bool wasNeg = neg;
- neg ^= b.neg;
- b.neg = false;
- BigInt cur;
- vector<ll> ret(num.size());
- for (ll i = (ll)num.size() - 1; i >= 0; --i) {
- cur *= BASE;
- cur += num[i];
- ll lo = 0, hi = BASE - 1;
- while (lo < hi) {
- ll d = (lo + hi + 1) >> 1;
- if (b * d > cur) hi = d - 1;
- else lo = d;
- }
- cur -= b * lo;
- ret[i] = lo;
- }
- swap(num, ret);
- trim();
- if (wasNeg && !cur.num.empty()) cur.neg = true;
- return cur;
- }
- BigInt& operator/=(const BigInt& x) {
- divide_and_remainder(x);
- return *this;
- }
- BigInt& operator%=(const BigInt& x) { return *this = divide_and_remainder(x); }
- BigInt& operator++() { return *this += 1; }
- BigInt& operator--() { return *this -= 1; }
- BigInt operator++(int) {
- BigInt ret(*this);
- *this += 1;
- return ret;
- }
- BigInt operator--(int) {
- BigInt ret(*this);
- *this -= 1;
- return ret;
- }
- friend BigInt operator+(BigInt a, const BigInt& b) { return a += b; }
- friend BigInt operator-(BigInt a, const BigInt& b) { return a -= b; }
- friend BigInt operator*(ll a, BigInt b) { return b *= a; }
- friend BigInt operator*(BigInt a, ll b) { return a *= b; }
- friend BigInt operator*(BigInt a, const BigInt& b) { return a *= b; }
- friend BigInt operator/(BigInt a, ll b) { return a /= b; }
- friend BigInt operator/(BigInt a, const BigInt& b) { return a /= b; }
- friend BigInt operator%(BigInt a, ll b) { return a %= b; }
- friend BigInt operator%(BigInt a, const BigInt& b) { return a %= b; }
- explicit operator ll() const {
- const unsigned long long MAX_ABS = LLONG_MAX + (unsigned ll)neg;
- const unsigned long long MX = MAX_ABS / BASE;
- unsigned long long ret = 0;
- for (ll i = (ll)num.size() - 1; i >= 0; --i) {
- if (ret > MX) throw;
- ret *= BASE;
- if (ret > MAX_ABS - num[i]) throw;
- ret += num[i];
- }
- assert(ret <= MAX_ABS);
- return neg ? -ret : ret;
- }
- str operator()() const {
- if (num.empty()) return "0";
- str ret;
- if (neg) ret += '-';
- ret += to_string(num.back());
- str fmt = "%0" + to_string(BASE_DIGITS) + "d";
- for (ll i = (ll)num.size() - 2; i >= 0; --i) {
- char buf[BASE_DIGITS + 1];
- sprintf(buf, fmt.c_str(), num[i]);
- ret += buf;
- }
- return ret;
- }
- friend BigInt gcd(const BigInt& a, ll b) {
- if (!b) return abs(a);
- ll r = static_cast<ll>(abs(a % b));
- if (r == 0) return abs(BigInt(b));
- return __gcd(r, abs(b % r));
- }
- friend BigInt gcd(ll a, const BigInt& b) { return gcd(b, a); }
- friend BigInt gcd(BigInt a, BigInt b) {
- a.neg = b.neg = false;
- while (!b.num.empty()) {
- BigInt c(b);
- b = a % b;
- swap(a, c);
- }
- return a;
- }
- friend BigInt rand_big_ll(BigInt n) {
- static mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
- assert(!n.num.empty() && !n.neg);
- n--;
- for (;;) {
- BigInt res;
- res.num.resize(n.num.size());
- for (ll i = (ll)n.num.size() - 1; i >= 0; --i) {
- ll mx = (i + 1 == n.num.size()) ? n.num[i] : BASE - 1;
- res.num[i] = rng() % (mx + 1);
- }
- res.trim();
- if (res <= n) return res;
- }
- assert(false);
- }
- friend BigInt abs(BigInt x) {
- x.neg = false;
- return x;
- }
- template <class U>
- friend U& operator<<(U& os, const BigInt& x) {
- os << x();
- return os;
- }
- template <class U>
- friend U& operator>>(U& is, BigInt& x) {
- str s;
- is >> s;
- x = s;
- return is;
- }
- };
- BigInt operator""_b(const char* str) {
- BigInt temp(str);
- return temp;
- }
- typedef BigInt bll;
- // Big Int end
- // Modular Start
- class Modular {
- private:
- ll value;
- const ll mod;
- inline void normalize(ll& val) {
- if (val >= mod && val <= -mod) val %= mod;
- if (val < 0) val += mod;
- }
- public:
- Modular(ll x = 0, ll m = mod1) : mod(m) {
- normalize(x);
- value = x;
- }
- Modular(const Modular& other) : value(other.value), mod(other.mod) {}
- Modular& operator=(const Modular& other) {
- assert(mod == other.mod && "The mod values have to be the same.");
- if (this != &other) value = other.value;
- return *this;
- }
- Modular& operator=(ll val) {
- normalize(val);
- value = val;
- return *this;
- }
- ll operator()() const {
- return value;
- }
- operator ll() const {
- return value;
- }
- Modular& operator+=(ll val) {
- normalize(val);
- value = (value + val) % mod;
- return *this;
- }
- Modular& operator-=(ll val) {
- normalize(val);
- value = (value - val + mod) % mod;
- return *this;
- }
- Modular& operator*=(ll val) {
- normalize(val);
- value = (value * val) % mod;
- return *this;
- }
- Modular pow(ll p) {
- return Modular(power(this->value, p, this->mod), this->mod);
- }
- Modular mod_in() {
- return Modular(mod_inv(this->value, this->mod), this->mod);
- }
- Modular& operator/=(ll val) {
- value = (value * mod_inv(val, mod)) % mod;
- return *this;
- }
- Modular& operator<<=(ll val) {
- value = (value * power(2, val, mod)) % mod;
- return *this;
- }
- Modular& operator>>=(ll val) {
- value = (value * mod_inv(power(2, val, mod), mod)) % mod;
- return *this;
- }
- Modular& operator++() {
- if (++value >= mod) value -= mod;
- return *this;
- }
- Modular& operator--() {
- if (--value < 0) value += mod;
- return *this;
- }
- Modular operator++(int) {
- Modular ret(*this);
- if (++value >= mod) value -= mod;
- return ret;
- }
- Modular operator--(int) {
- Modular ret(*this);
- if (--value < 0) value += mod;
- return ret;
- }
- Modular operator-() const {
- return Modular(mod - value, mod);
- }
- Modular operator+(ll val) {
- return Modular(*this) += val;
- }
- Modular operator-(ll val) {
- return Modular(*this) -= val;
- }
- Modular operator*(ll val) {
- return Modular(*this) *= val;
- }
- Modular operator/(ll val) {
- return Modular(*this) /= val;
- }
- Modular operator<<(ll val) {
- return Modular(*this) <<= val;
- }
- Modular operator>>(ll val) {
- return Modular(*this) >>= val;
- }
- template <class U>
- friend U& operator<<(U& os, const Modular& num) {
- return os << num.value;
- }
- template <class U>
- friend U& operator>>(U& is, Modular& num) {
- ll x;
- is >> x;
- num.value = (x % num.mod + num.mod) % num.mod;
- return is;
- }
- friend bool operator<(const Modular& lhs, const Modular& rhs) {
- return lhs.value < rhs.value;
- }
- friend bool operator>(const Modular& lhs, const Modular& rhs) {
- return lhs.value > rhs.value;
- }
- friend bool operator<=(const Modular& lhs, const Modular& rhs) {
- return lhs.value <= rhs.value;
- }
- friend bool operator>=(const Modular& lhs, const Modular& rhs) {
- return lhs.value >= rhs.value;
- }
- friend bool operator==(const Modular& lhs, const Modular& rhs) {
- return lhs.value == rhs.value;
- }
- friend bool operator!=(const Modular& lhs, const Modular& rhs) {
- return lhs.value != rhs.value;
- }
- };
- Modular operator""_m(const char* str) {
- Modular temp(stoll(str), mod1);
- return temp;
- }
- Modular operator""_m2(const char* str) {
- Modular temp(stoll(str), mod2);
- return temp;
- }
- typedef Modular mll;
- typedef vector<mll> vecmll;
- // Modular End
- // PNC Start
- class PNC {
- public:
- const ll size, mod;
- vecll fact, invfact;
- PNC(const ll len = max_if, const ll m = mod1) : size(len), mod(m), fact(size + 1, 1), invfact(size + 1, 0) {
- invfact[0] = mod_inv(fact[0], mod);
- for (ll i = 1; i <= size; ++i) {
- fact[i] = (fact[i - 1] * i) % mod;
- invfact[i] = mod_inv(fact[i], mod);
- }
- }
- ll facto(ll n) {
- assert(n >= 0 && "The number can't be negative.");
- if (n <= size) return fact[n];
- ll ans = 1;
- for (ll i = 1; i <= n; ++i) ans = (ans * i) % mod;
- return ans;
- }
- ll perm(ll n, ll r) {
- assert(n >= 0 && r >= 0 && "The number can't be negative.");
- if (n < r) return 0;
- if (n <= size) return (fact[n] * invfact[n - r]) % mod;
- ll ans = 1;
- for (ll i = n - r + 1; i <= n; ++i) ans = (ans * i) % mod;
- return ans;
- }
- ll comb(ll n, ll r) {
- assert(n >= 0 && r >= 0 && "The number can't be negative.");
- if (n < r) return 0;
- if (n <= size) return (fact[n] * (invfact[n - r] * invfact[r] % mod)) % mod;
- ll num = 1, den = 1;
- if (r > n / 2) r = n - r;
- ++n;
- for (ll i = 1; i <= r; ++i) {
- num = (num * (n - i)) % mod;
- den = (den * i) % mod;
- }
- return (num * mod_inv(den, mod)) % mod;
- }
- };
- // PNC End
- // Prime Start
- class Prime {
- public:
- ll size;
- vecbl isprime;
- vecll primes;
- Prime(const ll len = max_if) : size(len), isprime(size + 1, true) {
- isprime[0] = isprime[1] = false;
- for (ll i = 2; i <= sqrt_int_u(size); ++i)
- if (isprime[i])
- for (ll j = i * i; j <= size; j += i) isprime[j] = false;
- for (ll i = 2; i <= size; ++i)
- if (isprime[i]) primes.pb(i);
- }
- bool is_prime(ll n, bool old = false) {
- assert(n > 0 && "The given number can't be negative");
- if (n == 1) return false;
- if (n <= 3) return true;
- if (n % 2 == 0 || n % 3 == 0) return false;
- if (n <= size) return isprime[n];
- if (old) {
- for (ll i = 5; i < (int)sqrt(n) + 1; i += 6)
- if (n % i == 0 || n % (i + 2) == 0) return false;
- return true;
- }
- ll d = n - 1;
- while (d % 2 == 0) d /= 2;
- auto miller = [&](ll a) {
- if (a % n == 0) return true;
- ll x = power(a, d, n);
- if (x == 1 || x == n - 1) return true;
- ll c = d;
- while (c < n - 1) {
- x = (x * x) % n;
- if (x == n - 1) return true;
- c <<= 1;
- }
- return false;
- };
- vector<ll> bases64 = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };
- vector<ll> bases32 = { 2, 7, 61 };
- vector<ll>& bases = n <= 4294967296ll ? bases32 : bases64;
- for (ll base : bases)
- if (!miller(base)) return false;
- return true;
- }
- };
- // Prime End
- // Polynomial Hashing Start
- class PolyHash {
- public:
- ll n;
- str s;
- vecll hash, powers, mmi;
- const ll p = 31;
- PolyHash(str& st): n(st.size()), s(st), hash(n, 0), powers(n, 1), mmi(n, 1) {
- for (ll i = 1; i < n; i++) {
- powers[i] = (powers[i - 1] * p) % mod1;
- mmi[i] = mod_inv(powers[i]);
- }
- hash[0] = s[0] - 'a' + 1;
- for (ll i = 1; i < n; i++) hash[i] = (hash[i - 1] + (powers[i] * (s[i] - 'a' + 1) % mod1)) % mod1;
- }
- ll hash_val(ll left, ll right) {
- if (left == 0) return hash[right];
- ll ans = (hash[right] - hash[left - 1] + mod1) % mod1;
- ans = (mmi[left] * ans) % mod1;
- return ans;
- }
- };
- // Polynomial Hashing End
- // Disjoint Set Union Start
- class DisjointSet {
- private:
- vecll parent, depth, set_size, max_set, min_set;
- ll num_sets, max_size;
- public:
- DisjointSet() {}
- DisjointSet(ll n, ll start = 1) { init(n, start); }
- DisjointSet(const DisjointSet& obj) : parent(all(obj.parent)), depth(all(obj.depth)), set_size(all(obj.set_size)), min_set(all(obj.min_set)), max_set(all(obj.max_set)), max_size(obj.max_size), num_sets(obj.num_sets) {}
- void init(ll n, ll start = 1) {
- num_sets = n;
- max_size = 1;
- n += start;
- parent.assign(n, 0);
- max_set.assign(n, 0);
- min_set.assign(n, 0);
- for (ll i = start; i < n; ++i) parent[i] = max_set[i] = min_set[i] = i;
- depth.assign(n, 0);
- set_size.assign(n, 1);
- }
- ll find_set(ll n) {
- return parent[n] = (parent[n] == n ? n : find_set(parent[n]));
- }
- ll find_set(ll n, bool p) {
- stack<ll> st;
- ll v;
- while (n != parent[n]) {
- st.push(n);
- n = parent[n];
- }
- while (!st.empty()) {
- v = st.top();
- st.pop();
- parent[v] = n;
- }
- return n;
- }
- bool is_same_set(ll a, ll b) {
- return find_set(a) == find_set(b);
- }
- void union_set(ll a, ll b) {
- ll x = find_set(a), y = find_set(b);
- if (x == y) return;
- if (depth[x] > depth[y]) swap(x, y);
- if (depth[x] == depth[y]) depth[y]++;
- parent[x] = y;
- set_size[y] += set_size[x];
- max_size = max((ll)max_size, set_size[y]);
- min_set[y] = min(min_set[y], min_set[x]);
- max_set[y] = max(max_set[y], max_set[x]);
- num_sets--;
- }
- ll num_of_sets() { return num_sets; }
- ll size_of_set(ll n) { return set_size[find_set(n)]; }
- ll max_of_set(ll n) { return max_set[find_set(n)]; }
- ll min_of_set(ll n) { return min_set[find_set(n)]; }
- ll max_size_of_sets() { return max_size; }
- };
- // Disjoint Set Union End
- // Unweighted Graph Start
- // Unweighted Graph End
- // Weighted Graph Start
- // Weighted Graph End
- // Segment Tree Start
- template <class T>
- class SegmentTree {
- private:
- const function<T(T, T)>& func;
- vector<T> tree;
- const size_t size;
- size_t query_left, query_right, update_index, update_new_value;
- void build_tree(size_t tree_index, size_t left, size_t right) {
- if (left == right) {
- tree[tree_index] = data[left];
- return;
- }
- size_t mid = left + (right - left) / 2;
- build_tree(2 * tree_index + 1, left, mid);
- build_tree(2 * tree_index + 2, mid + 1, right);
- tree[tree_index] = func(tree[2 * tree_index + 1], tree[2 * tree_index + 2]);
- }
- T query(size_t tree_index, size_t left, size_t right) {
- if (query_left <= left && right <= query_right) return tree[tree_index];
- size_t mid = left + (right - left) / 2;
- if (mid < query_left || left > query_right) return query(2 * tree_index + 2, mid + 1, right);
- if (right < query_left || mid + 1 > query_right) return query(2 * tree_index + 1, left, mid);
- return func(query(2 * tree_index + 1, left, mid), query(2 * tree_index + 2, mid + 1, right));
- }
- void update(size_t tree_index, size_t left, size_t right) {
- if (left == right) {
- tree[tree_index] = update_new_value;
- return;
- }
- size_t mid = left + (right - left) / 2;
- if (update_index <= mid) update(2 * tree_index + 1, left, mid);
- else update(2 * tree_index + 2, mid + 1, right);
- tree[tree_index] = func(tree[2 * tree_index + 1], tree[2 * tree_index + 2]);
- }
- public:
- vector<T> data;
- SegmentTree(const vector<T>& vec, const function<T(T, T)>& fun) : size(vec.size()), func(fun), data(vec.begin(), vec.end()) {
- tree.resize(4 * size);
- build_tree(0, 0, size - 1);
- }
- T query(ll left, ll right) {
- assert(left >= 0 && right < size && left <= right && "Given query range is invalid or out of range.");
- query_left = left;
- query_right = right;
- return query(0, 0, size - 1);
- }
- void update(ll index, T new_value) {
- assert(index >= 0 && index < size && "Given update index is out of range.");
- data[index] = new_value;
- update_index = index;
- update_new_value = new_value;
- update(0, 0, size - 1);
- }
- };
- // Segment Tree End
- // Trie Start
- class Trie {
- public:
- ll size;
- ll cnt;
- vecll freq;
- str chars;
- unordered_map<char, ll> mp;
- vector<Trie*> child;
- Trie(const ll len = 26, str s = "abcdefghijklmnopqrstuvwxyz") : size(len), cnt(0), freq(size, 0), chars(s), child(size, nullptr) {
- for (ll i = 0; i < size; i++) mp[chars[i]] = i;
- }
- void insert(str s) {
- Trie* node = this;
- ll n = s.length();
- for (ll i = 0; i < n; i++) {
- ll mask = mp[s[i]];
- node->freq[mask]++;
- if (node->child[mask] == nullptr) node->child[mask] = new Trie();
- node = node->child[mask];
- }
- node->cnt++;
- }
- void remove(str s) {
- Trie* node = this;
- ll n = s.length();
- for (ll i = 0; i < n; i++) {
- ll mask = mp[s[i]];
- node->freq[mask]--;
- if (node->freq[mask] == 0) {
- node->child[mask] = nullptr;
- return;
- }
- node = node->child[mask];
- }
- }
- bool search(str s) {
- Trie* node = this;
- ll n = s.length();
- for (ll i = 0; i < n; i++) {
- ll mask = mp[s[i]];
- if (node->child[mask] == nullptr) return false;
- node = node->child[mask];
- }
- return true;
- }
- };
- // Trie End
- // Classes End
- //------------------------------------------------------------------------------------------
- // Global Variables Start
- PNC* pnc;
- Prime* prime;
- auto func = []() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- // pnc = new PNC();
- // prime = new Prime();
- return 0;
- }();
- // Global Variables End
- // #define debug(...) 60
- // /* // Solution Class Start
- class Solution {
- public:
- void solve(ll index) {
- //----------------------------------------------------------------------------------
- // debug("Case #",index,": ",newl);
- ll n,i,j,k;
- cin>>n;
- // cout<<"Case #"<<index<<": "<<ans<<newl;
- //----------------------------------------------------------------------------------
- }
- bool test_cases=true;
- };
- // Solution Class End
- //------------------------------------------------------------------------------------------
- // Main Function Start
- int main() {
- Solution sol;
- ll test_cases = 1;
- if (sol.test_cases) cin >> test_cases;
- for (ll test_case = 1; test_case <= test_cases; ++test_case) sol.solve(test_case);
- return 0;
- }
- // Main Function End
- // */ // Program End
- //------------------------------------------------------------------------------------------
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement