#include "brperm.h"
#include <bits/stdc++.h>
using namespace std;
int MAXL;
vector<vector<bool>> sol;
struct node {
map<int, int> child {};
set<int> id {};
};
void init(int n, const char s[]) {
MAXL = __lg(n) + 1;
sol = vector<vector<bool>> (n, vector<bool>(MAXL, false));
vector<node> trie {{}};
for (int i = 0; i < n; i++) {
int cur = 0;
for (int j = i; j < min(i + MAXL, n); j++) {
int c = s[j] - 'a';
if (trie[cur].child.count(c) == 0) {
trie[cur].child[c] = trie.size();
trie.push_back({});
}
cur = trie[cur].child[c];
trie[cur].id.insert(i);
}
}
for (int i = n-1; i >= 0; i--) {
int cur = 0;
for (int j = i; j >= max(i - MAXL + 1, 0); j--) {
int c = s[j] - 'a';
if (trie[cur].child.count(c) == 0) {
break;
}
cur = trie[cur].child[c];
if (trie[cur].id.count(j) == 1) {
sol[j][i - j] = true;
}
}
}
return;
}
int query(int i, int k) {
if (k == 0) return true;
if (k > MAXL) return false;
if (i+1 >= sol.size()) return false;
return sol[i+1][k-1];
}
