Problem: Some programming website is establishing a secure communication protocol. For security reasons, they want to choose several more or less random strings.

Initially, they have a string s consisting of lowercase English letters. Now they want to choose q strings using the following steps, and you are to help them.

  1. A string x consisting of lowercase English letters and integers l and r (1 ≤ l ≤ r ≤ |s|) are chosen. 
  2. Consider all non-empty distinct substrings of the s_l s_{l + 1} … s_r, that is all distinct strings s_i s_{i+1} … s_{j} where l ≤ i ≤ j ≤ r. Among all of them choose all strings that are lexicographically greater than x. 
  3. If there are no such strings, you should print -1. Otherwise print the lexicographically smallest among them. 



String a is lexicographically less than string b, if either a is a prefix of b and a ≠ b, or there exists such a position i (1 ≤ i ≤ min(|a|, |b|)), such that a_i < b_i and for all j (1 ≤ j < i) a_j = b_j. Here |a| denotes the length of the string a.

Input

The first line of input contains a non-empty string s (1 ≤ |s| ≤ 10^{5}) consisting of lowercase English letters.

The second line contains an integer q (1 ≤ q ≤ 2 ⋅ 10^5) — the number of strings to select.

Each of the next q lines contains two integers l, r (1 ≤ l ≤ r ≤ |s|) and a non-empty string x consisting of lowercase English letters. The total length of strings x for all queries does not exceed 2 ⋅ 10^{5}.

Output

Output q lines, each of them should contain the desired string or -1, if there is no such string.

Examples

Input

baa
5
1 2 ba
2 3 a
1 2 b
2 3 aa
1 3 b


Output

-1
aa
ba
-1
ba


Input

bacb
4
1 2 ba
2 3 ac
1 3 ac
3 4 c


Output

-1
c
b
cb


Input

bba
1
1 1 b


Output

-1

Note

Consider the first example.

The string s is "baa". The queries are as follows.

  1. We consider the substring s_1 s_2 that is "ba". It has substrings "b", "a" and "ba", since none of them is greater than the query string "ba", the answer is -1.
  2. We consider substring "aa". Among its substrings only "aa" is greater than the query string "a". So the answer is "aa".
  3. We consider substring "ba". Out of "b", "a" and "ba" only "ba" is greater than the query string "b", so the answer is "ba".
  4. We consider substring "aa". No substring of "aa" is greater than the query string "aa" so the answer is -1.
  5. We consider substring "baa" and it has (among others) substrings "ba", "baa" which are greater than the query string "b". Since "ba" is lexicographically smaller than "baa", the answer is "ba". 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ld = long double;
using vi = std::vector<int>;
using pii = std::pair<int, int>;
using vvi = std::vector<vi>;
using vii = std::vector<pii>;
template <typename T>
int sign(const T& t) {
  return (t > 0) - (t < 0);
}
template <typename T>
bool remax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool remin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
T gcd(T a, T b) {
  a = std::abs(a);
  b = std::abs(b);
  while (b) {
    a %= b;
    std::swap(a, b);
  }
  return a;
}
template <typename T>
T lcm(T a, T b) {
  a = std::abs(a);
  b = std::abs(b);
  return a / gcd(a, b) * b;
}
double get_time() { return static_cast<double>(clock()) / CLOCKS_PER_SEC; }
uint32_t mrand_32t() {
  static std::random_device rd;
  static std::mt19937 rng(rd());
  return rng();
}
uint64_t mrand_64t() {
  static std::random_device rd;
  static std::mt19937_64 rng(rd());
  return rng();
}
template <typename T>
void make_unique(std::vector<T>& v) {
  std::sort(std::begin(v), std::end(v));
  v.erase(std::unique(std::begin(v), std::end(v)), std::end(v));
}
namespace std {
template <typename A, typename B>
string to_string(const pair<A, B>& p) {
  string str;
  str += "(";
  str += to_string(p.first);
  str += ", ";
  str += to_string(p.second);
  str += ")";
  return str;
}
string to_string(bool value) { return value ? "true" : "false"; }
template <typename T>
string to_string(const vector<T>& vec) {
  string str = "{ ";
  bool first = true;
  for (const auto& it : vec) {
    if (!first) {
      str += ", ";
    }
    str += to_string(it);
    first = false;
  }
  str += " }";
  return str;
}
template <typename T>
string to_string(const set<T>& s) {
  string str = "{ ";
  bool first = true;
  for (const auto& it : s) {
    if (!first) {
      str += ", ";
    }
    str += to_string(it);
    first = false;
  }
  str += " }";
  return str;
}
template <typename K, typename V>
string to_string(const map<K, V>& m) {
  string str = "{ ";
  bool first = true;
  for (const auto& it : m) {
    if (!first) {
      str += ", ";
    }
    first = false;
    str += to_string(it.first);
    str += " -> ";
    str += to_string(it.second);
  }
  str += " }";
  return str;
}
string to_string(const string& s) { return "\"" + s + "\""; }
string to_string(const char* s) { return to_string(string(s)); }
string to_string(char ch) { return "\'" + string(1, ch) + "\'"; }
}  // namespace std
void debug_out() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  std::cerr << " " << std::to_string(H);
  debug_out(T...);
}
template <int MAXLEN, int Lc = 'a', int Rc = 'z'>
class SuffixAutomaton {
 public:
  static constexpr int A = Rc - Lc + 1;
  static constexpr int MAXN = MAXLEN * 2;
  struct node;
  using nodePtr = node*;

 private:
  std::vector<node> pool{};
  int ptr_pool{};

 public:
  struct node {
    std::array<nodePtr, A> to{};
    nodePtr link{};
    int len{};
    node() = default;
    void* operator new(size_t) = delete;
  };
  nodePtr newNode() {
    int pos = ptr_pool++;
    assert(pos < MAXN);
    pool[pos] = node();
    return pool.data() + pos;
  }
  SuffixAutomaton() : pool(MAXN) { dropNodesPool(); }
  void dropNodesPool() { ptr_pool = 0; }
  nodePtr root;
  void build(const std::string& s) {
    std::vector<int> ss(s.size());
    for (size_t i = 0; i < s.size(); ++i) {
      ss[i] = static_cast<int>(s[i]);
    }
    build(ss);
  }
  void build(const std::vector<int>& s) {
    root = newNode();
    nodePtr last = root;
    for (const auto& c : s) {
      add_c(encode(c), last);
    }
  }
  int id_node(const nodePtr v) const { return v ? v - pool.data() : -1; }
  nodePtr get_node(const int id) {
    assert(id != -1);
    return pool.data() + id;
  }
  int cnt_alive_nodes() const { return ptr_pool; }
  static int encode(const int c) { return c - Lc; }
  static int decode(const int c) { return c + Lc; }
  void output(std::ostream& os) const {
    assert(root);
    std::map<nodePtr, std::vector<std::string>> S;
    const std::function<void(nodePtr, std::string)> dfs =
        [&](nodePtr v, std::string cur = "") {
          if (!v) {
            return;
          }
          S[v].push_back(cur);
          for (int c = Lc; c <= Rc; ++c) {
            nodePtr to = v->to[encode(c)];
            if (!to) {
              continue;
            }
            cur.push_back(c);
            dfs(to, cur);
            cur.pop_back();
          }
        };
    dfs(root, "");
    for (const auto& it : S) {
      const nodePtr v = it.first;
      const int id = id_node(v);
      os << id << ": ";
      auto ss = S[v];
      std::sort(ss.begin(), ss.end(),
                [](const std::string& a, const std::string& b) {
                  return a.size() < b.size();
                });
      std::string prev___;
      for (const auto& s : ss) {
        if (!prev___.empty()) {
          assert(s.size() == prev___.size() + 1);
          assert(prev___ == s.substr(1));
        }
        prev___ = s;
      }
      if (!ss.empty()) {
        const auto a = ss.front();
        const auto b = ss.back();
        os << "[" << b.substr(0, b.size() - a.size()) << "[" << a << "]";
      }
      os << ", ";
      os << "link = " << id_node(v->link) << ", len = " << v->len << std::endl;
    }
  }

 private:
  void add_c(const int c, nodePtr& last) {
    nodePtr p = last;
    nodePtr nw = newNode();
    nw->len = last->len + 1;
    last = nw;
    for (; p && !p->to[c]; p = p->link) {
      p->to[c] = nw;
    }
    if (!p) {
      nw->link = root;
      return;
    }
    const nodePtr q = p->to[c];
    if (q->len == p->len + 1) {
      nw->link = q;
      return;
    }
    nodePtr clone = newNode();
    clone->to = q->to;
    clone->len = p->len + 1;
    clone->link = q->link;
    nw->link = q->link = clone;
    for (; p && p->to[c] == q; p = p->link) {
      p->to[c] = clone;
    }
  }
};
using namespace std;
const int MAXLEN = int(1e5) + 10;
using SuffAut = SuffixAutomaton<MAXLEN, 'a', 'z'>;
SuffAut aut;
using nodePtr = SuffAut::nodePtr;
struct SegmTree {
  vi t;
  int sz;
  SegmTree(int n = 0) {
    sz = 1;
    while (sz < n) sz *= 2;
    t.assign(sz * 2, -1);
  }
  int get_max(int l, int r) {
    l += sz;
    r += sz;
    int res = -1;
    while (l <= r) {
      remax(res, t[l]);
      remax(res, t[r]);
      l = (l + 1) >> 1;
      r = (r - 1) >> 1;
    }
    return res;
  }
  void upd(int pos, int val) {
    int v = sz + pos;
    remax(t[v], val);
    v >>= 1;
    while (v) {
      t[v] = -1;
      remax(t[v], t[v * 2]);
      remax(t[v], t[v * 2 + 1]);
      v >>= 1;
    }
  }
};
struct Query {
  int l, r;
  string x;
  int id;
  bool read(int i) {
    if (!(cin >> l >> r >> x)) {
      return 0;
    }
    --l;
    --r;
    id = i;
    return 1;
  }
};
string s;
vector<Query> qs;
bool read() {
  if (!(cin >> s)) {
    return 0;
  }
  int q;
  cin >> q;
  qs.resize(q);
  for (int i = int(0); i < int(q); ++i) {
    assert(qs[i].read(i));
  }
  return 1;
}
int N;
vi tin;
vi tout;
int timer;
vvi g;
void dfs(int v) {
  tin[v] = timer++;
  for (int to : g[v]) {
    dfs(to);
  }
  tout[v] = timer;
}
void solve() {
  aut.build(s);
  N = aut.cnt_alive_nodes();
  tin.resize(N);
  tout.resize(N);
  g.clear();
  g.resize(N);
  for (int i = int(0); i < int(N); ++i) {
    auto v = aut.get_node(i);
    if (v->link) {
      g[aut.id_node(v->link)].push_back(aut.id_node(v));
    }
  }
  timer = 0;
  dfs(0);
  assert(timer == N);
  vvi who(int((s).size()));
  for (const auto& q : qs) {
    who[q.r].push_back(q.id);
  }
  SegmTree T(N);
  for (int i = int(0); i < int(N); ++i) {
    T.upd(i, -1);
  }
  const auto get_last = [&](nodePtr v) -> int {
    int id = aut.id_node(v);
    int l = tin[id];
    int r = tout[id] - 1;
    int ans = T.get_max(l, r);
    return ans;
  };
  vector<string> ans(int((qs).size()));
  nodePtr ptr = aut.get_node(0);
  for (int i = int(0); i < int(int((s).size())); ++i) {
    ptr = ptr->to[s[i] - 'a'];
    assert(ptr);
    {
      int pos = tin[aut.id_node(ptr)];
      T.upd(pos, i);
    }
    for (int id : who[i]) {
      nodePtr v = aut.get_node(0);
      const int l = qs[id].l;
      const auto& x = qs[id].x;
      int pref = 0;
      int pref_nxt = -1;
      for (int j = int(0); j < int(int((x).size()) + 1); ++j) {
        const char ch = (j == int((x).size())) ? 0 : x[j];
        for (char nxt = max('a', char(ch + 1)); nxt <= 'z'; ++nxt) {
          nodePtr u = v->to[nxt - 'a'];
          if (!u) {
            continue;
          }
          int R = get_last(u);
          if (R == -1) {
            continue;
          }
          assert(R <= i);
          int L = R - j;
          if (L < l) {
            continue;
          }
          pref = j;
          pref_nxt = nxt - 'a';
          break;
        }
        if (!ch) {
          break;
        }
        v = v->to[ch - 'a'];
        if (!v) {
          break;
        }
      }
      if (pref == 0 && pref_nxt == -1) {
        ans[id].clear();
      } else {
        ans[id] = x.substr(0, pref);
        ans[id] += 'a' + pref_nxt;
      }
    }
  }
  for (int i = int(0); i < int(int((qs).size())); ++i) {
    if (ans[i].empty()) {
      cout << "-1"
           << "\n";
    } else {
      cout << ans[i] << "\n";
    }
  }
  cout << endl;
}
int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cout.precision(12);
  cout << fixed;
  while (read()) {
    solve();
    break;
  }
  return 0;
}