using System;using S=System.String;using System.Collections.Generic;partial class M{Dictionary<S,S>d=new Dictionary<S,S>();List<S>e=new List<S>();int p=9,m=999,x,y,z,u,v,i,j;S a="@",w="#",f=".",s=">",c;Random r=new Random();M(int k,int l,int h){u=m*l;while(i++<u){e.Add((r.Next(m)-499)+a+(r.Next(m)-499));d[e[e.Count-1]]="M";}d[X]=a;while(k>0){u=x;v=y;x=k>2&&k<20?x-1:k>12?x+1:x;y=k%2>0&&k%10!=0?y-1:k%2==0&&k%10!=0?y+1:y;c=T(X);if(e.Contains(X)){e.Remove(X);d[X]=f;}R();if(c==s){d.Clear();e.Clear();new M(1,l+1,h);return;}if(c!=f){x=u;y=v;}d[u+a+v]=f;d[X]=a;for(z=0;z<e.Count;z++){i=U(e[z],0);j=U(e[z],1);u=i<x?i+1:i>x?i-1:i;v=j<y?j+1:j>y?j-1:j;c=T(u+a+v);if(c==f){e[z]=u+a+v;d[e[z]]=d[i+a+j];d[i+a+j]=f;}if(c==a)h--;}if(h<1)return;z=p*2-1;for(j=0;j<z;j++){for(i=0;i<z;i++){c=T((i-p+x)+a+(j-p+y));W(c,c==w?l:0);}L();}L(l+f+h);k=I;}}S X{get{return x+a+y;}}S T(S c){return d.ContainsKey(c)?d[c]:d[c]=r.Next(m*p)<5?s:r.Next(9)<7?f:w;}int U(S c,int l){return int.Parse((c.Split('@'))[l]);}static void Main(){new M(1,1,9);}}