New

== == == == == =
[TEMPLATES]
== == == == == =
Direction array :
int dx[8] = {1, 0, -1, 0, -1, -1, 1, 1};
int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
//cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
#define filein freopen ("in.txt", "r", stdin)
#define fileout freopen ("out.txt", "w", stdout)
== == ==
[PBDS]
== == ==
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int64_t, null_type, less_equal<int64_t>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

freopen ("input.txt", "r", stdin);
freopen ("output.txt", "w", stdout);
template<typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ", "; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ", "; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << ", " << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << ": " << v.second << ", "; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << ": " << v.second << ", "; os << "}"; return os; }
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }
template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool chmin(T &m, const T q) { if (q < m) {m = q; return true;} else return false; }
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
== == == == == == == == == == == =
    [ BITWISE FUNCTIONS   ]
    == == == == == == == == == == == =

int set_bit(int n, int pos) {return n = (n | (1 << pos));}
int reset_bit(int n, int pos) {return n = n & ~(1 << pos);}
bool check_bit(int n, int pos) {return n = n & (1 << pos);}

void add (int & s, int n) {
	if ((s & (1 << (n - 1)))) return;
	s ^= (1 << (n - 1));
}

void remove (int & s, int n) {
	if (!(s & (1 << (n - 1)))) return;
	s ^= (1 << (n - 1));
}

void display (int s) {
	for (int bit = 0; bit < 9; ++bit) {
		if (s & (1 << bit)) {
			cout << bit + 1 << ' ';
		}
	}
	cout << '\n';
}
== == == == == == == == == == == =
    [NUMBER THEORY SECTION]
== == == == == == == == == == == =

int64_t Fibo (int64_t n) {
	//res[-1] = 0,res[0] = res[1] = 1;
	//check fibo of n, cout << Fibo(n - 1);
	if (res.find(n) != res.end()) {
		return res[n];
	}
	if (n % 2 == 0) {
		return res[n] = (Fibo(n / 2) * Fibo(n / 2) + Fibo(n / 2 - 1) * Fibo(n / 2 - 1)) % mod;
	} else {
		return res[n] = (Fibo(n / 2) * Fibo(n / 2 + 1) + Fibo(n / 2 - 1) * Fibo(n / 2)) % mod;
	}
}

/*
 GCD & LCM Template
 */

template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a % b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }

/*
Moduler Arithmetic
*/
inline void normal(int64_t &a) { a %= mod; (a < 0) && (a += mod); }
inline int64_t modMul(int64_t a, int64_t b) { a %= mod, b %= mod; normal(a), normal(b); return (a * b) % mod; }
inline int64_t modAdd(int64_t a, int64_t b) { a %= mod, b %= mod; normal(a), normal(b); return (a + b) % mod; }
inline int64_t modSub(int64_t a, int64_t b) { a %= mod, b %= mod; normal(a), normal(b); a -= b; normal(a); return a; }
inline int64_t modPow(int64_t b, int64_t p) { int64_t r = 1; while (p) { if (p & 1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline int64_t modInverse(int64_t a) { return modPow(a, mod - 2); }
inline int64_t modDiv(int64_t a, int64_t b) { return modMul(a, modInverse(b)); }
== == == == == == ==
[MATH FORMULA]
== == == == == == ==
//sum of (n)
int sum = n * (n + 1) / 2;
//sum of(n^2)
int sum = ((n * (n + 1)) * (2 * n + 1)) / 6;
//sum of range
sum_of_range = n * ((r - l + 1) * (l + r)) / 2;
/*
 Bitwise Sieve_of_Eratosthenes
 */
const int maxN = 10000;
int64_t isVisited[maxN / 64 + 200];
vector<int> primes;
void Sieve_of_Eratosthenes(int limit) {
	limit += 100;
	for (int64_t i = 3; i <= sqrt(limit) ; i += 2) {
		if (!(isVisited[i / 64] & (1LL << (i % 64)))) {
			for (int64_t j = i * i; j <= limit; j += 2 * i) {
				isVisited[j / 64] |= (1LL << (j % 64));
			}
		}
	}
	primes.push_back(2);
	for (int64_t i = 3; i <= limit; i += 2) {
		if (!(isVisited[i / 64] & (1LL << (i % 64)))) {
			primes.push_back(i);
		}
	}
}

/*
 IS PRIME Function(Bitwise Seive)
*/
bool is_prime(int n) {
	if (n < 2) return false;
	if (n == 2) return true;
	if (n % 2 == 0) return false;
	if (!(isVisited[n / 64] & (1LL << (n % 64)))) return true;
	return false;
}

== == == == == == == == == == == == ==
[DIS - JOINT SET UNION (DSU)]
== == == == == == == == == == == == ==
const int maxN = 100100;
int parent[maxN];

int Find(int child) {
	if (parent[child] < 0) {
		return child;
	}
	return parent[child] = Find(parent[child]);
}

void Union(int a, int b) {
	parent[a] += parent[b];
	parent[b] = a;
}
== == == == == == == == == == == == =
[KMP SEARCH ALGORITHM]
[COMPLEXITY : O(N + M) ]
== == == == == == == == == == == == =

vector<int> lps_array(string p) {
	vector<int> lps((int) p.size());
	int i = 1, idx = 0;
	while (i < (int) p.size()) {
		if (p[idx] == p[i]) {
			lps[i] = idx + 1;
			idx += 1, i += 1;
		} else {
			if (idx != 0) {
				idx = lps[idx - 1];
			} else {
				lps[i] = 0;
				i += 1;
			}
		}
	}
	return lps;
}
void kmp(string s, string p) {
	vector<int> lps = lps_array(p);
	int i = 0, j = 0;
	while (i < (int) s.size()) {
		if (s[i] == p[j]) {
			i += 1, j += 1;
		} else {
			if (j != 0) {
				j = lps[j - 1];
			} else {
				i += 1;
			}
		}
		if (j == (int) p.size()) {
			cout << i - (int) p.size() << "\n";
		}
	}
}


/*
	Build Suffix Array (basic)
*/
	for (int t = 1; t <= T; ++t) {
		string s;
		cin >> s;
		s += '$';
		int n = s.size();
		int order[n]; // order
		int class_[n]; // equivalent class
		pair<char, int> pos[n]; // position
		for (int i = 0; i < n; ++i) {
			pos[i] = make_pair(s[i], i);
		}
		sort(pos, pos + n);
		for (int i = 0; i < n; ++i) {
			order[i] = pos[i].second;
		}
		class_[order[0]] = 0;
		for (int i = 1; i < n; ++i) {
			if (pos[i].first == pos[i - 1].first) {
				class_[order[i]] = class_[order[i - 1]];
			} else {
				class_[order[i]] = class_[order[i - 1]] + 1;
			}
		}
		int k = 0;
		while ((1 << k) < n) {
			pair<pair<int, int>, int> suf[n]; //positon array
			for (int i = 0; i < n; ++i) {
				suf[i] = make_pair(make_pair(class_[i], class_[(i + (1 << k)) % n]), i);
			}
			sort(suf, suf + n);
			for (int i = 0; i < n; ++i) {
				order[i] = suf[i].second;
			}
			class_[order[0]] = 0; // first class to be order[0] = 0
			for (int i = 1; i < n; ++i) {
				if (suf[i].first == suf[i - 1].first) {
					class_[order[i]] = class_[order[i - 1]];
				} else {
					class_[order[i]] = class_[order[i - 1]] + 1;
				}
			}
			k += 1;
		}
		for (int i = 0; i < n; ++i) {
			cout << order[i] << " ";
		}


== == == == == == =
[Z Algorithm]
== == == == == == =
vector<int> z_algo (string s) {
	int n = (int) s.size();
	int l = 0, r = 0;
	vector<int> z(n);
	for (int i = 1; i < n; ++i) {
		if (i > r) {
			l = r = i;
			while (r < n and s[r] == s[r - l]) {
				++r;
			}
			z[i] = r - l;
			--r;
		} else {
			if (i + z[i - l] <= r) {
				z[i] = z[i - l];
			} else {
				l = i;
				while (r < n and s[r] == s[r - l]) {
					++r;
				}
				z[i] = r - l;
				--r;
			}
		}
	}
	return z;
}
== == == == ==
[DIJKSTRA]
== == == == ==
void dijkstra (int source, int n) {
	for (int i = 1; i <= n; ++i) dist[i] = LLONG_MAX;
	dist[source] = 0;
	priority_queue<pair<int64_t, int64_t>, vector<pair<int64_t, int64_t>>, greater<pair<int64_t, int64_t>>> pq;
	pq.push(make_pair(0, source));

	while (!pq.empty()) {
		int64_t u = pq.top().second;
		int64_t current_dist = pq.top().first;
		pq.pop();

		if (dist[u] < current_dist) {
			continue;
		}

		for (pair<int64_t, int64_t> v : adj[u]) {
			if (current_dist + v.second < dist[v.first]) {
				dist[v.first] = current_dist + v.second;
				pq.push(make_pair(dist[v.first], v.first));
			}
		}
	}
}

//Sparse Table

const int maxN = 1e5 + 10;
int64_t st[maxN][20];
int bin_log[maxN];
int64_t input[maxN];

void sparseTable (int n) {
	for (int i = 2; i <= n; ++i) bin_log[i] = bin_log[i / 2] + 1;
	for (int i = 0; i < n; ++i) st[i][0] = input[i];
	for (int j = 1; j < 20; ++j) {
		for (int i = 0; i + (1 << j) - 1 < n; ++i) {
			st[i][j] = max(st[i][j - 1],st[i + (1 << (j - 1))][j - 1]);
		}
	}
	//for query min_max
	/*
		 int l,r;
		 cin >> l >> r;
		 int j = bin_log[r - l + 1];
		 cout << min(st[l][j],st[r - (1 << j) + 1][j]) << '\n';
	*/
}


//String Hashing
const int maxN = 2100;
const int64_t p = 31;
const int64_t m = 1e9 + 7;
int64_t h[maxN],inv[maxN];

int64_t bin_pow (int64_t a,int64_t b) {
	a %= m;
	int64_t res = 1;
	while (b > 0) {
		if (b & 1) res = res * a % m;
		a = a * a % m;
		b >>= 1;
	}
	return res;
}

void compute_hash (string & s) {
	int64_t p_pow = 1;
	inv[0] = 1;
	h[0] = s[0] - 'a' + 1;
	for (int i = 1; i < (int) s.size(); ++i) {
		p_pow = (p_pow * p) % m;
		inv[i] = bin_pow(p_pow,m - 2);
		h[i] = (h[i - 1] + (s[i] - 'a' + 1) * p_pow) % m;
	}
}

int64_t sub_hash (int l,int r) {
	int64_t res = h[r];
	if (l > 0) res -= h[l - 1];
	res = (res * inv[l]) % m;
	if (res < 0) res = (res + m) % m;
	return res;
}

int64_t single_hash (string & s) {
	int64_t hash_value = 0;
	int64_t p_pow = 1;
	for (char c : s) {
		hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
		p_pow = (p_pow * p) % m;
	}
	return hash_value;
}