#include <iostream>
#include <fstream>

using namespace std;

int v[10][250001];
int nr_v;
int pos;

char a[100];

inline void trans(const char *a, int &i)
{
	i=0;
	for (int i=0; a[i]!=NULL; ++i)
		i=i*5<<1+(a[i]-'0');
}

void solve()
{
	fstream f("stramosi.in", ios::in);
	fstream g("stramosi.out", ios::out);
	f>>a;
	trans(a, nr_v);
	f>>a;
	trans(a, pos);
	for (int i=1; i<=nr_v; ++i)
	{
		f>>a;
		//trans(a, v[1][i]);
		for (int k=0; a[k]!='\0'; ++i)
			v[1][i]=v[1][i]*10+a[k]-'0';
	}

	for (int j=2; j<=8; ++j)
		for (int i=1; i<=nr_v; ++i)
			v[j][i]=v[1][v[j-1][i]];

	int p,q;

	for (int i=1; i<=pos; ++i)
	{
		//f>>q>>p;
		f>>a;
		trans(a, q);
		f>>a;
		trans(a, p);
		if (p<=8)
			g<<v[p][q]<<"\n";
		else
		{
			while (p>8)
			{
				q=v[8][q];
				p=p-8;
			}
			g<<v[p][q]<<"\n";
		}
	}
	f.close();
	g.close();
}

int main()
{
	solve();
	return 0;
}