cpp.snippets

snippet vec2
	vector<vector<${1:T}>> ${2:name}(${3:size}, vector<$1>(${4:size}));
snippet template
	#include <bits/stdc++.h>

	using namespace std;
	using ll = long long;

	int main() {
		ios_base::sync_with_stdio(false);
		cin.tie(nullptr);
		${1}	
		return 0;
	}

snippet tests
	int tt;
	cin >> tt;
	while(tt--) {
		${1}
	}

snippet fenwick
	template <typename T>
	class fenwick {
	public:
		vector<T> fenw;
		int n;

		fenwick(int _n) : n(_n) {
			fenw.resize(n);
		}

		void modify(int x, T v) {
			while (x < n) {
				fenw[x] += v;
				x |= (x + 1);
			}
		}

		T get(int x) {
			T v{};
			while (x >= 0) {
				v += fenw[x];
				x = (x & (x + 1)) - 1;
			}
			return v;
		}
	};

snippet debug
	string to_string(string s) {
		return '"' + s + '"';
	}

	string to_string(const char* s) {
		return to_string((string) s);
	}

	string to_string(bool b) {
		return (b ? "true" : "false");
	}

	template <typename A, typename B>
	string to_string(pair<A, B> p) {
		return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
	}

	template <typename A>
	string to_string(A v) {
		bool first = true;
		string res = "{";
		for (const auto &x : v) {
			if (!first) {
				res += ", ";
			}
			first = false;
			res += to_string(x);
		}
		res += "}";
		return res;
	}

	void debug_out() { cerr << endl; }

	template <typename Head, typename... Tail>
	void debug_out(Head H, Tail... T) {
		cerr << " " << to_string(H);
		debug_out(T...);
	}

	#ifdef ABHI
		#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
		#define eprintf(...) fprintf(stderr, __VA_ARGS__)
	#else
		#define debug(...) 42
		#define eprintf(...) 42
	#endif

snippet trace
	#ifdef ABHI
	#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
	template <typename Arg1>
	void __f(const char* name, Arg1&& arg1){
		cerr << name << " : " << arg1 << std::endl;
	}
	template <typename Arg1, typename... Args>
	void __f(const char* names, Arg1&& arg1, Args&&... args){
		const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
	}
	#else
	#define trace(...)
	#endif

snippet segt
	template<class T, int SZ> struct Seg { // SZ should be power of 2
		T seg[2 * SZ], ID = 0;

		Seg() {
			for(int i = 0; i < 2 * SZ; ++i) seg[i] = ID;
		}

		T comb(T a, T b) {
				return max(a, b);
		}
		// easily change this to min or max
		// comb(ID,b) must equal b

		void build() { for(int i = SZ - 1; i >= 0; --i) { seg[i] = comb(seg[2*i],seg[2*i+1]); } }

		void upd(int p, T value) {  // set value at position p
			for (seg[p += SZ] = value; p > 1; p >>= 1)
				seg[p >> 1] = comb(seg[(p|1)^1],seg[p|1]);
				// make sure non-commutative operations work
		}

		T query(int l, int r) {  // query on interval [l, r]
			T res1 = ID, res2 = ID; r++;
			for (l += SZ, r += SZ; l < r; l >>= 1, r >>= 1) {
				if (l&1) res1 = comb(res1,seg[l++]);
				if (r&1) res2 = comb(seg[--r],res2);
			}
			return comb(res1,res2);
		}
	};

snippet segtree
	class SegTree {
	public:
		struct Node {
			// don't forget to set default value (used for leaves)
			// not necessarily neutral element!
			int x = 0;
			int add = 0;
			void apply(int val){
				x = val;
			}
			void update(int val){
				x += val;
			}
		};
	private:
		vector<Node> tree;
		int N , n;

		// for lazy propogation
		inline void push(int x , int l , int r){
			if(tree[x].add != 0){
				tree[x].update(tree[x].add);
				if(l != r){
					int cover = (r - l + 1);
					tree[x << 1].add += (tree[x].add);
					tree[(x << 1)|1].add += (tree[x].add);
				}
				tree[x].add = 0;
			}
		}

		Node combine(const Node &A , const Node &B){
			Node ans;
			ans.x = max(A.x , B.x);
			return ans;
		}

		void build(int s , int e , int idx) {
			if(s == e){
				tree[idx].apply(0);
				return;
			}
			int mid = (s+e) >> 1;
			build(s , mid , (idx << 1));
			build(mid + 1 , e , ((idx << 1)|1));
			return;
		}

		template <typename T>
		void build(const vector < T > &ar , int s , int e , int idx) {
			if(s == e){
				tree[idx].apply(ar[s]);
				return;
			}
			int mid = (s+e) >> 1;
			build(ar , s , mid , (idx << 1));
			build(ar , mid + 1 , e , ((idx << 1)|1));
			tree[idx] = combine(tree[idx << 1] , tree[(idx << 1)|1]);
			return;
		}

		Node query(int s , int e , int lf , int rf , int idx) {
			push(idx , s , e);
			if(rf < s or e < lf) return Node();
			if(lf <= s and e <= rf){
			 return tree[idx];
			}
			int mid = (s + e) >> 1;
			int l = idx << 1;
			int r =  (idx << 1) | 1;
			if(lf <= mid){
				if(rf <= mid){
					return query(s , mid , lf , rf , l);
				}else{
					return combine(query(s , mid , lf , rf , l) , query(mid + 1 , e , lf , rf , r));
				}
			}else{
				return query(mid + 1 , e , lf , rf , r);
			}
		}

		template <typename M>
		void update(int s , int e , int i , M val , int idx) {
			if(s > i or e < i) return;
			if(s == e){
				tree[idx].apply(val);
				return;
			}
			int mid = (s + e) >> 1;
			update(s , mid , i , val , (idx << 1));
			update(mid + 1 , e , i , val , (idx << 1)|1);
			tree[idx] = combine(tree[idx << 1] , tree[(idx << 1) | 1]);
			return;
		}

		template <typename M>
		void update(int s , int e , int l , int r , M val , int idx) {
			push(idx , s , e);
			if(s > r or e < l or s > e) return;
			if(l <= s && e <= r){
				tree[idx].add += val;
				push(idx , s , e);
				return;
			}
			int mid = (s + e) >> 1;
			update(s , mid , l , r , val , (idx << 1));
			update(mid + 1 , e , l , r , val , (idx << 1)|1);
			tree[idx] = combine(tree[idx << 1] , tree[(idx << 1) | 1]);
			return;
		}

	public:
		template<typename T>
		SegTree(const vector<T> &ar) {
			n = (int) ar.size();
			N = 4*(n) + 1;
			tree.resize(N, {});
			build(ar , 0 , n - 1 , 1);
		}

		SegTree(int _n) : n (_n){
			N = 4 * (n) + 1;
			tree.resize(N , {});
			build(0 , n - 1 , 1);
		}

		SegTree(){
			n = 100000;
			N = 4 * n + 1;
			tree.resize(N , {});
		}

		void build(){
			build(0 , n - 1 , 1);
		}

		template<typename T>
		void build(const vector<T> &ar) {
			build(ar , 0 , n - 1 , 1);
		}

		Node query(int l ,int r){
			return query(0 , n - 1 , l , r , 1);
		}

		template<typename T>
		void update(int l , int r , T val){
			update(0 , n - 1 , l , r , val , 1);
		}

		template<typename M>
		void update(int i , M val) {
			update(0 , n - 1 , i , val , 1);
		}
	};

snippet math
	const ll MOD = 998244353;

	inline ll add(ll a, ll b) {
		a += b;
		if (a >= MOD) a -= MOD;
		return a;
	}

	inline ll sub(ll a, ll b) {
		a -= b;
		if (a < 0) a += MOD;
		return a;
	}

	inline ll mul(ll a) {
		return a;
	}

	template<typename... T>
	inline ll mul(ll a, T... b) {
		return (ll) ((ll) a * mul(b...) % MOD);
	}

	inline ll power(ll a, ll b) {
		ll res = 1;
		while (b) {
			if (b & 1) {
				res = mul(res, a);
			}
			a = mul(a, a);
			b >>= 1;
		}
		return res;
	}

	inline ll inv(ll a) {
		a %= MOD;
		if (a < 0) a += MOD;
		ll b = MOD, u = 0, v = 1;
		while (a) {
			ll t = b / a;
			b -= t * a; swap(a, b);
			u -= t * v; swap(u, v);
		}
		assert(b == 1);
		if (u < 0) u += MOD;
		return u;
	}

snippet begin
	${1:ar}.begin(), $1.end()

snippet convexhull
	namespace geo{
		struct point{
			int x , y;
		};
		bool operator < (point a, point b) {
			return a.x < b.x || (a.x == b.x && a.y < b.y);
		}
		bool cw(point a, point b, point c) { //clockwise
			return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y-b.y) < 0;
		}

		bool ccw(point a, point b, point c) { //counter-clockwise
			return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) > 0;
		}
	}

	using namespace geo;

	vector <point> convex_hull(vector<point> a) {
		if (a.size() == 1)
			return a;
		sort(a.begin(), a.end());
		point p1 = a[0], p2 = a.back();
		vector<point> up, down;
		up.push_back(p1);
		down.push_back(p1);
		for (int i = 1; i < (int)a.size(); i++) {
			if (i == (int) a.size() - 1 || cw(p1, a[i], p2)) {
				while (up.size() >= 2 && !cw(up[up.size()-2], up[up.size()-1], a[i]))
					up.pop_back();
				up.push_back(a[i]);
			}
			if (i == (int) a.size() - 1 || ccw(p1, a[i], p2)) {
				while(down.size() >= 2 && !ccw(down[down.size()-2], down[down.size()-1], a[i]))
					down.pop_back();
				down.push_back(a[i]);
		 }
		}
		vector <point> ans;
		for (int i = 0; i < (int)up.size(); i++)
			ans.push_back(up[i]);
		for (int i = (int) down.size() - 2; i > 0; i--)
			ans.push_back(down[i]);
		return ans;
	}

snippet dsu
	template <typename T>
	class dsu {
	public:
		vector<T> p;
		vector<T> rank;
		int n;

		dsu(int _n) : n(_n) {
			p.resize(n);
			rank.resize(n);
			iota(p.begin(), p.end(), 0);
			fill(rank.begin(), rank.end() , 1);
		}

		inline T get(T x) {
			return (x == p[x] ? x : (p[x] = get(p[x])));
		}

		inline bool unite(T x, T y) {
			T px = get(x);
			T py = get(y);
			if (px != py) {
				if(rank[px] == rank[py]){
					p[py] = px;
					rank[px]++;
				} else if(rank[px] < rank[py]){
					p[px] = py;
				} else {
					p[py] = px;
				}
				return true;
			}
			return false;
		}
	};

snippet dijkstra
	template <typename T>
	using minpq = priority_queue<T, vector<T>, greater<T>>;
	const ll inf = (ll) (1e18);

	void dijkstra(int S) {
		ll u , vv , c , w;
		minpq<pair<ll, ll>> Q;
		fill(dist.begin(), dist.end(), inf);
		Q.push({0,S});
		dist[S] = 0;
		while(!Q.empty()){
			u = Q.top().second;
			c = Q.top().first;
			Q.pop();
			if(dist[u] < c){
				continue;
			}
			for(int i = 0 ; i < (int) G[u].size() ; i++){
				w = G[u][i].first;
				vv = G[u][i].second;
				if(dist[vv] > dist[u] + w){
					dist[vv] = dist[u] + w;
					Q.push({dist[vv],vv});
				}
			}
		}
	}

snippet dbg
	#ifdef ABHI
		#include "../debug.h"
		#define _GLIBCXX_DEBUG
	#else
		#define debug(...) 42
		#define cerr if(0) cout
	#endif

snippet eulerphi
	template<typename T>
	T phi(T n){
		double res = n;
		for(int p = 2 ; p*p <= n ; ++p){
			if(n % p == 0){
				while(n % p == 0) {
					n /= p;
				}
				res -= res/p;
			}
		}
		if(n > 1){
			res -= res / n;
		}
		return (T) res;
	}

snippet exgcd
	template <typename T>
	T gcdE(T a , T b , T &x , T &y){
		if(a == 0){
			*x = 0;
			*y = 1;
			return b;
		}
		T x1 , y1;
		T gcd = gcdE(b%a , a , &x1 , &y1);
		x = y1 - (b/a)*x1;
		y = x1;
		return gcd;
	}

snippet fenwick2d
	template <typename T>
	class fenwick{
		vector<vector<T>> tree;
		int n;
	public:
		fenwick(int _n) : n(_n){
			tree.resize(n + 1 , vector <T>(n + 1,0));
		}

		void modify(int x , int y , T val){
			for(int i = x ; i <= n ; i += (i&-i)){
				for(int j = y ; j <= n ; j += (j&-j)){
					tree[i][j] += val;
				}
			}
		}

		T query(int x , int y){
			T res = 0;
			for(int i = x ; i ; i -= (i&-i)){
				for(int j = y ; j ; j-= (j&-j)){
					res += tree[i][j];
				}
			}
			return res;
		}

		T query(int x1 , int y1 , int x2 , int y2){
			return (query(x2,y2) - query(x2,y1-1) - query(x1-1,y2) + query(x1-1,y1-1));
		}
	};

snippet hashing
	// code credit : https://www.codechef.com/viewsolution/18660185
	typedef long long lint;
	const int maxn = 400001;
	const int mod = 1004669333, base = 33, inv_base = 121778101;
	vector<int> base_pow(maxn + 1), inv_base_pow(maxn + 1);
	void prep() {
		base_pow[0] = 1;
		for (int i = 1; i <= maxn; ++i)
			base_pow[i] = (lint)base_pow[i - 1] * base % mod;
		inv_base_pow[0] = 1;
		for (int i = 1; i <= maxn; ++i)
			inv_base_pow[i] = (lint)inv_base_pow[i - 1] * inv_base % mod;
	}
	struct hashes_t {
		string s;
		int n;
		vector<int> acc_hash, acc_inv_hash;
		hashes_t(const string &_s): s(_s), n(s.size()), acc_hash(n + 1, 0)
			, acc_inv_hash(n + 1, 0) {
			for (int i = 0; i < n; ++i) {
				acc_hash[i + 1] =
					(acc_hash[i] + (lint)base_pow[i] * (s[i] - 'a' + 1)) % mod;
				acc_inv_hash[i + 1] =
					(acc_inv_hash[i] + (lint)inv_base_pow[i] * (s[i] - 'a' + 1)) % mod;
			}
		}
		int get_hash(int a, int b) {
			int hash = acc_hash[b + 1] - acc_hash[a];
			if (hash < 0) hash += mod;
			hash = (lint)hash * inv_base_pow[a] % mod;
			return hash;
		}
		int get_inv_hash(int a, int b) {
			int hash = acc_inv_hash[b + 1] - acc_inv_hash[a];
			if (hash < 0) hash += mod;
			hash = (lint)hash * base_pow[b] % mod;
			return hash;
		}
	};

snippet kmp
	template <typename T>
	vector<int> kmp_table(int n, const T &s) {
		vector<int> p(n, 0);
		int k = 0;
		for (int i = 1; i < n; i++) {
			while (k > 0 && !(s[i] == s[k])) {
				k = p[k - 1];
			}
			if (s[i] == s[k]) {
				k++;
			}
			p[i] = k;
		}
		return p;
	}

	template <typename T>
	vector<int> kmp_table(const T &s) {
		return kmp_table((int) s.size(), s);
	}

	template <typename T>
	vector<int> kmp_search(int n, const T &s, int m, const T &w, const vector<int> &p) {
		assert(n >= 1 && (int) p.size() == n);
		vector<int> res;
		int k = 0;
		for (int i = 0; i < m; i++) {
			while (k > 0 && (k == n || !(w[i] == s[k]))) {
				k = p[k - 1];
			}
			if (w[i] == s[k]) {
				k++;
			}
			if (k == n) {
				res.push_back(i - n + 1);
			}
		}
		return res;
		// returns 0-indexed positions of occurrences of s in w
	}

	template <typename T>
	vector<int> kmp_search(const T &s, const T &w, const vector<int> &p) {
		return kmp_search((int) s.size(), s, (int) w.size(), w, p);
	}

snippet LCA
	const int MAXN = 200010;
	const int LG = 20;
	vector<vector<int>> g(MAXN);
	vector<vector<int>> par(MAXN, vector<int>(LG, -1));
	vector<int> dep(MAXN);

	void dfs(int u, int p) {
		if(p == -1) dep[u] = 0;
		else dep[u] = dep[p] + 1;
		par[u][0] = p;
		for(int x: g[u]) if(x != p) {
			dfs(x, u);
		}
	}

	void precompute() {
		for(int k = 1; k < LG; ++k) {
			for(int i = 0; i < MAXN; ++i) {
				if(par[i][k - 1] != -1) {
					par[i][k] = par[par[i][k - 1]][k - 1];
				}
			}
		}
	}

	int walk(int u, int k) {
		for(int i = 0; i < LG && u != -1; ++i) {
			if((k >> i) & 1) {
				assert(u != -1);
				u = par[u][i];
			}
		}
		return u;
	}

	int LCA(int u, int v) {
		if(dep[u] < dep[v]) {
			v = walk(v, dep[v] - dep[u]);
		}
		if(dep[v] < dep[u]) {
			u = walk(u, dep[u] - dep[v]);
		}
		if(u == v) {
			return u;
		}
		for(int i = LG - 1; i >= 0; --i) {
			if(par[u][i] != par[v][i]) {
				u = par[u][i];
				v = par[v][i];
			}
		}
		return par[u][0];
	}

	int dist(int u, int v) {
		int L = LCA(u, v);
		return dep[u] + dep[v] - 2 * ((L + 1) ? dep[L] : 0);
	}

snippet matrix
	const int sz = 3;
	struct vec{
		int arr[SZ];
		void reset(){
			memset(arr , 0 , sizeof(arr));
		}
	};
	struct matrix{
		int arr[SZ][SZ];
		void reset(){
			memset(arr , 0 , sizeof(arr));
		}
		void makeiden(){
			reset();
			for(int i = 0 ; i < SZ ; ++i){
				arr[i][i] = 1;
			}
		}
		matrix operator + (const matrix &o) const {
			matrix res;
			for(int i = 0 ; i < SZ ; ++i){
				for(int j = 0 ; j < SZ ; ++j){
					res.arr[i][j] = arr[i][j] + o.arr[i][j];
					res.arr[i][j] -= (res.arr[i][j] >= mod) * mod;
				}
			}
			return res;
		}
		matrix operator * (const matrix &o) const {
			matrix res;
			for(int i = 0 ; i < SZ ; ++i){
				for(int j = 0 ; j < SZ ; ++j){
					res.arr[i][j] = 0;
					for(int k = 0 ; k < SZ ; ++k){
						res.arr[i][j] = (res.arr[i][j] + 1LL * arr[i][k] * o.arr[k][j]) % mod;
					}
				}
			}
			return res;
		}
		vec operator * (const vec &o) const {
			vec res;
			for(int i = 0 ; i < SZ ; ++i){
				res.arr[i] = 0;
				for(int k = 0 ; k < SZ ; ++k){
					res.arr[i] = (res.arr[i] + 1LL * arr[i][k] * o.arr[k]) % mod;
				}
			}
			return res;
		}
	};

snippet miller
	using ll = long long;

	ll power(ll n , ll p , ll MOD){
		ll ans = 1;
		n %= MOD;
		for(;p;p>>=1){
			if(p&1){
				ans = (ans*n)%MOD;
			}
			n = (n*n)%MOD;
		}
		return ans;
	}
	bool miillerTest(ll d, ll n) {
		ll a = 2 + rand() % (n - 4);
		ll x = power(a, d, n);
		if (x == 1  || x == n-1)
			 return true;
		while (d != n-1) {
			x = (x * x) % n;
			d *= 2;
			if (x == 1)      return false;
			if (x == n-1)    return true;
		}
		return false;
	}

	bool isPrime(ll n, ll k) {
		if (n <= 1 || n == 4)  return false;
		if (n <= 3) return true;
		ll d = n - 1;
		while (d % 2 == 0)
				d /= 2;
		for (ll i = 0; i < k; i++)
		 if (miillerTest(d, n) == false)
			return false;
		return true;
	}

snippet persistenttrie
	// code credit : https://www.codechef.com/viewsolution/23850895
	namespace persistentTrie {
		const int MAXN = 200007, LOG = 22;
		int root[MAXN], availNode = 0;

		struct node {
			int ara[2], sum;
			node() {}
		} tree[MAXN * LOG];

		void insert(int prevnode, int &curRoot, int val) {
			curRoot = ++availNode;
			int curnode = curRoot;
			for(int i = 20; i >= 0; i--) {
				bool bit = val & (1 << i);
				tree[curnode] = tree[prevnode];
				tree[curnode].ara[bit] = ++availNode;
				tree[curnode].sum += 1;
				prevnode = tree[prevnode].ara[bit];
				curnode = tree[curnode].ara[bit];
			}
			tree[curnode] = tree[prevnode];
			tree[curnode].sum += 1;
		}
		int find_xor_max(int prevnode, int curnode, int x) {
			int ans = 0;
			for(int i = 20; i >= 0; i--) {
				bool bit = x & (1 << i);
				if(tree[tree[curnode].ara[bit ^ 1]].sum > tree[tree[prevnode].ara[bit ^ 1]].sum) {
					curnode = tree[curnode].ara[bit ^ 1];
					prevnode = tree[prevnode].ara[bit ^ 1];
					ans = ans | (1 << i);
				}
				else {
					curnode = tree[curnode].ara[bit];
					prevnode = tree[prevnode].ara[bit];
				}
			}
			return ans;
		}
		// USAGE
		// inline void solve() {
			// insert(root[0], root[0], 0);
			// int n;
			// input(n);
			// for(int i = 1; i <= n; i++) {
				// int val;
				// input(val);
				// insert(root[i - 1], root[i], val);
			// }
			// int q;
			// input(q);
			// while(q--) {
				// int l, r, val;
				// input(l); input(r); input(val);
				// output(find_xor_max(root[l - 1], root[r], val));
				// outchar('\n');
			// }
		// }
	} // persistent trie
	using namespace persistentTrie;

snippet psegtree
	struct Node {
		int x;
		Node* l, *r;
		Node(Node* _l = NULL , Node* _r = NULL , int _x = 0) {
			l = _l;
			r = _r;
			x = _x;
		}
	};

	int ar[N];
	Node* versions[N];

	void build(Node* tree , int l , int r) {
		if(r < l) return;
		if(l == r) {
			tree->x = ar[l];
			return;
		}
		int mid = (l + r) >> 1;
		tree->l = new Node();
		tree->r = new Node();
		build(tree->l , l , mid);
		build(tree->r , mid + 1 , r);
		tree->x = tree->l->x + tree->r->x;
	}

	void update(Node* old, Node* curr, int l , int r , int idx , int val) {
		if(idx < l || idx > r || r < l) return;
		if(l == r) {
		 curr->x = old->x + val;
		 return;
		}
		int mid = (l + r) >> 1;
		if(idx <= mid) {
		 curr->r = old->r;
		 curr->l = new Node();
		 update(old->l , curr->l , l , mid , idx , val);
		} else {
		 curr->l = old->l;
		 curr->r = new Node();
		 update(old->r , curr->r , mid + 1 , r , idx , val);
		}
		curr->x = curr->l->x + curr->r->x;
	}

	int query(Node* root , int l , int r , int lo , int hi) {
		if(lo > r || hi < l || r < l) return 0;
		if(root == NULL) assert(false);
		if(lo <= l && r <= hi) {
			return root->x;
		}
		int mid = (l + r) >> 1;
		int a = query(root->l , l , mid , lo , hi);
		int b = query(root->r , mid + 1 , r , lo , hi);
		return a + b;
	}

snippet factor
	const int MAXN = 1e5 + 10;
	vector<int> spf(MAXN);

	void sieve(){
		iota(spf.begin(), spf.end() , 0);
		for (int i = 4 ; i < MAXN ;  i += 2)
			spf[i] = 2;
		for (int i = 3 ; i * i < MAXN ; i++) {
			if (spf[i] == i) {
				for (int j = i * i; j < MAXN ;  j += i)
					if (spf[j] == j)
						spf[j] = i;
			}
		}
	}

	vector<int> getF(int x){
		vector<int> factors;
		while (x != 1) {
			factors.push_back(spf[x]);
			x = x / spf[x];
		}
		return factors;
	}

snippet pbds
	#include <ext/pb_ds/assoc_container.hpp>
	#include <ext/pb_ds/tree_policy.hpp>

	using namespace __gnu_pbds;
	template<typename T, class cmp = std::less<T>>
	using Tree = tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;

snippet remax
	template<typename T> void remax (T &u, const T &v) {u = (v > u ? v : u);}
	template<typename T> void remin (T &u, const T &v) {u = (v < u ? v : u);}

snippet sieve
	vector <int> primes;
	void sieve(){
		const int n = 1000010;
		bool prime[n + 1];
		memset(prime, true, sizeof(prime));
		for (int p = 2 ; p * p <= n; ++p) {
			if (prime[p] == true) {
				for (int i = p * 2 ; i <= n ; i += p)
						prime[i] = false;
			}
		}
		for (int p = 2 ; p <= n ; p++)
		 if (prime[p])
			primes.push_back(p);
	}

snippet trie
	const int SZ = 26;
	struct TrieNode {
		vector<TrieNode*> node;
		int pass = 0;
		TrieNode() {
			pass = 0;
			node.resize(SZ);
			for(int i = 0; i < SZ; ++i) {
				node[i] = nullptr;
			}
		}
	};

	class Trie {
		TrieNode *root, *temp;
	public:
		Trie() {
			root = new TrieNode;
		}

		void add(const string &s) {
			temp = root;
			for(auto &c: s) {
				int x = c - 'a';
				if(temp->node[x] == nullptr) {
					temp->node[x] = new TrieNode;
				}
				temp = temp->node[x];
				temp->pass++;
			}
		}

		int query(const string &s) {
			temp = root;
			for(auto &c: s) {
				int x = c - 'a';
				if(temp->node[x] == nullptr) {
					return 0;
				}
				temp = temp->node[x];
			}
			return (temp ? temp->pass : 0);
		}
	};

snippet zalgo
	// z[i] is the length of the longest common prefix between s and the suffix of s starting at i.
	vector<int> z_function(string s) {
		int n = (int) s.length();
		vector<int> z(n);
		for (int i = 1, l = 0, r = 0; i < n; ++i) {
			if (i <= r)
				z[i] = min (r - i + 1, z[i - l]);
			while (i + z[i] < n && s[z[i]] == s[i + z[i]])
				++z[i];
			if (i + z[i] - 1 > r)
				l = i, r = i + z[i] - 1;
		}
		return z;
	}

snippet prng
	mt19937 prng(chrono::steady_clock::now().time_since_epoch().count());
	int rand(int n) {
		return prng() % n;
	}

	int rand(int l, int r) {
		return uniform_int_distribution<int>(l, r)(prng);
	}

snippet modint
	template <int T_MOD>
	struct Modll {
		static constexpr int MOD = T_MOD;
	private:
		using ll = long long;
		int v;

		static int minv(int a, int m) {
			a %= m;
			if (a < 0) a += m;
			int b = m, u = 0, v = 1;
			while (a) {
				int t = b / a;
				b -= t * a; swap(a, b);
				u -= t * v; swap(u, v);
			}
			assert(b == 1);
			if (u < 0) u += m;
			return u;
		}

	public:

		Modll() : v(0) {}
		template<class T> Modll(T v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
		explicit operator int() const { return v; }
		friend std::ostream& operator << (std::ostream& out, const Modll& n) { return out << int(n); }
		friend std::istream& operator >> (std::istream& in, Modll& n) { ll v_; in >> v_; n = Modll(v_); return in; }
		friend bool operator == (const Modll& a, const Modll& b) { return a.v == b.v; }
		friend bool operator != (const Modll& a, const Modll& b) { return a.v != b.v; }

		Modll inv() const {
			Modll res;
			res.v = minv(v, MOD);
			return res;
		}

		Modll neg() const {
			Modll res;
			res.v = v ? MOD - v : 0;
			return res;
		}

		Modll operator- () const {
			return neg();
		}

		Modll operator+ () const {
			return Modll(*this);
		}

		Modll& operator ++ () {
			v++;
			if (v == MOD) v = 0;
			return *this;
		}

		Modll& operator -- () {
			if (v == 0) v = MOD;
			v --;
			return *this;
		}

		Modll& operator += (const Modll& o) {
			v += o.v;
			if (v >= MOD) v -= MOD;
			return *this;
		}

		Modll& operator -= (const Modll& o) {
			v -= o.v;
			if (v < 0) v += MOD;
			return *this;
		}

		Modll& operator *= (const Modll& o) {
			v = int(ll(v) * ll(o.v) % MOD);
			return *this;
		}

		Modll& operator /= (const Modll& o) {
			return *this *= o.inv();
		}

		friend Modll operator ++ (Modll& a, int) { Modll r = a; ++a; return r; }
		friend Modll operator -- (Modll& a, int) { Modll r = a; --a; return r; }
		friend Modll operator + (const Modll& a, const Modll& b) { return Modll(a) += b; }
		friend Modll operator - (const Modll& a, const Modll& b) { return Modll(a) -= b; }
		friend Modll operator * (const Modll& a, const Modll& b) { return Modll(a) *= b; }
		friend Modll operator / (const Modll& a, const Modll& b) { return Modll(a) /= b; }  
	};
	
	const int mod = 1000000007;
	using Mint = Modll<mod>;

	Mint power(Mint x, int p) {
		Mint ans = Mint(1);
		while(p) {
			if(p & 1) {
				ans *= x;
			}
			x *= x;
			p >>= 1;
		}
		return ans;
	}

snippet sort
	sort(${1:ar}.begin(), $1.end());

snippet SCC
	int n;
	namespace SCC {  
		const int M = 100010;

		vector<vector<int>> g(M), gr(M);
		vector<bool> used;
		vector<int> order, component;

		void dfs1(int u) {
			used[u] = true;
			for(int x: g[u]) if (!used[x]) {
				dfs1(x);
			}
			order.push_back(u);
		}

		void dfs2(int u) {
			used[u] = true;
			component.push_back(u);
			for(int x: gr[u]) if(!used[x]) {
				dfs2(x);
			}
		}

		void add(int u, int v) {
			g[u].push_back(v);
			gr[v].push_back(u);
		}

	void solve() {
			used.assign(n, false);
			for(int i = 0; i < n; ++i) {
				if(!used[i]) dfs1(i);
			}
			fill(used.begin(), used.end(), false);
			for(int i = 0; i < n; ++i) {
				int v = order[n - i - 1];
				if(!used[v]) {
					dfs2(v);
					/* the component is stored in component vector*/
					component.clear();
				}
			}
		}
	}