Chengcheng is building a website recently. Some of the contents of the pages come from different data records in the database, but the basic structure of the pages is the same. For example, for a page showing user information, when the user is Tom, the source code of the page is


When the user is Jerry, the source code of the web page is


There are many examples of this in websites with dynamic content. In order to simplify the work of generating web pages, Cheng felt that he needed to introduce a template generation system.
Templates are text containing special tags. The template used for generation contains only one special tag in the format {VAR}, where VAR is a variable. This tag is replaced by the value of the variable VAR when the template is generated. For example, if the variable name = Tom, then {{name}} generates Tom. The specific rules are as follows:
· Variable names are composed of upper and lower case letters, numbers and underscores (), and the first character is not a number and is not longer than 16 characters.
· Variable names are case sensitive, and Name and name are two different variables.
· The value of a variable is a string.
· If the variable in the tag is undefined, an empty string is generated, which is equivalent to deleting the tag from the template.
· Templates are not generated recursively. That is to say, if the value of a variable contains something like {VAR}, no further substitution will be made.

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

struct mde{
		string var;
		string key;
};

string mode[100];
vector<mde> modes;
vector< vector<int> > change; 
vector<int> two(2);
int main(){
	int m,n;
	int i,j,p;
	int loc,locl,locr;
	string k,v2,temp; 

	string sl="{{ ",sr=" }}";
	cin>>m>>n;
	string s1,s2,s3,v;
	getchar();
	for(i=0;i<m;i++){
		getline(cin,mode[i]);//try scanf
	}
	
	mde X;
	for(i=0;i<n;i++){
		getline(cin,v);
	
	
		loc=v.find("\"");
		k=v.substr(0,loc-1);
		v2=v.substr(loc+1,v.length()-loc-2);
		X.var=v2;
		X.key=k;
		modes.push_back(X);
	}

	
	for(i=0;i<m;i++){//Line i 
		temp=mode[i];
		while(strstr(temp.c_str(),sl.c_str())!=NULL&&strstr(temp.c_str(),sr.c_str())!=NULL){
			int l=0;
			int r=0;
			//Look for the left first. 
			l=temp.find("{{ ");

			//Find the left and the first right. 
			r=temp.find(" }}",l);

			int len=r-l-3;
			s1=temp.substr(0,l);
			s2=temp.substr(l+3,len);
			s3=temp.substr(r+3,temp.length()-r-3);
			
			for(j=0;j<n;j++){//Find something to replace 
				if(strcmp(s2.c_str(),modes[j].key.c_str())==0){
					two[0]=j;//Record the location of the VAR to be replaced in the VAR vector
					two[1]=l;//Record the starting position to be replaced
					change.push_back(two); 
					break;
				}
			}
			temp=s1+s3;
		}
		for(int p=0;p<change.size();p++){
			temp=temp.replace(change[p][1],0,modes[change[p][0]].var);
			for(int q=p+1;q<change.size();q++){
				change[q][1]+=strlen(modes[change[p][0]].var.c_str());
			}
		}
		mode[i]=temp;
		change.clear();
	}
	for(i=0;i<m;i++){
		cout<<mode[i]<<endl;
	}
	return 0;
}