stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)

#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)

#define EREP(i,u) for(int i=start[u];i;i=e[i].next)

#define fi first

#define se second

#define mkr(a,b) make_pair(a,b)

#define SZ(A) ((int)A.size())

template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}

template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}

inline int read()

{

	int s=0,f=1; char ch=getchar();

	while(!isdigit(ch) && ch!='-')ch=getchar();

	if(ch=='-')ch=getchar(),f=-1;

	while(isdigit(ch))s=s*10+ch-'0',ch=getchar();

	return ~f?s:-s;

}



const int maxn=1e6+20;



int n;

char S[maxn],T[maxn];



inline void init()

{

	n=read();

	scanf("%s",S+1);

	scanf("%s",T+1);

}



int ans;



inline void doing()

{

	deque<int>q;q.push_back(n+1);

	for(int i=n,j=n+1,del=0;i;i--)

	{

		int tmp=j;

		while(j && (j>i || S[j]!=T[i]))j--;

		if(!j)puts("-1"),exit(0);

		if(j==tmp)

		{

			while(!q.empty() && q.back()-del>=i)q.pop_back();

			q.push_back(i+del); 

		}else

		{

			del++;

			if(i!=j)

			{

				chkmax(ans,SZ(q));

				q.push_front(j+del);

			}

		}

	}

	printf("%d\n",ans);

}



int main()

{

	init();

	doing();

	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 5.2660722819499375x):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e6;

int n,s[N+1],t[N+1];

int hea=1,tai,que[N+1];

int res;

void input(int x[])

{

	static char str[N+2];

	scanf("%s",str+1);

	for(int i=1;i<=n;++i) {

		x[i]=str[i]-'a';

	}

	return;

}

bool check0()

{

	for(int i=1;i<=n;++i) {

		if(s[i]!=t[i]) {

			return false;

		}

	}

	return true;

}

int main()

{

	scanf("%d",&n);

	input(s);

	input(t);

	if(check0()) {

		puts("0");

		return 0;

	}

	for(int spos=n,tpos=n;tpos;--tpos) {

		while((tpos>1)&&(t[tpos-1]==t[tpos])) {

			--tpos;

		}

		while(spos&&((spos>tpos)||(s[spos]!=t[tpos]))) {

			--spos;

		}

		if(!spos) {

			puts("-1");

			return 0;

		}

		while((hea<=tai)&&(que[hea]-(tai-hea+1)+1>tpos)) {

			++hea;

		}

		que[++tai]=spos;

		if(tpos!=1) {

			res=max(res,tai-hea+1);

		}

	}

	++res;

	printf("%d\n",res);

	return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

#define N 1000005

queue<int> q;

char a[N],b[N];

int main()

{

	int n,i,j,ans=0;

	scanf("%d%s%s",&n,a+1,b+1);

	if(strcmp(a+1,b+1)==0){printf("0");return 0;}

	i=j=n;

	while(j){

		while(j&&b[j]==b[j-1])j--;

		while(i&&(i>j||a[i]!=b[j]))i--;

		if(i==0){printf("-1");return 0;}

		while(!q.empty()&&q.front()-(int)q.size()>=j)q.pop();

		if(i!=j)q.push(i);

		ans=max(ans,(int)q.size()+1);

		j--;

	}

	printf("%d",ans);

}

// Faster C++ solution for the same problem (measured speedup: 4.938683877953894x):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e6;

int n,s[N+1],t[N+1];

int hea=1,tai,que[N+1];

int res;

void input(int x[])

{

	static char str[N+2];

	scanf("%s",str+1);

	for(int i=1;i<=n;++i) {

		x[i]=str[i]-'a';

	}

	return;

}

bool check0()

{

	for(int i=1;i<=n;++i) {

		if(s[i]!=t[i]) {

			return false;

		}

	}

	return true;

}

int main()

{

	scanf("%d",&n);

	input(s);

	input(t);

	if(check0()) {

		puts("0");

		return 0;

	}

	for(int spos=n,tpos=n;tpos;--tpos) {

		while((tpos>1)&&(t[tpos-1]==t[tpos])) {

			--tpos;

		}

		while(spos&&((spos>tpos)||(s[spos]!=t[tpos]))) {

			--spos;

		}

		if(!spos) {

			puts("-1");

			return 0;

		}

		while((hea<=tai)&&(que[hea]-(tai-hea+1)+1>tpos)) {

			++hea;

		}

		que[++tai]=spos;

		if(tpos!=1) {

			res=max(res,tai-hea+1);

		}

	}

	++res;

	printf("%d\n",res);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)

#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)

#define EREP(i,u) for(int i=start[u];i;i=e[i].next)

#define fi first

#define se second

#define mkr(a,b) make_pair(a,b)

#define SZ(A) ((int)A.size())

template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}

template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}

inline int read()

{

	int s=0,f=1; char ch=getchar();

	while(!isdigit(ch) && ch!='-')ch=getchar();

	if(ch=='-')ch=getchar(),f=-1;

	while(isdigit(ch))s=s*10+ch-'0',ch=getchar();

	return ~f?s:-s;

}



const int maxn=1e6+20;



int n;

char S[maxn],T[maxn];



inline void init()

{

	n=read();

	scanf("%s",S+1);

	scanf("%s",T+1);

}



int ans;



inline void doing()

{

	deque<int>q;q.push_back(n+1);

	for(int i=n,j=n+1,del=0;i;i--)

	{

		int tmp=j;

		while(j && (j>i || S[j]!=T[i]))j--;

		if(!j)puts("-1"),exit(0);

		if(j==tmp)

		{

			while(!q.empty() && q.back()-del>=i)q.pop_back();

			q.push_back(i+del); 

		}else

		{

			del++;

			if(i!=j)

			{

				chkmax(ans,SZ(q));

				q.push_front(j+del);

			}

		}

	}

	printf("%d\n",ans);

}



int main()

{

	init();

	doing();

	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 5.263359184013346x):
#include<cstdio>

const int N=1000005;

int n,he[128],nx[N],a,qu[N*2],hd,tl,d;char s[N],t[N];

inline int mx(int x,int y){return x>y?x:y;}

int main()

{

	scanf("%d%s%s",&n,s+1,t+1),hd=n+1,tl=n;

	for(int i=1;i<=n;++i)nx[i]=he[s[i]],he[s[i]]=i;

	for(int i=n;i;--i)

	{

		if(hd>tl||i<qu[hd]-d)

		{

			hd=n+1,tl=n,d=0;

			if(s[i]!=t[i])

			{

				for(;he[t[i]]&&he[t[i]]>=i;he[t[i]]=nx[he[t[i]]]);

				if(!he[t[i]])return printf("-1"),0;

				qu[--hd]=he[t[i]],qu[++tl]=i;

			}

		}

		else

		{

			if(s[qu[hd]-d]!=t[i])

			{

				for(;he[t[i]]&&he[t[i]]>=qu[hd]-d;he[t[i]]=nx[he[t[i]]]);

				if(!he[t[i]])return printf("-1"),0;

				for(;qu[tl]-d>i;--tl);++d,qu[--hd]=he[t[i]]+d,qu[++tl]=i+d;

			}

		}

		a=mx(a,tl-hd);

	}

	printf("%d",a);

	return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

#define N 1000005

queue<int> q;

char a[N],b[N];

int main()

{

	int n,i,j,ans=0;

	scanf("%d%s%s",&n,a+1,b+1);

	if(strcmp(a+1,b+1)==0){printf("0");return 0;}

	i=j=n;

	while(j){

		while(j&&b[j]==b[j-1])j--;

		while(i&&(i>j||a[i]!=b[j]))i--;

		if(i==0){printf("-1");return 0;}

		while(!q.empty()&&q.front()-(int)q.size()>=j)q.pop();

		if(i!=j)q.push(i);

		ans=max(ans,(int)q.size()+1);

		j--;

	}

	printf("%d",ans);

}

// Faster C++ solution for the same problem (measured speedup: 4.936139451610815x):
#include<cstdio>

const int N=1000005;

int n,he[128],nx[N],a,qu[N*2],hd,tl,d;char s[N],t[N];

inline int mx(int x,int y){return x>y?x:y;}

int main()

{

	scanf("%d%s%s",&n,s+1,t+1),hd=n+1,tl=n;

	for(int i=1;i<=n;++i)nx[i]=he[s[i]],he[s[i]]=i;

	for(int i=n;i;--i)

	{

		if(hd>tl||i<qu[hd]-d)

		{

			hd=n+1,tl=n,d=0;

			if(s[i]!=t[i])

			{

				for(;he[t[i]]&&he[t[i]]>=i;he[t[i]]=nx[he[t[i]]]);

				if(!he[t[i]])return printf("-1"),0;

				qu[--hd]=he[t[i]],qu[++tl]=i;

			}

		}

		else

		{

			if(s[qu[hd]-d]!=t[i])

			{

				for(;he[t[i]]&&he[t[i]]>=qu[hd]-d;he[t[i]]=nx[he[t[i]]]);

				if(!he[t[i]])return printf("-1"),0;

				for(;qu[tl]-d>i;--tl);++d,qu[--hd]=he[t[i]]+d,qu[++tl]=i+d;

			}

		}

		a=mx(a,tl-hd);

	}

	printf("%d",a);

	return 0;

}
// Slower C++ solution:
// LNU_Algotesters

#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include <fstream>

#include <complex>

using namespace std;



#define FOR(i,a,b) for (int i = (a); i < (b); i++)

#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



#define SZ(a) (int)a.size()

#define ALL(a) a.begin(), a.end()

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL) INF;



const int MAX = 100 * 10000 + 47;





int W[MAX];

bool U[MAX];

int X[MAX];



int main()

{

    

    //freopen("in.txt", "r", stdin);

    //ios::sync_with_stdio(false); cin.tie(0);

    

    int n;

    cin >> n;

    string S, T;

    cin >> S >> T;

    int idx = n - 1;

    FILL(W, -1);

    RFOR(i, n, 0)

    {

        while(idx >= 0 && (idx > i || S[idx] != T[i]))--idx;

        W[i] = idx;

        U[idx] = 1;

        X[idx] = max(X[idx], i);

    }

    

    if (S == T)

    {

        cout << 0 << endl;

        return 0;

    }

    

    FOR(i, 0, n)

        if (W[i] == -1)

        {

            cout << -1 << endl;

            return 0;

        }

    

    vector<PII> V;

    

    FOR(i, 0, n)

        if (U[i])V.PB(MP(i, X[i]));

    

    int ans = 0;

    

    FOR(i, 0, SZ(V))

    {

        int L = i, R = SZ(V);

        while(R - L > 1)

        {

            int M = (R + L) / 2;

            if (V[M].first + i >= V[i].second + M)

                R = M;

            else L = M;

        }

        ans = max(ans, R - i);

    }

    cout << ans << endl;

    

    

}








// Faster C++ solution for the same problem (measured speedup: 5.112159074171989x):
#include<bits/stdc++.h>

using namespace std;



const int _ = 1e6 + 7;

vector < int > pot[26];

int N; char S[_] , T[_];



int main(){

	scanf("%d %s %s" , &N , S , T);

	for(int i = 0 ; i < N ; ++i) pot[S[i] - 'a'].push_back(i);

	int mx = 0 , mrk = 0; char curc; deque < int > q; q.push_back(1e9);

	for(int i = N - 1 ; ~i ; --i){

		if((q.front() + mrk <= i ? curc : S[i]) != T[i]){

			if(pot[T[i] - 'a'].empty()){puts("-1"); return 0;}

			int t = pot[T[i] - 'a'].back(); curc = T[i];

			for(int j = min(i , q.front() + mrk - 1) ; j >= t ; --j) pot[S[j] - 'a'].pop_back();

			--mrk; q.push_front(t - mrk); while(q.back() + mrk >= i) q.pop_back();

			q.push_back(i - mrk); mx = max(mx , (int)q.size() - 1);

		}

		if(q.front() + mrk > i) pot[S[i] - 'a'].pop_back();

	}

	cout << mx; return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define FOR(i,a,b) for (int i = (a); i < (b); i++)

#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



#define SZ(a) (int)a.size()

#define ALL(a) a.begin(), a.end()

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL) INF;



const int MAX = 1001000;



char S[MAX];

char T[MAX];



int A[MAX];



int main()

{

	//freopen("in.txt", "r", stdin);

	//ios::sync_with_stdio(false); cin.tie(0);



	int n;

	scanf("%d", &n);

	scanf("%s", S);

	scanf("%s", T);



	if ((string)(S) ==(string(T)))

	{

		cout<<0<<endl;

		return 0;

	}



	FILL(A, -1);

	int ind = n-1;

	RFOR(i, n, 0)

	{

		while (ind > i) ind--;

		while(ind >= 0 && S[ind] != T[i])

		{

			ind--;

		}



		if (ind == -1)

		{

			cout<<-1<<endl;

			return 0;

		}



		if (A[ind] == -1) A[ind] = i;

	}



	vector<PII> a;

	FOR (i, 0, n)

	{

		if (A[i] != -1) a.PB(MP(i, A[i]));

	}



	/*FOR (i, 0, SZ(a))

	{

		cout<<a[i].first<<' '<<a[i].second<<endl;

	}

	cout<<endl;*/



	int res = 0;



	ind = 0;

	int ind2 = 0;

	FOR (i, 0, SZ(a))

	{

		while(true)

		{

			if (ind2 == SZ(a)) break;

			if (a[ind2].first <= a[i].second)

			{

				ind2++;

				continue;

			}

			break;

		}

		while(true)

		{

			if (ind == SZ(a)) break;

			if (a[ind].first - (ind - i - 1) <= a[i].second)

			{

				ind++;

				continue;

			}

			break;

		}



		res = max(res, ind - i);

	}



	cout<<res<<endl;



}




// Faster C++ solution for the same problem (measured speedup: 4.992223600171655x):
#include<bits/stdc++.h>

using namespace std;



const int _ = 1e6 + 7;

vector < int > pot[26];

int N; char S[_] , T[_];



int main(){

	scanf("%d %s %s" , &N , S , T);

	for(int i = 0 ; i < N ; ++i) pot[S[i] - 'a'].push_back(i);

	int mx = 0 , mrk = 0; char curc; deque < int > q; q.push_back(1e9);

	for(int i = N - 1 ; ~i ; --i){

		if((q.front() + mrk <= i ? curc : S[i]) != T[i]){

			if(pot[T[i] - 'a'].empty()){puts("-1"); return 0;}

			int t = pot[T[i] - 'a'].back(); curc = T[i];

			for(int j = min(i , q.front() + mrk - 1) ; j >= t ; --j) pot[S[j] - 'a'].pop_back();

			--mrk; q.push_front(t - mrk); while(q.back() + mrk >= i) q.pop_back();

			q.push_back(i - mrk); mx = max(mx , (int)q.size() - 1);

		}

		if(q.front() + mrk > i) pot[S[i] - 'a'].pop_back();

	}

	cout << mx; return 0;

}
// Slower C++ solution:
// LNU_Algotesters

#include <iostream>

#include <sstream>

#include <iomanip>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <cstring>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

#include <algorithm>

#include <iterator>

#include <bitset>

#include <ctime>

#include <fstream>

#include <complex>

using namespace std;



#define FOR(i,a,b) for (int i = (a); i < (b); i++)

#define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



#define SZ(a) (int)a.size()

#define ALL(a) a.begin(), a.end()

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL) INF;



const int MAX = 100 * 10000 + 47;





int W[MAX];

bool U[MAX];

int X[MAX];



int main()

{

    

    //freopen("in.txt", "r", stdin);

    //ios::sync_with_stdio(false); cin.tie(0);

    

    int n;

    cin >> n;

    string S, T;

    cin >> S >> T;

    int idx = n - 1;

    FILL(W, -1);

    RFOR(i, n, 0)

    {

        while(idx >= 0 && (idx > i || S[idx] != T[i]))--idx;

        W[i] = idx;

        U[idx] = 1;

        X[idx] = max(X[idx], i);

    }

    

    if (S == T)

    {

        cout << 0 << endl;

        return 0;

    }

    

    FOR(i, 0, n)

        if (W[i] == -1)

        {

            cout << -1 << endl;

            return 0;

        }

    

    vector<PII> V;

    

    FOR(i, 0, n)

        if (U[i])V.PB(MP(i, X[i]));

    

    int ans = 0;

    

    FOR(i, 0, SZ(V))

    {

        int L = i, R = SZ(V);

        while(R - L > 1)

        {

            int M = (R + L) / 2;

            if (V[M].first + i >= V[i].second + M)

                R = M;

            else L = M;

        }

        ans = max(ans, R - i);

    }

    cout << ans << endl;

    

    

}








// Faster C++ solution for the same problem (measured speedup: 5.110698819527195x):
#include<bits/stdc++.h>

#define maxn 1000005

using namespace std;

int n,ans;

char s[maxn],t[maxn];

queue<int>q;

int main()

{

	scanf("%d%s%s",&n,s,t);

	for(int i=0;i<n;i++) if(s[i]!=t[i]) {ans=-1;break;}

	if(ans!=-1) return puts("0"),0;

	for(int up=n-1,down=n-1;down>=0;down--){

		if(t[down]==t[down-1]) continue;

		while(up>down||(up>=0&&s[up]!=t[down])) up--;

		if(up<0) {ans=-1;break;}

		while(!q.empty()&&q.front()-q.size()>=down) q.pop();

		if(up!=down) q.push(up);

		ans=max(ans,(int)q.size()+1);

	}

	printf("%d\n",ans);

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define FOR(i,a,b) for (int i = (a); i < (b); i++)

#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)

#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define FILL(a,value) memset(a, value, sizeof(a))



#define SZ(a) (int)a.size()

#define ALL(a) a.begin(), a.end()

#define PB push_back

#define MP make_pair



typedef long long LL;

typedef vector<int> VI;

typedef pair<int, int> PII;



const double PI = acos(-1.0);

const int INF = 1000 * 1000 * 1000 + 7;

const LL LINF = INF * (LL) INF;



const int MAX = 1001000;



char S[MAX];

char T[MAX];



int A[MAX];



int main()

{

	//freopen("in.txt", "r", stdin);

	//ios::sync_with_stdio(false); cin.tie(0);



	int n;

	scanf("%d", &n);

	scanf("%s", S);

	scanf("%s", T);



	if ((string)(S) ==(string(T)))

	{

		cout<<0<<endl;

		return 0;

	}



	FILL(A, -1);

	int ind = n-1;

	RFOR(i, n, 0)

	{

		while (ind > i) ind--;

		while(ind >= 0 && S[ind] != T[i])

		{

			ind--;

		}



		if (ind == -1)

		{

			cout<<-1<<endl;

			return 0;

		}



		if (A[ind] == -1) A[ind] = i;

	}



	vector<PII> a;

	FOR (i, 0, n)

	{

		if (A[i] != -1) a.PB(MP(i, A[i]));

	}



	/*FOR (i, 0, SZ(a))

	{

		cout<<a[i].first<<' '<<a[i].second<<endl;

	}

	cout<<endl;*/



	int res = 0;



	ind = 0;

	int ind2 = 0;

	FOR (i, 0, SZ(a))

	{

		while(true)

		{

			if (ind2 == SZ(a)) break;

			if (a[ind2].first <= a[i].second)

			{

				ind2++;

				continue;

			}

			break;

		}

		while(true)

		{

			if (ind == SZ(a)) break;

			if (a[ind].first - (ind - i - 1) <= a[i].second)

			{

				ind++;

				continue;

			}

			break;

		}



		res = max(res, ind - i);

	}



	cout<<res<<endl;



}




// Faster C++ solution for the same problem (measured speedup: 5.0343632893010595x):
#include<bits/stdc++.h>

#define maxn 1000005

using namespace std;

int n,ans;

char s[maxn],t[maxn];

queue<int>q;

int main()

{

	scanf("%d%s%s",&n,s,t);

	for(int i=0;i<n;i++) if(s[i]!=t[i]) {ans=-1;break;}

	if(ans!=-1) return puts("0"),0;

	for(int up=n-1,down=n-1;down>=0;down--){

		if(t[down]==t[down-1]) continue;

		while(up>down||(up>=0&&s[up]!=t[down])) up--;

		if(up<0) {ans=-1;break;}

		while(!q.empty()&&q.front()-q.size()>=down) q.pop();

		if(up!=down) q.push(up);

		ans=max(ans,(int)q.size()+1);

	}

	printf("%d\n",ans);

}
// Slower C++ solution:
#include <iostream>

using namespace std;

constexpr int MOD = 1e9 + 7;



long L, R;

long dp[66][2][2][2];



// y % x = y ^ x and x <= y

// y % x is less than x. 

// when (y>>1) > x, MSB(y) == MSB(y^x) > x. so this doesnt fulfill the condition.

// then (x<<1) >= y >= x. In this case, y % x == y - x.

//

// On the other hand, xor is addition without carry-up.

// Digit that will carry when y + x and not when y ^ x, can be found by y & x.

// finally y ^ x is y + x - (y & x)<<1

// Requirement : y % x = y ^ x (y>=x) => y - x = y + x - (y & x)<<1 => x == y & x

//



int main() {

	cin >> L >> R;



	dp[0][0][0][0] = 1;

	

	// l = 1 : x is already more than L

	// r = 1 : y is already less than R

	// j = 1 : MSB of x and y is matched

	//

	// (x, y) = (1, 1), (0, 1), (0, 0) is required on each digit

	bool x[3] = {1, 0, 0}, y[3] = {1, 1, 0};



	for(int i = 0; i < 60; ++i) {

		bool lb = L>>(59-i)&1, rb = R>>(59-i)&1;



		for(int l = 0; l < 2; ++l) {

			for(int r = 0; r < 2; ++r) {

				for(int j = 0; j < 2; ++j) {



					// loop for updating

					for(int k = 0; k < 3; ++k) {

						if(!l && !x[k] && lb) continue;

						if(!r && y[k] && !rb) continue;

						if(!j && x[k] ^ y[k]) continue;

						

						int nl = (x[k] ^ lb   ? 1 : l);

						int nr = (y[k] ^ rb   ? 1 : r);

						int nj = (x[k] & y[k] ? 1 : j);



						(dp[i+1][nl][nr][nj] += dp[i][l][r][j]) %= MOD;

					}



				}

			}

		}

	}



	long ans = 0;

	for(int l=0;l<2;++l) for(int r=0;r<2;++r) ans = (ans + dp[60][l][r][1]) % MOD;



	cout << ans << '\n';

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.037010867487711x):
#include <cstdio>

long L, R, MOD=1e9+7;

long dp[66][2][2][2];



int main() {

	scanf("%ld%ld", &L, &R);



	dp[0][0][0][0] = 1;

	bool x[3] = {1, 0, 0}, y[3] = {1, 1, 0};



	for(int i = 0; i < 60; ++i) {

		bool lb = L>>(59-i)&1, rb = R>>(59-i)&1;



		for(int l = 0; l < 2; ++l)

			for(int r = 0; r < 2; ++r)

				for(int j = 0; j < 2; ++j)



					for(int k = 0; k < 3; ++k) {

						if(!l && !x[k] && lb) continue;

						if(!r && y[k] && !rb) continue;

						if(!j && x[k] ^ y[k]) continue;

						

						int nl = (x[k] ^ lb   ? 1 : l);

						int nr = (y[k] ^ rb   ? 1 : r);

						int nj = (x[k] & y[k] ? 1 : j);



						(dp[i+1][nl][nr][nj] += dp[i][l][r][j]) %= MOD;

					}



	}

	long ans = dp[60][0][0][1] + dp[60][0][1][1] + dp[60][1][0][1] + dp[60][1][1][1];

	printf("%ld\n", ans % MOD);

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define N 1000021

using namespace std;

int w,h;

int par[N],Rank[N];

char mp[1001][1001];



void init(){

  for(int i=0;i<N;i++) par[i]=i,Rank[i]=0;

}



int find(int x){

  if(par[x]==x)return x;

  return par[x]=find(par[x]);

}



void unite(int x,int y){

  x=find(x),y=find(y);

  if(x==y)return;

  if(Rank[x]<Rank[y])par[x]=y;

  else par[y]=x,Rank[x]+=(Rank[x]==Rank[y]);

}



bool same(int x,int y){return find(x)==find(y);}

int Pos(int x,int y){return w*y+x;}



int dx[]={0,0,-1,1};

int dy[]={1,-1,0,0};

void umeru(){

  for(int i=0;i<h;i++)

    for(int j=0;j<w;j++)

      for(int k=0;k<4;k++){

	int ni=i+dy[k],nj=j+dx[k];

	if(mp[i][j]=='#')continue;

	if(ni<0||nj<0||ni>=h||nj>=w||mp[ni][nj]=='#')continue;

	unite(Pos(j,i),Pos(nj,ni));

      }

}



void umeru2(int x,int y){

  for(int i=0;i<4;i++){

    int ny=y+dy[i],nx=x+dx[i];

    if(ny<0||nx<0||ny>=h||nx>=w||mp[ny][nx]=='#')continue;

    unite(Pos(x,y),Pos(nx,ny));

  }

}



int main(){

  init();

  cin>>w>>h;

  int t;

  for(int i=0;i<h;i++)

    for(int j=0;j<w;j++){

      cin>>mp[i][j];

      if(mp[i][j]=='t')t=Pos(j,i);

    }

  umeru();

 

  int n,ans=-1;

  if(same(0,t)) ans=0;

  cin>>n;

  for(int i=1,a,b;i<=n;i++){

    cin>>a>>b;

    umeru2(a,b);

    mp[b][a]='.';

    if(same(0,t)&&ans==-1)ans=i;

  }

  cout <<ans<<endl;

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.682899023154809x):
#include<bits/stdc++.h>

using namespace std;

#define lp(i,n) for(int i=0;i<n;i++)

#define lps(i,j,n) for(int i=j;i<n;i++)

#define fordebug int hoge;cin>>hoge;

#define DEKAI 1000000007;

#define INF (1<<28)

#define int long long

#define double long double

#define floot10 cout<<fixed<<setprecision(10)

bool dp[1100][1100];



signed main(){

  int w,h;

  cin>>w>>h;

  char a[1100][1100];

  lp(i,1100)lp(j,1100){

    dp[i][j]=false;

    a[i][j]='#';

  }

  int gx,gy;

  lp(i,h){

    lp(j,w){

      cin>>a[i+1][j+1];

      if(a[i+1][j+1]=='t'){

	gx=i+1;

	gy=j+1;

      }

    }

  }

  queue<pair<int,int>> q;

  q.push({1,1});

  dp[1][1]=true;

  int ax[4]={0,0,-1,1};

  int ay[4]={-1,1,0,0};

  int n;

  cin>>n;

  int hox[1010],hoy[1010];

  lp(i,n){

    cin>>hox[i]>>hoy[i];

  }

  lp(z,n+1){

    while(!q.empty()){

      int x,y;

      x=q.front().first;

      y=q.front().second;

      //cout<<x<<y<<endl;

      q.pop();

      lp(i,4){

	int nex=x+ax[i];

	int ney=y+ay[i];

	if(nex==gx&&ney==gy){

	  cout<<z<<endl;

	  return 0;

	}

	if(dp[nex][ney]==false){

	  dp[nex][ney]=true;

	  if(a[nex][ney]=='.'){

	    q.push({nex,ney});

	  }

	}

      }

    }

    if(z==n) break;/*

    lp(i,10){

      lp(j,10){

	if(dp[i+1][j+1]==false){

	  cout<<0;

	}

	else cout<<1;

      }

      cout<<endl;

    }

    lp(i,10){

      lp(j,10){

	cout<<a[i+1][j+1]

      }

      cout<<endl;

      }*/

    int bx,by;

    bx=hoy[z];

    by=hox[z];

    bx++;

    by++;

    if(a[bx][by]=='#'){

      a[bx][by]='.';

      if(dp[bx][by]==true){

	q.push({bx,by});

      }

    }

  }

  cout<<-1<<endl;

  return 0;

}