import os import sys from io import BytesIO, IOBase BUFSIZE = 8192 class FastIO(IOBase): newlines = 0 def __init__(self, file): self._fd = file.fileno() self.buffer = BytesIO() self.writable = "x" in file.mode or "r" not in file.mode self.write = self.buffer.write if self.writable else None def read(self): while True: b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)) if not b: break ptr = self.buffer.tell() self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr) self.newlines = 0 return self.buffer.read() def readline(self): while self.newlines == 0: b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE)) self.newlines = b.count(b"\n") + (not b) ptr = self.buffer.tell() self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr) self.newlines -= 1 return self.buffer.readline() def flush(self): if self.writable: os.write(self._fd, self.buffer.getvalue()) self.buffer.truncate(0), self.buffer.seek(0) class IOWrapper(IOBase): def __init__(self, file): self.buffer = FastIO(file) self.flush = self.buffer.flush self.writable = self.buffer.writable self.write = lambda s: self.buffer.write(s.encode("ascii")) self.read = lambda: self.buffer.read().decode("ascii") self.readline = lambda: self.buffer.readline().decode("ascii") sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout) input = lambda: sys.stdin.readline().rstrip("\r\n") class SegTree: def __init__(self, n, e, ope, lst=[]): self.N0 = 2 ** (n - 1).bit_length() self.e = e self.ope = ope self.data = [e] * (2 * self.N0) if lst: for i in range(n): self.data[self.N0 + i] = lst[i] for i in range(self.N0 - 1, 0, -1): self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1]) def build(self): for i in range(self.N0 - 1, 0, -1): self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1]) def update(self, i, x): #a_iの値をxに更新 i += self.N0 self.data[i] = x while i > 1: i >>= 1 self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1]) def add(self, i, x): self.update(i, x + self.get(i)) def set(self, i, x): self.data[self.N0 + i] = x def query(self, l, r): #区間[l, r)での演算結果 if r <= l: return self.e lres = self.e rres = self.e l += self.N0 r += self.N0 while l < r: if l & 1: lres = self.ope(lres, self.data[l]) l += 1 if r & 1: r -= 1 rres = self.ope(self.data[r], rres) l >>= 1 r >>= 1 return self.ope(lres, rres) def get(self, i): #a_iの値を返す return self.data[self.N0 + i] def SA_IS(a): a += [0] k = max(a) + 1 n = len(a) def induce_l(sa, a, n, k, stype): bucket = get_buckets(a, k, 1) for i in range(n): j = sa[i] - 1 if j >= 0 and (not stype[j]): sa[bucket[a[j]]] = j bucket[a[j]] += 1 def induce_s(sa, a, n, k, stype): bucket = get_buckets(a, k, 0) for i in range(n)[::-1]: j = sa[i] - 1 if j >= 0 and stype[j]: bucket[a[j]] -= 1 sa[bucket[a[j]]] = j def get_buckets(a, k, start = 0): bucket = [0] * k for item in a: bucket[item] += 1 s = 0 for i in range(k): s += bucket[i] bucket[i] = s - (bucket[i] if start else 0) return bucket def set_lms(a, n, k, default_order): bucket = get_buckets(a, k) sa = [-1] * n for i in default_order[::-1]: bucket[a[i]] -= 1 sa[bucket[a[i]]] = i return sa def induce(a, n, k, stype, default_order): sa = set_lms(a, n, k, default_order) induce_l(sa, a, n, k, stype) induce_s(sa, a, n, k, stype) return sa def rename_LMS_substring(sa, a, n, stype, LMS, l): sa = [_s for _s in sa if LMS[_s]] tmp = [-1] * (n//2) + [0] dupl = 0 for _ in range(1, l): i, j = sa[_-1], sa[_] for ii in range(n): if a[i+ii] != a[j+ii] or stype[i+ii] != stype[j+ii]: break if ii and (LMS[i+ii] or LMS[j+ii]): dupl += 1 break tmp[j//2] = _ - dupl tmp = [t for t in tmp if t >= 0] return tmp, dupl def calc(a, n, k): stype = [1] * n for i in range(n-1)[::-1]: if a[i] > a[i+1] or (a[i] == a[i+1] and stype[i+1] == 0): stype[i] = 0 LMS = [1 if stype[i] and not stype[i-1] else 0 for i in range(n-1)] + [1] l = sum(LMS) lms = [i for i in range(n) if LMS[i]] sa = induce(a, n, k, stype, lms) renamed_LMS, dupl = rename_LMS_substring(sa, a, n, stype, LMS, l) if dupl: sub_sa = calc(renamed_LMS, l, l - dupl) else: sub_sa = [0] * l for i in range(l): sub_sa[renamed_LMS[i]] = i lms = [lms[sub_sa[i]] for i in range(l)] sa = induce(a, n, k, stype, lms) return sa sa = calc(a, n, k) return sa def LCP(s, n, sa): lcp = [-1]*(n+1) rank = [0]*(n+1) for i in range(n+1): rank[sa[i]] = i h = 0 lcp[0] = 0 for i in range(n): j = sa[rank[i] - 1] if h > 0: h -= 1 while j+h < n and i+h < n and s[j+h]==s[i+h]: h += 1 lcp[rank[i] - 1] = h return lcp n = int(input()) S = [] le = [] ind = 0 for _ in range(n): le.append(ind) for s in input(): S.append(ord(s)) ind += 1 sa = SA_IS(S) lcp = LCP(S, ind, sa) inv = [0] * ind for i, s in enumerate(sa[1:]): inv[s] = i pos = [0] * n lst = [] for i, l in enumerate(le): pos[i] = inv[l] lst.append(inv[l]) lst.sort() mp = {} A = [] for i, l in enumerate(lst): mp[l] = i if i != 0: mi = 1 << 30 for j in range(lst[i - 1], l): mi = min(mi, lcp[j + 1]) A.append(mi) for i in range(n): pos[i] = mp[pos[i]] seg = SegTree(n - 1, 1 << 30, min, A) def make_query(m, x, d): for _ in range(m): i = x // (n - 1) j = x - i * (n - 1) i += 1 j += 1 if i > j: i, j = j, i else: j += 1 yield i, j x = (x + d) % (n * (n - 1)) ans = 0 for i, j in make_query(*map(int, input().split())): l = pos[i - 1] r = pos[j - 1] if l > r: l, r = r, l ans += seg.query(l, r) print(ans)