sparse table

== == == == == =
[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<long long, null_type, less_equal<long long>, 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]
    == == == == == == == == == == == =

        /*
        Fibonacchi
        */

long long Fibo (long long 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(long long &a) { a %= mod; (a < 0) && (a += mod); }
inline long long modMul(long long a, long long b) { a %= mod, b %= mod; normal(a), normal(b); return (a * b) % mod; }
inline long long modAdd(long long a, long long b) { a %= mod, b %= mod; normal(a), normal(b); return (a + b) % mod; }
inline long long modSub(long long a, long long b) { a %= mod, b %= mod; normal(a), normal(b); a -= b; normal(a); return a; }
inline long long modPow(long long b, long long p) { long long r = 1; while (p) { if (p & 1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline long long modInverse(long long a) { return modPow(a, mod - 2); }
inline long long modDiv(long long a, long long b) { return modMul(a, modInverse(b)); }

== == == == == == =
[MOD Inverse]
== == == == == == =


== == == == == == ==
[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;
long long isVisited[maxN / 64 + 200];
vector<int> primes;
void Sieve_of_Eratosthenes(int limit) {
	limit += 100;
	for (long long i = 3; i <= sqrt(limit) ; i += 2) {
		if (!(isVisited[i / 64] & (1LL << (i % 64)))) {
			for (long long j = i * i; j <= limit; j += 2 * i) {
				isVisited[j / 64] |= (1LL << (j % 64));
			}
		}
	}
	primes.push_back(2);
	for (long long 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;
}


/*
 Generate All Divisors of a Number Using Prime Factorization
 */

//Seive CODE Here

vector<int> setDivisors(int n, int i, vector<int> & divisors, vector<pair<int, int>> factors) {
	int j, x, k;
	for (j = i; j < (int) factors.size(); j++) {
		x = factors[j].first * n;
		for (k = 0; k < factors[j].second; k++) {
			divisors.push_back(x);
			setDivisors(x, j + 1, divisors, factors);
			x *= factors[j].first;
		}
	}
	return divisors;
}
vector<int> PF(int n) {
	int x = n;
	vector<pair<int, int>> factors;
	for (auto i : primes) {
		if (i * i > n) {
			break;
		}
		if (n % i == 0) {
			int count = 0;
			while (n % i == 0) {
				n /= i;
				count += 1;
			}
			factors.push_back(make_pair(i, count));
		}
	}
	if (n > 1) {
		factors.push_back(make_pair(n, 1));
	}
	vector<int> d = {1};
	vector<int> divisors = setDivisors(1, 0, d, factors);
	return divisors;
}

/*
Generate Divisors in Sqrt(n) Time
*/
vector<int> GEN_DIVS_SQRT(int n) {
	vector<int> divisors;
	for (int i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			if (n / i != i) {
				divisors.push_back(n / i);
			}
			divisors.push_back(i);
		}
	}
	return divisors;
}

/*
Count Divisors Using Prime Factorization
*/
int COUNT_DIVISORS(int n) {
	int divisors = 1;
	for (auto i : primes) {
		if (n % i == 0) {
			if (i * i > n) {
				return divisors;
			}
			int count = 1;
			while (n % i == 0) {
				n /= i;
				count += 1;
			}
			divisors *= count;
		}
	}
	return divisors;
}

== == == == == == == == == =
    [ BIG MOD SECTION ]
    == == == == == == == == == =
//divide a long number(like 10^18)
int Quotient(string s, int m) {
	int count = 0;
	for (int i = 0; i < (int) s.size(); i++) {
		count = (count * 10 + (s[i] - 48)) % m;
	}
	return  count;
}

== == == == == == == == == == == == == == =
    [Range Minimum Query SECTION]
    == == == == == == == == == == == == == == =
        == == == == == == == == == == == == == ==
        [SEGMENT TREE (SUM) EDITABLE]
        == == == == == == == == == == == == == ==
        const int maxN = 10000 * 4 + 1;
int input[maxN / 4], tree[maxN];
void buildTree(int idx, int start, int end) {
	if (start == end) {
		tree[idx] = input[start];
	} else {
		int mid = start + (end - start) / 2;
		buildTree(idx * 2, start, mid);
		buildTree(idx * 2 + 1, mid + 1, end);
		tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
	}
}
int query(int idx, int start, int end, int l, int r) {
	if (l > end or r < start) {
		return 0;
	}
	if (start >= l and  end <= r) {
		return tree[idx];
	}
	int mid = start + (end - start) / 2;
	return query(idx * 2, start, mid, l, r) + query(idx * 2 + 1, mid + 1, end, l, r);
}
void update(int idx, int l, int r, int pos, int val) {
	set<char> res;
	if (l == r) {
		tree[idx] = val;
	} else {
		int mid = l + (r - l) / 2;
		if (pos <= mid) {
			update(idx * 2, l, mid, pos, val);
		} else {
			update(idx * 2 + 1, mid + 1, r, pos, val);
		}
		res.insert(tree[idx * 2].begin(), tree[idx * 2].end());
		res.isnert(Tree[idx * 2 + 1].begin(), tree[idx * 2].end());
		tree[idx] = res;
	}
}
== == == == == == == == == == == == ==
[DIS - JOINT SET UNION (DSU)]
== == == == == == == == == == == == ==


const int maxN = 26;
int p[maxN],r[maxN];
bool has[maxN];

int __find__ (int a) {
	return p[a] = (p[a] == a ? a : __find__(p[a]));
}

void __union__ (int a,int b) {
	a = __find__(a);
	b = __find__(b);
	if (r[a] == r[b]) ++r[a];
	if (r[a] > r[b]) p[b] = a;
	else p[a] = b;
}

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;
}
== == == == == == == == == =
[STRING ALGORITHMS]
== == == == == == == == == =
== == == == == == == == == == == == =
[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";
		}
	}
}
== == == == == == ==
[GRAPH THEORY]
== == == == == == ==
/*
 Bipartile(Also Known as Two Coloring Problem) Checking
 */
const int maxN = 101;
vector<int> adj[maxN];
bool isVisited[maxN];
int color[maxN];
int Two_Coloring(int node, int col) {
	isVisited[node] = true;
	color[node] = col;
	for (auto u : adj[node]) {
		if (!isVisited[node]) {
			if (!Two_Coloring(u, col ^ 1)) {
				return false;
			}
		} else {
			if (color[node] == color[u`]) {
				return false;
			}
		}
	}
	return true;
}

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

/*
 Cycle Detection / Finding Back Edge
 */
const int maxN = 101;
vector<int> adj[maxN];
bool isVisited[maxN];
bool CycleDetection(int node, int parent) {
	isVisited[node] = true;
	for (auto u : adj[node]) {
		if (!isVisited[u]) {
			if (CycleDetection(u, node)) {
				return true;
			}
		}
	} else {
		if (u != parent) {
			return true;
		}
	}
}
return false;
}

/*
 In and Out Time of a Node
 */
const int maxN = 101;
vector<int> adj[maxN];
bool isVisited[maxN];
int InTime[maxN], OutTime[maxN];
int Timer = 1;
void InOutTime(int node) {
	isVisited[node] = true;
	InTime[node] = Timer++;
	for (auto u : adj[node]) {
		if (!isVisited[u]) {
			InOutTime(u);
		}
	}
	OutTime[node] = Timer++;
}

/*
 BFS : Breath First Search
 */
const int maxN = 101;
vector<int> adj[maxN];
bool isVisited[maxN];
int dist[maxN];
void BFS(int node) {
	queue<int> q;
	q.push(node);
	isVisited[node] = true;
	dist[node] = 0;
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (auto u : adj[v]) {
			if (!isVisited[u]) {
				isVisited[u] = true;
				dist[u] = dist[v] + 1;
				q.push(u);
			}
		}
	}
}

/*
 Diameter of a Tree Using DFS
*/

const int maxN = 10100;
int max_distance, max_node;
vector<int> adj[maxN];
bool isVisited[maxN];
void diameter(int node, int distance) {
	isVisited[node] = true;
	if (distance > max_distance) {
		max_distance = distance;
		max_node = node; `
	}
	for (int child : adj[node]) {
		if (!isVisited[child]) {
			dfs(child, distance + 1);
		}
	}
}

/*
 Diameter of a Tree Using BFS
*/
const int maxN = 10100;
vector<int> adj[maxN];
bool isVisited[maxN];
int dist[maxN];
pair<int, int> BFS(int node, int distance) {
	int max_node = -1, max_dist = -1;
	queue<int> q;
	q.push(node);
	dist[node] = distance;
	while (!q.empty()) {
		int v = q.front();
		q.pop();
		for (auto u : adj[v]) {
			if (!isVisited[u]) {
				q.push(u);
				isVisited[u] = true;
				dist[u] = dist[v] + 1;
				if (dist[u] > max_dist) {
					max_dist = dist[u];
					max_node = u;
				}
			}
		}
	}
	return {max_node, max_dist};
}
/* Main Functon (DFS) */
max_distance = -1;
dfs(1, 0);
for (int i = 1; i <= n; i++) {
	isVisited[i] = false;
}
max_distance = -1;
dfs(max_node, 0);
cout << max_distance << "\n";

/* Main Function (BFS) */
pair<int, int> node = BFS(1, 0);
for (int i = 1; i <= n; i++) {
	isVisited[i] = false;
	dist[i] = 0;
}
node = BFS(node.first, 0);
cout << node.second << "\n";

/*
 Calculating SUbtree size using dfs in O(n) Time
*/

const int maxN = 101;
vector<int> adj[maxN];
bool isVisited[maxN];
int subTreeSize[maxN];
int dfs(int node) {
	isVisited[node] = true;
	int count = 1;
	for (auto child : adj[node]) {
		if (!isVisited[child]) {
			count += dfs(child);
		}
	}
	subTreeSize[node] = count;
}

/*
 Find Bridges Using DFS
*/

const int maxN = 101;
const int maxN = 101;
vector<int> adj[maxN];
bool visited[maxN];
int in[maxN], low[maxN];
int timer = 0;
void dfs(int node, int parent) {
	visited[node] = true;
	in[node] = low[node] = timer++;
	for (auto child : adj[node]) {
		if (child == parent) {
			continue;
		}
		if (visited[child]) {
			low[node] = min(low[node], in[child]);
		} else {
			dfs(child, node);
			if (low[child] > in[node]) {
				cout << node << " -> " << child << " Is a Bridge\n";
			}
			low[node] = min(low[node], low[child]);
		}
	}
}

/*
	Build Suffix Array (basic)
*/

#include<bits/stdc++.h>
using namespace std;

int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	//~ cin >> T;
	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] << " ";
		}
	}
}


//[Count Set Bits]
int count = 0;
while (n) {
	count += (n & 1);
	n >>= 1;
}

== == == == == == =
[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;
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	//~ cin >> T;
	for (int test_case = 1; test_case <= T; ++test_case) {
		string s, t;
		cin >> s >> t;
		string total = t + "$" + s;
		vector<int> z = z_algo(total);
		for (int i = 0; i < (int) z.size(); ++i) {
			if (z[i] == (int) t.size()) {
				cout << i - (int) t.size() - 1 << "\n";
			}
		}
	}
	//cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

== == == == == ==
[BITMASK DP]
== == == == == ==
#include<bits/stdc++.h>
using namespace std;

int mem[1000][1030];

bool check (int mask) {
	return (bool) (mask & ((1 << 10) - 1));
}

int solve (int pos, int n, int mask) {
	if (pos >= n) {
		return check(mask);
	}
	if (mem[pos][mask] != -1) {
		return mem[pos][mask];
	}
	int res = 0;
	for (int i = (pos == 0 ? 1 : pos); i <= 9; ++i) {
		res += solve (pos + 1, n, mask | (1 << pos));
	}
	return mem[pos][mask] = res;
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	//~ cin >> T;
	for (int test_case = 1; test_case <= T; ++test_case) {
		memset(mem, -1, sizeof(mem));
		int n;
		cin >> n;
		cout << solve (1, n, 0) << "\n";
	}
	//cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

== == == == ==
[DIJKSTRA]
== == == == ==

/*
======================
[     ___T_          ]
[    | 6=6 | =>HI :-)]
[    |__o__|         ]
[ >===]__o[===<      ]
[     [o__]          ]
[      .".           ]
[      |_|           ]
[                    ]
======================
*/

#include<bits/stdc++.h>
using namespace std;

const int maxN = 2 * 1e5;
vector<pair<long long, long long>> adj[maxN];
long long dist[maxN];

void dijkstra (int source, int n) {
	for (int i = 1; i <= n; ++i) dist[i] = LLONG_MAX;
	dist[source] = 0;
	priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
	pq.push(make_pair(0, source));

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

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

		for (pair<long long, long long> 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));
			}
		}
	}
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T = 1;
	//~ cin >> T;
	for (int test_case = 1; test_case <= T; ++test_case) {
		int n, m;
		cin >> n >> m;
		for (int i = 1; i <= m; ++i) {
			long long u, v, w;
			cin >> u >> v >> w;
			adj[u].push_back(make_pair(v, w));
		}
		dijkstra(1, n);
		for (int i = 1; i <= n; ++i) {
			cout << dist[i] << " ";
		}
	}
	//cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}


Sparse Table

const int maxN = 1e5 + 10;
long long st[maxN][20];
int bin_log[maxN];
long long 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

int single_hash (const string & s) {
	const int p = 31;
	const int m = 1e9 + 9;
	long long hash_value = 0;
	long long 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;
}

int compute_hash (const string & s) {
	int n = (int) s.size();
	const int p = 31;
	const int m = 1e9 + 9;
	vector<long long> p_pow(n);
	p_pow[0] = 1;
	for (int i= 1; i < n; ++i) p_pow[i] = (p_pow[i - 1] * p) % m;
	vector<long long> h(n + 1,0);
	for (int i = 0; i < n; ++i) {
		h[i + 1] = (h[i] + (s[i] - 'a' + 1) * p_pow[i]) % m;
	}
	//number of different substring(for small length)
	int cnt = 0;
	for (int l = 1; l <= n; ++l) {
		set<long long> hs;
		for (int i = 0; i <= n - l; ++i) {
			long long cur_h = (h[i + l] + m - h[i]) % m;
			cur_h = (cur_h * p_pow[n - i - 1]) % m;
			hs.insert(cur_h);
		}
		cnt += (int) hs.size();
	}
	return cnt;
}



const int maxN = 2100;
const long long p = 31;
const long long m = 1e9 + 7;
long long h[maxN],inv[maxN];

long long bin_pow (long long a,long long b) {
	a %= m;
	long long 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) {
	long long 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;
	}
}

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

long long single_hash (string & s) {
	long long hash_value = 0;
	long long 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;
}


struct StringHash {
	const long long p = 31;
	const long long m = 1e9 + 7;
	vector<long long> h;
	vector<long long> inv;
	inline void init (string & s) {
		h.resize((int) s.size());
		inv.resize((int) s.size());
		compute_hash(s);
	}
	inline long long bin_pow (long long a,long long b) {
		a %= m;
		long long res = 1;
		while (b > 0) {
			if (b & 1) res = res * a % m;
			a = a * a % m;
			b >>= 1;
		}
		return res;
	}
	inline void compute_hash (string & s) {
		long long 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;
		}
	}
	inline long long sub_hash (int l,int r) {
		long long res = h[r];
		if (l > 0) res -= h[l - 1];
		res = (res * inv[l]) % m;
		if (res < 0) res += m;
		return res;
	}
	inline long long single_hash (string & s) {
		long long hash_value = 0;
		long long p_pow = 1;
		for (int i = 0; i < (int) s.size(); ++i) {
			hash_value = (hash_value + (s[i] - 'a' + 1) * p_pow) % m;
			p_pow = (p_pow * p) % m;
		}
		return hash_value;
	}
};


//sparse table min

const int maxN = 2e5 + 100;
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] = min(st[i][j - 1],st[i + (1 << (j - 1))][j - 1]);
		}
	}
}

int query (int l, int r) {
	//0 based idx
	int j = bin_log[r - l + 1];
	return min(st[l][j],st[r - (1 << j) + 1][j]);
}