Identity Decode

Time Limit: 1 Second    Memory Limit: 32768 KB

WishingBone met a ppmm in school today. He is really enthusiastic to know her name. The only information he's got is her school identity which is on her school bag. At night, WishingBone broke into the office of the principal, and found a long long list of all the students' names. It reads:

1: WishingBone ID: green_bone blue_bone red_bone
2: WishingMM ID: blue_bone green_bone red_bone
3: WishingFish ID: green_bone red_bone blue_bone
4: WashingBone ID: red_bone green_bone blue_bone

And he remembers the ppmm's ID is white_bone blue_bone greed_bone. Of course, he did not want to read the list through to find this ID. Well, fortunately, he found a piece of code in the recycled bin that the principle used to generate those ID's. This program reads in m and n, where m is the number of color of bones and n is the length of the ID. Then it reads in a list of colors and generates the list of possible ID's. Since WishingBone is quite poor at programming, he resorts to your help.

Input

Input consists of multiple tests. Each test starts with a line of m and n (0 < n <= m <= 12), and a list of m distinct names of colors on the next line, separated by a single space. Names are made up of up to 30 upper, lower Latin characters and the '_' character. The third line of a test contains a sequence of n names of colors, which is the school identity of the ppmm.

Process to the end of file. There will be no more than 10000 tests.

Output

For each test in the input, output a single integer - the line on which to find her name.

Sample Input

4 3
red_bone blue_bone green_bone white_bone
red_bone green_bone blue_bone
4 3
red_bone blue_bone green_bone white_bone
white_bone blue_bone green_bone

Sample Output

4
21
 

The Program WishingBone found in the pricipal's office:

#include 
#define MAXN 12

void FAINT(int m,int n,int l,int a[MAXN][3],int t,char name[MAXN][50],int& c){
  int i;
  if (!t--)
    for (cout<<++c<<": ",i=0;i       cout<   else
    for (i=0;i       if (!a[i][2])
        a[t][a[i][2]=1]=a[i][0],FAINT(m,n,l,a,t,name,c),a[i][2]=0;
}

void faint(int m,int n,int l,int a[MAXN][3],int t,char name[MAXN][50],int& c){
  int i;
  if (t==n)
    FAINT(m,n,l,a,n,name,c);
  else
    for (i=l;i       a[t][0]=i,faint(m,n,i+1,a,t+1,name,c);
}

int main(){
  char name[MAXN][50];
  int a[MAXN][3],m,n,i,c=0;
  cin>>m>>n;
  for (i=0;i     cin>>name[i],a[i][2]=0;
  faint(m,n,0,a,0,name,c);
  return 0;
}

const maxn=12;
type words=string[50];
var n,m,i:integer;
    name:array [1..maxn] of words;
    a,p:array [1..maxn] of integer;
    yes:array [1..maxn] of boolean;
    g:longint;
procedure getwords(var s:words);
var ch:char;
function rec:boolean;
begin
  rec:=(ch='_') or ('A'<=ch) and (ch<='Z') or ('a'<=ch) and (ch<='z');
end;
begin
  s:='';repeat read(ch);until rec;
  repeat s:=s+ch;read(ch);
  until not rec;
end;
procedure print(l:integer);
var i:integer;
begin
  if l=0 then
    begin
      inc(g);write(g,':');
      for i:=1 to m do write(' ',name[p[a[i]]]);
      writeln;
    end else
  for i:=1 to m do if yes[i] then
    begin yes[i]:=false;a[l]:=i;print(l-1);yes[i]:=true;end;
end;
procedure faint(nn,mm:integer);
begin
  if mm=0 then print(m) else
    begin
      p[m-mm+1]:=n-nn+1;
      faint(nn-1,mm-1);
      if nn>mm then faint(nn-1,mm);
    end;
end;
begin
  read(n,m);
  for i:=1 to n do getwords(name[i]);
  fillchar(yes,sizeof(yes),1);g:=0;
  faint(n,m);
end.

Submit

Source: WishingBone's Contest #1