Problem: Find places where a R × C pattern is found within a H × W region. Print top-left coordinates (i, j) of sub-regions where the pattern found. The top-left and bottom-right coordinates of the region is (0, 0) and (H-1, W-1) respectively.

Constraints

* 1 ≤ H, W ≤ 1000
* 1 ≤ R, C ≤ 1000
* The input consists of alphabetical characters and digits

Input

In the first line, two integers H and W are given. In the following H lines, i-th lines of the region are given.

In the next line, two integers R and C are given. In the following R lines, i-th lines of the pattern are given.

Example

Input

4 5
00010
00101
00010
00100
3 2
10
01
10


Output

0 3
1 2

Solution (in CPP):

Solution:
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;

//Code size is too big,sorry.

class Loc{
public:
	Loc(){
		Table = new int[1001];
		for(int i=0;i<1001;i++){
			Table[i] = -1;
		}
		index = 0;
	}
	void init_index(){
		index = 0;
	}
	void reg_loc(int location){
		Table[index++] = location;
	}
	int next_loc(){
		int ret = Table[index];
		index++;
		return ret;
	}
private:
	int* Table;
	int index;
};

int H_lmt,W_lmt;
long long T_h,T_w,P_h,P_w;

int main(){

	scanf("%lld %lld",&T_h,&T_w);

	char T[T_h][T_w+1];

	for(int i=0;i<T_h;i++){
		scanf("%s",T[i]);
	}

	scanf("%lld %lld",&P_h,&P_w);

	if((T_h<P_h)||(T_w<P_w)) return 0;

	char P[P_h][P_w+1];

	for(int i=0;i<P_h;i++){
		scanf("%s",P[i]);
	}

	H_lmt=T_h-P_h,W_lmt=T_w-P_w;

	int P_count[128]={0},P_first_loc[128];

	for(int i=0;i<128;i++) P_first_loc[i] = -1;

	for(int row=0;row<P_h;row++){
		for(int col=0;col<P_w;col++){
			P_count[P[row][col]]++;
			if(P_first_loc[P[row][col]]==-1){
				P_first_loc[P[row][col]]=1000*row+col;
			}
		}
	}
	int c_count=0,c_min=1000001,c_max=-1,min_char,max_char,appeard_min=1000001;
	bool multFLG = false;
	for(int i=48;i<=122;i++){
		if(P_count[i] > 0){
			c_count++;
			if(c_min>P_count[i]){
				c_min=P_count[i];
				min_char=i;
			}
			if(c_max<P_count[i]){
				c_max=P_count[i];
				max_char=i;
			}
		}
		if(P_first_loc[i]!=0&&P_first_loc[i]<appeard_min){
			appeard_min=P_first_loc[i];
		}
	}
	if(c_count>=2)multFLG=true;

	int second_row=appeard_min/1000,second_col=appeard_min%1000,T_char_count[128]={0};

	for(int row=0;row<T_h;row++){
		for(int col=0;col<T_w;col++){
			T_char_count[T[row][col]]++;
		}
	}
	int tc_count=0,tc_max=-1,t_max_char;
	bool t_multFLG=false;
	for(int i=48;i<=122;i++){
		if(T_char_count[i]>0){
			tc_count++;
			if(tc_max<T_char_count[i]){
				tc_max=T_char_count[i];
				t_max_char=i;
			}
		}
	}
	if(tc_count>=2)t_multFLG=true;

	for(int i=0;i<128;i++){
		if(T_char_count[i]<P_count[i])	return 0;
	}

	char p00=P[0][0];
	if(multFLG==true){
		if(c_max/(P_h*P_w-c_max)>=899){
			bool matchFLG;
			int chk_row=P_first_loc[min_char]/1000,chk_col=P_first_loc[min_char]%1000;

			for(int row=0;row<=H_lmt;row++){
				for(int col=0;col<=W_lmt;col++){
					if(T[row][col]==p00&&T[row+chk_row][col+chk_col]==P[chk_row][chk_col]){
						matchFLG=true;
						for(int tmp_row=0;tmp_row<P_h;tmp_row++){
							for(int tmp_col=0;tmp_col<P_w;tmp_col++){
								if(T[row+tmp_row][col+tmp_col]!=P[tmp_row][tmp_col]){
									matchFLG=false;
									break;
								}
							}
							if(!matchFLG)break;
						}
						if(matchFLG){
							printf("%d %d\n",row,col);
						}
					}
				}
			}
		}else if(P_w*second_row+second_col>1000){
			bool matchFLG;
			for(int row=0;row<=H_lmt;row++){
				for(int col=0;col<=W_lmt;col++){
					if(T[row][col]==p00&&T[row+second_row][col+second_col]==P[second_row][second_col]){
						matchFLG=true;
						for(int tmp_row=0;tmp_row<P_h;tmp_row++){
							for(int tmp_col=0;tmp_col<P_w;tmp_col++){
								if(T[row+tmp_row][col+tmp_col]!=P[tmp_row][tmp_col]){
									matchFLG=false;
									break;
								}
							}
							if(!matchFLG)break;
						}
						if(matchFLG){
							printf("%d %d\n",row,col);
						}
					}
				}
			}
		}else{
			bool ptnFLG=true;
			if((100*(c_max/P_h*P_w)<=5)||(100*(tc_max/T_h*T_w)<=5)){
				ptnFLG=false;
			}
			if(ptnFLG){
				if((T_h-P_h)*(T_w-P_w)*(P_h*P_w)<500000000){
					ptnFLG=false;
				}
			}
			if(ptnFLG){
				if(100*abs(c_max/(P_h*P_w)-tc_max/(T_h*T_w))>=5){
					ptnFLG=false;
				}
			}
			int second_p_max=-1,second_t_max=-1,second_p_char,second_t_char;
			if(ptnFLG){
				for(int i=0;i<128;i++){
					if(T_char_count[i]>0&&i!=t_max_char){
						second_t_max=std::max(second_t_max,T_char_count[i]);
						second_t_char=i;
					}
					if(P_count[i]>0&&i!=max_char){
						second_p_max=std::max(second_p_max,P_count[i]);
						second_p_char=i;
					}
				}
				if(100*abs(second_p_max/(P_h*P_w)-second_t_max/(T_h*T_w))>=2){
					ptnFLG=false;
				}
			}
			if(ptnFLG){
				if((max_char!=t_max_char&&max_char!=second_t_char)||(second_p_char!=t_max_char&&second_p_char!=second_t_char)){
					ptnFLG=false;
				}
			}
			Loc p_brokenH,t_brokenH;
			bool yokoP=false,ptnP=false,lByokoP=false,lMyokoP=false,yokoT=false,ptnT=false,lByokoT=false,lMyokoT=false;
			int p_yoko_max_suc=0,tmp_suc=0,t_yoko_max_suc=0;
			if(ptnFLG){
				char tmp;
				for(int i=0,k=0;i<P_h;i++){
					tmp=P[i][0];
					for(k=1;k<P_w;k++){
						if(tmp!=P[i][k])	break;
					}
					if(k!=P_w){
						p_yoko_max_suc=std::max(p_yoko_max_suc,tmp_suc);
						tmp_suc=0;
						p_brokenH.reg_loc(1000*i+k);
					}else{
						tmp_suc++;
					}
				}
				p_yoko_max_suc=std::max(p_yoko_max_suc,tmp_suc);

				if(100*(p_yoko_max_suc/P_h)<=5){
					int** P_each_row_char=new int*[P_h];

					for(int i=0;i<P_h;i++){
						P_each_row_char[i]=new int[128];
						for(int k=0;k<128;k++){
							P_each_row_char[i][k]=0;
						}
						for(int k=0;k<P_w;k++){
							P_each_row_char[i][P[i][k]]++;
						}
					}
					int** P_dist_table=new int*[P_h];
					for(int i=0;i<P_h;i++){
						P_dist_table[i]=new int[128];
						for(int k=0;k<128;k++){
							P_dist_table[i][k]=0;
						}
					}
					int history_loc[128],tmp_dist,history_max,history_min;
					for(int i=0;i<P_h;i++){
						for(int k=0;k<128;k++)history_loc[k]=0;
						for(int k=0;k<P_w;k++){
							if(history_loc[P[i][k]]==0){
								history_loc[P[i][k]]=k;
							}else{
								tmp_dist=k-history_loc[P[i][k]];
								history_max=P_dist_table[i][P[i][k]]/1000;
								history_min=P_dist_table[i][P[i][k]]%1000;
								if(history_max==0||history_max<tmp_dist){
									history_max=tmp_dist;
								}
								if(history_min==0||history_min>tmp_dist){
									history_min=tmp_dist;
								}
								P_dist_table[i][P[i][k]]=1000*history_max+history_min;
								history_loc[P[i][k]]=k;
							}
						}
					}
					bool val_and_count=true,char_dist=true;
					for(int i=1,k=0;i<P_h;i++){
						for(k=0;k<128;k++){
							if(P_each_row_char[i][k]!=P_each_row_char[0][k]&&abs(P_each_row_char[i][k]-P_each_row_char[0][k])>1){
								val_and_count=false;
								break;
							}
						}
						if(k!=128)break;
					}
					bool Dist0=true,DistOther=true;
					if(val_and_count){
						int min_0=1001,max_0=-1;
						for(int i=0;i<128;i++){
							if(P_dist_table[0][i]>0){
								if(min_0==1001&&max_0==-1){
									min_0=P_dist_table[0][i]%1000;
									max_0=P_dist_table[0][i]/1000;
									if(min_0!=max_0){
										Dist0=false;
										break;
									}
								}
								if(min_0!=1001&&max_0!=-1){
									if(P_dist_table[0][i]%1000!=min_0||P_dist_table[0][i]/1000!=max_0){
										Dist0=false;
										break;
									}
								}
							}
						}
					}
					if(Dist0){
						for(int i=1;i<P_h;i++){
							for(int k=0;k<128;k++){
								if(P_dist_table[0][k]!=P_dist_table[i][k]){
									DistOther=false;
									break;
								}
							}
						}
					}
					if(val_and_count==true&&char_dist==true&&Dist0==true&&DistOther==true){
						ptnP=true;
					}
				}
				if(100*(p_yoko_max_suc/P_h)<=5&&ptnP==false){
					ptnFLG=false;
				}else{
					if(p_yoko_max_suc==P_h){
						yokoP=true;
					}else if(100*(p_yoko_max_suc/P_h)>=50){
						lByokoP=true;
					}else if(100*(p_yoko_max_suc/P_h)>=6){
						lMyokoP=true;
					}
				}
				if(ptnFLG){
					tmp_suc=0;
					for(int i=0,k=0;i<T_h;i++){
						tmp=T[i][0];
						for(k=1;k<T_w;k++){
							if(tmp!=T[i][k])	break;
						}
						if(k!=T_w){
							t_yoko_max_suc=std::max(t_yoko_max_suc,tmp_suc);
							tmp_suc=0;
							t_brokenH.reg_loc(1000*i+k);
						}else{
							tmp_suc++;
						}
					}
					t_yoko_max_suc=std::max(t_yoko_max_suc,tmp_suc);

					if(100*(t_yoko_max_suc/T_h)<=5){
						int** T_each_row_char=new int*[T_h];
						for(int i=0;i<T_h;i++){
							T_each_row_char[i]=new int[128];
							for(int k=0;k<128;k++){
								T_each_row_char[i][k]=0;
							}
							for(int k=0;k<T_w;k++){
								T_each_row_char[i][T[i][k]]++;
							}
						}
						int** T_dist_table=new int*[T_h];
						for(int i=0;i<T_h;i++){
							T_dist_table[i]=new int[128];
							for(int k=0;k<128;k++){
								T_dist_table[i][k]=0;
							}
						}

						int history_loc[128],tmp_dist,history_max,history_min;
						for(int i=0;i<T_h;i++){
							for(int k=0;k<128;k++)history_loc[k]=0;
							for(int k=0;k<T_w;k++){
								if(history_loc[T[i][k]]==0){
									history_loc[T[i][k]]=k;
								}else{
									tmp_dist=k-history_loc[T[i][k]];

									history_max=T_dist_table[i][T[i][k]]/1000;
									history_min=T_dist_table[i][T[i][k]]%1000;
									if(history_max==0||history_max<tmp_dist){
										history_max=tmp_dist;
									}
									if(history_min==0||history_min>tmp_dist){
										history_min=tmp_dist;
									}
									T_dist_table[i][T[i][k]]=1000*history_max+history_min;
									history_loc[T[i][k]]=k;
								}
							}
						}
						bool val_and_count=true;
						bool char_dist=true;
						for(int i=1,k=0;i<T_h;i++){
							for(k=0;k<128;k++){
								if(T_each_row_char[i][k]!=T_each_row_char[0][k]&&abs(T_each_row_char[i][k]-T_each_row_char[0][k])>1){
									val_and_count=false;
									break;
								}
							}
							if(k!=128)break;
						}
						bool Dist0=true;
						bool DistOther=true;
						if(val_and_count){
							int min_0=1001,max_0=-1;
							for(int i=0;i<128;i++){
								if(T_dist_table[0][i]>0){
									if(min_0==1001&&max_0==-1){
										min_0=T_dist_table[0][i]%1000;
										max_0=T_dist_table[0][i]/1000;
										if(min_0!=max_0){
											Dist0=false;
											break;
										}
									}
									if(min_0!=1001&&max_0!=-1){
										if(T_dist_table[0][i]%1000!=min_0||T_dist_table[0][i]/1000!=max_0){
											Dist0=false;
											break;
										}
									}
								}
							}
						}
						if(Dist0){
							for(int i=1;i<T_h;i++){
								for(int k=0;k<128;k++){
									if(T_dist_table[0][k]!=T_dist_table[i][k]){
										DistOther=false;
										break;
									}
								}
							}
						}

						if(val_and_count==true&&char_dist==true&&Dist0==true&&DistOther==true){
							ptnT=true;
						}
					}
					if(100*(t_yoko_max_suc/T_h)<=5&&ptnT==false){
						ptnFLG=false;
					}else{
						if(t_yoko_max_suc==T_h){
							yokoT=true;
						}else if(100*(t_yoko_max_suc/T_h)>=50){
							lByokoT=true;
						}else if(100*(t_yoko_max_suc/T_h)>=6){
							lMyokoT=true;
						}
					}
				}
			}

			if(ptnFLG){
					if((yokoP==true||lByokoP==true||lMyokoP==true)&&
						(yokoT==false&&lByokoT==false&&lMyokoT==false)){
						ptnFLG=false;
					}
					if(ptnP==true&&ptnT==false){
						ptnFLG=false;
					}
			}

			if(ptnFLG){
				if(yokoP==true){

					if(yokoT==true&&p_yoko_max_suc<=t_yoko_max_suc){
						int yoko_top=0,yoko_bottom=P_h-1;
						int top_limit=T_h-P_h,search_row,out_W_lmt=T_w-P_w;

						while(yoko_top<=top_limit){
							for(search_row=yoko_top;search_row<=yoko_bottom;search_row++){
								if(P[search_row-yoko_top][0]!=T[search_row][0])break;
							}

							if(search_row>yoko_bottom){
								for(int out_col=0;out_col<=out_W_lmt;out_col++){
									printf("%d %d\n",yoko_top,out_col);
								}
							}
							yoko_top++;
							yoko_bottom++;
						}
					}else if((lByokoT==true||lMyokoT==true)&&p_yoko_max_suc<=t_yoko_max_suc){
						int horizon_top=0,horizon_bottom=P_h-1;
						int top_limit=T_h-P_h,search_row,out_W_lmt=T_w-P_w,broken_row;


						while(horizon_top<=top_limit){
							t_brokenH.init_index();
							for(search_row=horizon_top;search_row<=horizon_bottom;search_row++){
								if(P[search_row-horizon_top][0]!=T[search_row][0])break;
								while((broken_row=t_brokenH.next_loc())!=-1){
									if(broken_row/1000==search_row){
										break;
									}
								}
							}
							if(search_row>horizon_bottom){
								for(int out_col=0;out_col<=out_W_lmt;out_col++){
									printf("%d %d\n",horizon_top,out_col);
								}
							}
							horizon_top++;
							horizon_bottom++;
						}
					}

				}else if(lByokoP == true){
					if(yokoT==true){
						//Do nothing
					}else if((lByokoT==true||lMyokoT==true)&&p_yoko_max_suc<=t_yoko_max_suc){
						int horizon_top=0,horizon_bottom=P_h-1;
						int top_limit=T_h-P_h,search_row,out_W_lmt=T_w-P_w,broken_row;
						while(horizon_top<=top_limit){
							t_brokenH.init_index();
							for(search_row=horizon_top;search_row<=horizon_bottom;search_row++){
								if(P[search_row-horizon_top][0]!=T[search_row][0])break;
								while((broken_row=t_brokenH.next_loc())!=-1){
									if(broken_row/1000==search_row){
										break;
									}
								}
							}
							if(search_row>horizon_bottom){
								for(int out_col=0;out_col<=out_W_lmt;out_col++){
									printf("%d %d\n",horizon_top,out_col);
								}
							}
							horizon_top++;
							horizon_bottom++;
						}
					}
				}else if(lMyokoP==true){
					if(yokoT==true){
						//Do nothing
					}else if((lByokoT==true||lMyokoT==true)&&p_yoko_max_suc<=t_yoko_max_suc){
						bool matchFLG;
						int broken_point,comp_count;
						for(int row=0;row<=H_lmt;row++){
							for(int col=0;col<=W_lmt;col++){
								if(T[row][col]==p00){
									t_brokenH.init_index();
									comp_count=0;
									while((broken_point=t_brokenH.next_loc())!=-1&&comp_count<100){
										if(T[row+(broken_point/1000)][col+(broken_point%1000)]!=P[broken_point/1000][broken_point%1000]){
											break;
										}
										comp_count++;
									}
									if(broken_point==-1||comp_count==100){

										bool leftMatchFLG=true;
										for(int tmp_row=0;tmp_row<P_h;tmp_row++){
											if(T[row+tmp_row][0]!=P[tmp_row][0]){
												leftMatchFLG=false;
												break;
											}
										}
										if(leftMatchFLG){
											matchFLG=true;
											for(int tmp_row=0;tmp_row<P_h;tmp_row++){
												for(int tmp_col=0;tmp_col<P_w;tmp_col++){
													if(T[row+tmp_row][col+tmp_col]!=P[tmp_row][tmp_col]){
														matchFLG=false;
														break;
													}
												}
												if(!matchFLG)break;
											}
											if(matchFLG){
												printf("%d %d\n",row,col);
											}
										}
									}
								}
							}
						}
					}
				}else if(ptnP){
					bool matchFLG;
					for(int row=0;row<=H_lmt;row++){
						for(int col=0;col<=W_lmt;col++){
							if(T[row][col]==p00){
								matchFLG=true;
								for(int tmp_row=0;tmp_row<P_h;tmp_row++){
									if(T[row+tmp_row][col]!=P[tmp_row][0]){
										matchFLG=false;
										break;
									}
								}
								if(matchFLG){
									printf("%d %d\n",row,col);
								}
							}
						}
					}
				}else{
					//omit
				}
			}else{
				bool matchFLG;

				for(int row=0;row<=H_lmt;row++){
					for(int col=0;col<=W_lmt;col++){
						if(T[row][col]==p00){
							matchFLG=true;
							for(int tmp_row=0;tmp_row<P_h;tmp_row++){
								for(int tmp_col=0;tmp_col<P_w;tmp_col++){
									if(T[row+tmp_row][col+tmp_col]!=P[tmp_row][tmp_col]){
										matchFLG=false;
										break;
									}
								}
								if(!matchFLG)break;
							}
							if(matchFLG){
								printf("%d %d\n",row,col);
							}
						}
					}
				}
			}
		}

	}else if(P_h==1&&P_w==1){
		char ch= P[0][0];
		for(int i=0;i<T_h;i++){
			for(int k=0;k<T_w;k++){
				if(T[i][k]==ch){
					printf("%d %d\n",i,k);
				}
			}
		}
	}else{
		if(t_multFLG){
			if(max_char==p00&&((tc_max)/(T_h*T_w-tc_max)>=10000)&&(t_max_char==P[0][0])){
				Loc tLoc;
				for(int row=0;row<T_h;row++){
					for(int col=0;col<T_w;col++){
						if(T[row][col]!=t_max_char){
							tLoc.reg_loc(1000*row+col);
						}
					}
				}

				int** possibilityTable=new int*[T_h];
				for(int i=0;i<T_h;i++){
					possibilityTable[i]=new int[T_w];
					for(int k=0;k<T_w;k++){
						possibilityTable[i][k]=0;
					}
				}
				tLoc.init_index();
				int del_loc=tLoc.next_loc();
				int del_left,del_right,del_top,del_floor,center_row,center_col;

				while(del_loc!=-1){
					center_row=del_loc/1000;
					center_col=del_loc%1000;

					if(0<center_col-(P_w-1)){
						del_left=center_col-(P_w-1);
					}else{
						del_left=0;
					}
					del_right=center_col;
					if(0<center_row-(P_h-1)){
						del_top=center_row-(P_h-1);
					}else{
						del_top=0;
					}
					del_floor=center_row;
					for(int i=del_top;i<=del_floor;i++){
						for(int k=del_left;k<=del_right;k++){
							possibilityTable[i][k]=-1;
						}
					}
					del_loc=tLoc.next_loc();
				}

				for(int row=0;row<=H_lmt;row++){
					for(int col=0;col<=W_lmt;col++){
						if(possibilityTable[row][col]==0)printf("%d %d\n",row,col);
					}
				}

			}else if(((T_h-P_h)*(T_w-P_w)*(P_h*P_w)<500000000)||(tc_max/(T_h*T_w-tc_max)<=1000)){

				char p_ch=P[0][0];
				bool matchFLG;

				for(int row=0;row<=H_lmt;row++){
					for(int col=0;col<=W_lmt;col++){
						if(T[row][col]==p_ch){
							matchFLG=true;
							for(int tmp_row=0;tmp_row<P_h;tmp_row++){
								for(int tmp_col=0;tmp_col<P_w;tmp_col++){
									if(T[row+tmp_row][col+tmp_col]!=P[tmp_row][tmp_col]){
										matchFLG=false;
										break;
									}
								}
								if(!matchFLG)break;
							}
							if(matchFLG){
								printf("%d %d\n",row,col);
							}
						}
					}
				}
			}else{
					int S=0,historyS;
					int top,bottom,left,right;
					int** calcTable=new int*[T_h];

					for(int i=0;i<T_h;i++){
						calcTable[i]=new int[T_w];
						for(int k=0;k<T_w;k++){
							if(T[i][k]!=P[0][0]){
								calcTable[i][k]=1;
								if(i<P_h&&k<P_w){
									S++;
								}
							}else{
								calcTable[i][k]=0;
							}
						}
					}
					if(S==0)printf("0 0\n");
					historyS=S;

					top=0,left=1,right=P_w,bottom=P_h-1;

					while(top<=H_lmt){
						while(right<T_w){
							for(int row=top;row<=bottom;row++){
								S-=calcTable[row][left-1];
							}
							for(int row=top;row<=bottom;row++){
								S+=calcTable[row][right+1];
							}
							if(S==0){
								printf("%d %d\n",top,left);
							}
							left++;
							right++;
						}

						if(bottom<H_lmt){
							for(int col=0;col<T_w;col++){
								historyS-=calcTable[top][col];
							}
							for(int col=0;col<T_w;col++){
								historyS+=calcTable[bottom+1][col];
							}

							if(historyS==0){
								printf("%d %d\n",top+1,0);
							}
						}

						top++;
						bottom++;
						left=1,right=P_w,S=historyS;
					}
			}

		}else{

			if(T[0][0]==P[0][0]){

				for(int row=0;row<=H_lmt;row++){
					for(int col=0;col<=W_lmt;col++){
						printf("%d %d\n",row,col);
					}
				}
			}
		}
	}

return 0;
}