#include <cstdio>
#include <cstring>
#include <algorithm>

const int MN = 100005;

int N, M;
char str[MN];

struct SuffixArray {
	int N, Str[MN], SA[MN], rk[MN], SA2[MN];
	int Sig, Buk[MN], Tmp[MN];
	int Height[MN];
	
	inline void RSort() {
		for (int i = 1; i <= Sig; ++i) Buk[i] = 0;
		for (int i = 1; i <= N; ++i) ++Buk[rk[i]];
		for (int i = 1; i <= Sig; ++i) Buk[i] += Buk[i - 1];
		for (int i = N; i >= 1; --i) SA[Buk[rk[SA2[i]]]--] = SA2[i];
	}
	
	inline void BuildSA() {
		/* Init Str */
		for (int i = 1; i <= N; ++i) rk[i] = Str[i], SA2[i] = i;
		rk[N + 1] = 0;
		Sig = 26 /* maximum letter in Str */, RSort();
		for (int j = 1; j < N; j <<= 1) {
			int P = 0;
			for (int i = 1; i <= j; ++i) SA2[++P] = N - j + i;
			for (int i = 1; i <= N; ++i) if (SA[i] > j) SA2[++P] = SA[i] - j;
			RSort();
			Tmp[SA[1]] = P = 1;
			for (int i = 2; i <= N; ++i) {
				if (rk[SA[i]] != rk[SA[i - 1]] || rk[SA[i] + j] != rk[SA[i - 1] + j]) ++P;
				Tmp[SA[i]] = P;
			}
			for (int i = 1; i <= N; ++i) rk[i] = Tmp[i];
			Sig = P;
			if (Sig == N) break;
		}
	}
	
	inline void GetHeight() {
		int k = 0;
		for (int i = 1; i <= N; ++i) {
			if (rk[i] == 1) k = Height[1] = 0;
			else {
				if (k) --k;
				int j = SA[rk[i] - 1];
				while (i + k <= N && j + k <= N && Str[i + k] == Str[j + k]) ++k;
				Height[rk[i]] = k;
			}
		}
	}
	
	int BLCP[MN][21], Bt;
	
	inline void InitST() {
		for (int i = 1; i <= N; ++i) BLCP[i][0] = Height[i];
		while (2 << Bt <= N) ++Bt;
		for (int j = 1; j <= Bt; ++j)
			for (int i = 1 << j; i <= N; ++i)
				BLCP[i][j] = std::min(BLCP[i][j - 1], BLCP[i - (1 << (j - 1))][j - 1]);
	}
	
	inline int LCP(int x, int y) {
		if (x == y) return N + 1;
		x = rk[x], y = rk[y];
		if (x > y) std::swap(x, y);
		int j = 31 - __builtin_clz(y - x);
		return std::min(BLCP[y][j], BLCP[x + (1 << j)][j]);
	}
	
	inline void GetRange(int pos, int k, int &lb, int &rb) {
		int lj = 0;
		while (pos > 1 << lj && BLCP[pos][lj] >= k) ++lj;
		for (--lj, lb = pos; lj >= 0; --lj)
			if (lb > 1 << lj && BLCP[lb][lj] >= k)
				lb -= 1 << lj;
		int rj = 0;
		while (N - pos >= 1 << rj && BLCP[pos + (1 << rj)][rj] >= k) ++rj;
		for (--rj, rb = pos; rj >= 0; --rj)
			if (N - rb >= 1 << rj && BLCP[rb + (1 << rj)][rj] >= k)
				rb += 1 << rj;
	}
} C1, C2;

int main() {
	scanf("%d%d", &N, &M);
	scanf("%s", str + 1);
	for (int i = 1; i <= N; ++i) C2.Str[N - i + 1] = C1.Str[i] = str[i] - 'a' + 1;
	C2.N = C1.N = N, C1.BuildSA(), C2.BuildSA(), C1.GetHeight(), C2.GetHeight(), C1.InitST(), C2.InitST();
	for (int i = 1; i <= N; ++i) printf("%3d : %s\n", i, str + C1.SA[i]);
	while (M--) {
		int pos, k;
		scanf("%d%d", &pos, &k);
		pos = C1.rk[pos];
		int lb, rb;
		C1.GetRange(pos, k, lb, rb);
		for (int i = lb; i <= rb; ++i)
			printf("  %s\n", str + C1.SA[i]);
	}
	return 0;
}