import sequtils,algorithm template times*(n:int,body) = (for _ in 0.." ,discardable.} proc scan(): int = while true: let k = getchar_unlocked() if k < '0': return result = 10 * result + k.ord - '0'.ord type SuffixArray = ref object S : string n : int SA : seq[int] LCP : seq[int] proc newSuffixArray(S:string):SuffixArray = new(result) result.S = S let n = S.len result.n = n # SA var G = newSeq[int](n+1) for i in 0.. 0 : var j = result.SA[B[i]-1] while j + h < n and i + h < n and S[j+h] == S[i+h]: h += 1 result.LCP[B[i]] = h if h > 0 : h -= 1 result.LCP[0] = -1 iterator find(self:SuffixArray,target:string): int = var a = -1 var b = self.n + 1 while a + 1 < b: let m = (a + b) shr 1 let start = self.SA[m] if cmp(self.S[start..= target.len: yield start else: break elif cmp(self.S[start..