#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<int D, typename T>struct vec : public vector<vec<D - 1, T>> {template<typename... Args>vec(int n = 0, Args... args) : vector<vec<D - 1, T>>(n, vec<D - 1, T>(args...)) {}};
template<typename T>struct vec<1, T> : public vector<T> {vec(int n = 0, T val = T()) : vector<T>(n, val) {}};
template<class T1,class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const deque<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
int ri(){int x;scanf("%i",&x);return x;}
void rd(int&x){scanf("%i",&x);}
void rd(long long&x){scanf("%lld",&x);}
void rd(double&x){scanf("%lf",&x);}
void rd(long double&x){scanf("%Lf",&x);}
void rd(string&x){cin>>x;}
void rd(char*x){scanf("%s",x);}
template<typename T1,typename T2>void rd(pair<T1,T2>&x){rd(x.first);rd(x.second);}
template<typename T>void rd(vector<T>&x){for(T&p:x)rd(p);}
template<typename C,typename...T>void rd(C&a,T&...args){rd(a);rd(args...);}
//istream& operator>>(istream& is,__int128& a){string s;is>>s;a=0;int i=0;bool neg=false;if(s[0]=='-')neg=true,i++;for(;i<s.size();i++)a=a*10+s[i]-'0';if(neg)a*=-1;return is;}
//ostream& operator<<(ostream& os,__int128 a){bool neg=false;if(a<0)neg=true,a*=-1;ll high=(a/(__int128)1e18);ll low=(a-(__int128)1e18*high);string res;if(neg)res+='-';if(high>0){res+=to_string(high);string temp=to_string(low);res+=string(18-temp.size(),'0');res+=temp;}else res+=to_string(low);os<<res;return os;}
struct hasher{
	bool isPrime(int i){
		for(int j=2;j*j<=i;j++)
			if(i%j==0)
				return 0;
		return 1;
	}
	vector<int> mod;
	int n,m,a,mxMod=1e9+7;
	vector<vector<int> > pwr;
	vector<vector<int> > h;
	void init(string s,int number_of_mods){
		m=number_of_mods;
		for(;sz(mod)<m;mxMod++)
			if(isPrime(mxMod))
				mod.push_back(mxMod);
		n=s.size();
		a=300;
		h.resize(m);
		pwr.resize(m);
		for(int i=0;i<m;i++)
			h[i].resize(n),pwr[i].resize(n+1);
		for(int j=0;j<m;j++){
			h[j][0]=s[0]%mod[j];
			pwr[j][0]=1;
			for(int i=1;i<n;i++){
				h[j][i]=((ll)h[j][i-1]*a+s[i])%mod[j],pwr[j][i]=(ll)pwr[j][i-1]*a%mod[j];
			}
			pwr[j][n]=(ll)pwr[j][n-1]*a%mod[j];
		}
	}
	int getHash(int l,int r,int i){
		int hh=h[i][r];
		if(l){
			hh=hh-((ll)pwr[i][r-l+1]*h[i][l-1]%mod[i]);
			if(hh<0)
				hh+=mod[i];
		}
		return hh;
	}
	bool same(int l1,int r1,int l2,int r2){
		if(r1-l1!=r2-l2||l1>r1)
			return 0;
		for(int i=0;i<m;i++)
			if(getHash(l1,r1,i)!=getHash(l2,r2,i))
				return 0;
		return 1;
	}
}h,rh;
const int M=2;
int n,q;
bool pali(int l,int r){
	int l2=n-1-r;
	int r2=n-1-l;
	for(int i=0;i<M;i++){
		if(h.getHash(l,r,i)!=rh.getHash(l2,r2,i)){
			return 0;
		}
	}
	return 1;
}
bool same(int l,int r,int k){
	int l2=n-1-r;
	int r2=n-1-l;
	for(int i=0;i<M;i++){
		if(h.getHash(l,l+k-1,i)!=rh.getHash(l2,l2+k-1,i)){
			return 0;
		}
	}
	return 1;
}
vector<pair<int,int>> solve(vector<pair<int,int>> qu){
	vector<vector<int>> on(n),off(n);
	vector<vector<int>> on2(n),off2(n);
	for(int i=0;i<n;i++){
		int l=0,r=min(i,n-1-i);
		while(l<r){
			int m=(l+r+1)>>1;
			if(pali(i-m,i+m)){
				l=m;
			}
			else{
				r=m-1;
			}
		}
		on[i-l].pb(i);
		if(i!=n-1)
		off[i+1].pb(i);
		if(i!=n-1&&pali(i,i+1)){
			l=0,r=min(i,n-2-i);
			while(l<r){
				int m=(l+r+1)>>1;
				if(pali(i-m,i+1+m)){
					l=m;
				}
				else{
					r=m-1;
				}
			}
			on2[i-l].pb(i);
			off2[i+1].pb(i);
		}
	}
	set<int> o,o2;
	vector<vector<pair<int,int>>> qus(n);
	vector<int> koliko(q);
	for(int i=0;i<q;i++){
		int l=qu[i].f,r=qu[i].s;
		int le=0,ri=(r-l+1)/2;
		while(le<ri){
			int m=(le+ri+1)>>1;
			if(same(l,r,m)){
				le=m;
			}
			else{
				ri=m-1;
			}
		}
		koliko[i]=le;
		if(2*le!=r-l+1)
			qus[l+le].pb({r-le,i});
	}
	vector<int> ans(q);
	for(int i=0;i<n;i++){
		for(auto p:on[i]){
			o.insert(p);
		}
		for(auto p:off[i]){
			o.erase(p);
		}
		for(auto p:on2[i]){
			o2.insert(p);
		}
		for(auto p:off2[i]){
			o2.erase(p);
		}
		for(auto p:qus[i]){
			int r=p.f;
			int ind=p.s;
			int maxCentre=i+(r-i-1)/2;
			auto it=o.upper_bound(maxCentre);
			if(it!=o.begin()){
				it--;
				int cen=(*it);
				int cnt=2*(cen-i)+1;
				ans[ind]=max(ans[ind],cnt);
			}
			maxCentre=i+(r-i-2)/2;//1 -> i-1, 2 -> i
			auto it2=o2.upper_bound(maxCentre);
			if(it2!=o2.begin()){
				it2--;
				int cen=(*it2);
				int cnt=2*(cen-i+1);
				ans[ind]=max(ans[ind],cnt);
			}
		}
	}
	vector<pair<int,int>> res;
	for(int i=0;i<q;i++){
		int l=qu[i].f,r=qu[i].s;
		int crno=koliko[i];
		int zeleno=ans[i];
		int crveno=r-l+1-2*crno-zeleno;
		if(crveno==0){
			res.pb({0,0});
			continue;
		}
		int le=0,ri=crno;
		while(le<ri){
			int m=(le+ri+1)>>1;
			if(h.same(l+crno+zeleno,l+crno+zeleno+m-1,l+crno+zeleno+crveno,l+crno+zeleno+crveno+m-1)){
				le=m;
			}
			else{
				ri=m-1;
			}
		}
		//printf("%i: %i %i\n",i,crveno,le+1);
		res.pb({crveno,le+1});
	}
	return res;
}
string s;
vector<pair<int,int>> qu;
vector<pair<int,int>> mysolve(){
	h.init(s,M);
	reverse(all(s));
	rh.init(s,M);
	vector<pair<int,int>> a=solve(qu);
	swap(h,rh);
	for(auto &p:qu){
		swap(p.f,p.s);
		p.f=n-1-p.f;
		p.s=n-1-p.s;
	}
	vector<pair<int,int>> b=solve(qu);
	vector<pair<int,int>> ans;
	for(int i=0;i<q;i++){
		int mn=a[i].f;
		int cnt=a[i].s;
		if(b[i].f<mn){
			mn=b[i].f;
			cnt=0;
		}
		if(b[i].f==mn){
			cnt+=b[i].s;
		}
		ans.pb({mn,cnt});
	}
	return ans;
}
void read(){
	qu.clear();
	rd(n,s,q);
	for(int i=0;i<q;i++){
		int l=ri()-1,r=ri()-1;
		qu.pb({l,r});
	}
}
void gen(){
	n=rng()%6+1;
	s="";
	for(int i=0;i<n;i++){
		s+='a'+(rng()%3);
	}
	q=rng()%100+1;
	qu.clear();
	for(int i=0;i<q;i++){
		int l=rng()%n,r=rng()%n;
		if(l>r)swap(l,r);
		qu.pb({l,r});
	}
}
bool pali(string s){
	for(int i=0;i<sz(s);i++){
		if(s[i]!=s[sz(s)-1-i]){
			return 0;
		}
	}
	return 1;
}
vector<pair<int,int>> brute(){
	vector<pair<int,int>> ans;
	for(auto p:qu){
		string str=s.substr(p.f,p.s-p.f+1);
		if(pali(str)){
			ans.pb({0,0});
			continue;
		}
		for(int i=1;i<sz(str);i++){
			int cnt=0;
			for(int j=0;j<=sz(str)-i;j++){
				string novi="";
				if(j){
					novi+=str.substr(0,j);
				}
				if(j+i!=sz(str)){
					novi+=str.substr(j+i);
				}
				if(pali(novi))cnt++;
			}
			if(cnt){
				ans.pb({i,cnt});
				break;
			}
		}
	}
	return ans;
}
void printAns(){
	for(auto p:mysolve()){
		printf("%i %i\n",p.f,p.s);
	}
}
int main()
{
	/*int cnt=0;
	while(1){
		cnt++;
		if(cnt%1000==0){
			printf("%i!\n",cnt);
		}
		gen();
		auto my=mysolve();
		auto br=brute();
		if(my!=br){
			cout << s << qu << my << br << endl;
			for(int i=0;i<sz(my);i++){
				if(my[i]!=br[i]){
					printf("Nije isto za %i!  %i %i\n",i,qu[i].f,qu[i].s);
				}
			}
			exit(0);
		}
	}*/
	read();printAns();
	return 0;
}