#include<bits/stdc++.h>

#define re register
#define il inline
#define inf 0x3f3f3f3f
#define Wanderer 0

using namespace std;

const int MAXN = 5e4+5;
int n, m;
string s[MAXN];

struct node {
	int l, r;
	string maxx;
} tree[MAXN << 2];

il string max(string s1, string s2) {
	int leng = min(s1.length(), s2.length());
	bool vis1[18], vis2[18];
	memset(vis1, 0, sizeof(vis1));
	memset(vis2, 0, sizeof(vis2));
	for (re int i = 0; i < leng; ++i) {
		if (s1[i] >= 'A' && s1[i] <= 'Z')
			s1[i] -= 'A', s1[i] += 'a', vis1[i] = true;
		if (s2[i] >= 'A' && s2[i] <= 'Z')
			s2[i] -= 'A', s2[i] += 'a', vis2[i] = true;
		if (s1[i] > s2[i]) {
			for (re int j = 0; j <= i; ++j) {
				if (vis1[j])
					s1[j] -= 'a', s1[j] += 'A';
				if (vis2[j])
					s2[j] -= 'a', s2[j] += 'A';
			}
			return s1;
		}
		if (s2[i] > s1[i]) {
			for (re int j = 0; j <= i; ++j) {
				if (vis1[j])
					s1[j] -= 'a', s1[j] += 'A';
				if (vis2[j])
					s2[j] -= 'a', s2[j] += 'A';
			}
			return s2;
		}
	}
	if ((int)s1.length() == leng)
		return s2;
	else
		return s1;
}

void build(int p, int l, int r) {
	tree[p].l = l, tree[p].r = r;
	if (l == r) {
		tree[p].maxx = s[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
	tree[p].maxx = max(tree[p << 1].maxx, tree[p << 1 | 1].maxx);
}

string ask(int p, int l, int r, int x, int y) {
	if (x <= tree[p].l && tree[p].r <= y)
		return tree[p].maxx;
	int mid = (tree[p].l + tree[p].r) >> 1;
	string ans = "";
	if (x <= mid)
		ans = max(ans, ask(p << 1, l, mid, x, y));
	if (y > mid)
		ans = max(ans, ask(p << 1 | 1, mid + 1, r, x, y));
	return ans;
}

int main() {
	cin >> n >> m;
	for (re int i = 1; i <= n; ++i)
		cin >> s[i];
	build(1, 1, n);
	for (re int i = 1; i <= m; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		cout << ask(1, 1, n, x, y) << endl;
	}
	return Wanderer;
}