#!/usr/bin/perl
use strict;
use warnings;
;$  "=q%ef%;$_  =q~my($i,$  x,$y,$p)=(  0,0,0,pop|  |5);my$r=2
<<  $p      ;m  y@      i=  ma      p[  (1      )x  $r      ,2
],1..$  r;subi  {$i[$x  ][$y]-  -}i;su  bp{((1  <$_[0]  ?$y:$x
        )-          =1          -(          $_          [0
]&1)*2  ,i)for  -1,1}s  ubf{my  ($  p,$f)=  @_  ;$p--;  my@m=(
$f  ,3      -$  f,      1-  $f  );  my  @o  =(  3-  $f      ,$
f,  $f,$f-2)if  $p>0;($_&=  3)  for@o,  @m;@o&  &f  ($p,pop@o)
,@                          m&                  &p
(pop@m  )while(@o||@m)  }f$p,(  $p&1)*  2;subb  {y  ,y4102,b#\
    n,  ;p          ri  nt      }m  ap  {b  fo  r@  $_      }@
i~;y~   \n~~d;  ;s&b&b  &g;$;=  1;  eval;#  %$  _+28;$  x-=$y;
my          ($  pi          )=  '3          .1          41
59  26535'  ;$  ,=  2*2**$  [;  ;my@b=  map[5x  $pi],1  ..$[;s
{}  {q  %S  {$  b[  $x  ][  $y      ]=  0}      S;  su      bp
{($_[0  ]>1?$y  :$x+=-  1+$_[0  ]^2*2,  S)for(0,1)  }suba{($l,
                                $d
)=@_;$  l--;@m  =map$_  *4,5-$  d,3-$d  ,$d;@h=map  $_*4,$d+2,
$d  ,$  d,  3-  $d  if  $l  >0      ;{  a(      $l  ,s      hi
ft  @h)if@  h;  @m  &&p(sh  if  t@m);(  @m+@h)  &&redo  }}a$l,
$l          ^2  *2          ;p  ri          nt          @$
_,$/fo  r@b($x  ,$y,$c  )=qw/0  0*  /;$l=s  hi  ft||4;  $r=$s*
    2*  *$          l;  @b      =m  ap  [(  ''  )x  $r      ],
1..$r;  for(0,1){eval[  qw/$x-  -$x++$  y--$y+  +/  ]->[i$_[0]
];                          $b                  [$
x]  [$y]=$c;}@  m=split//,  [q  w/rdll  urdruu  ld  /]->[i$d];
@h  =s      pl  it      //  ,[  qw  /u  ll  dd  rr  ul      uu
rrddl/  ]->[i$  d]if$l  >0;@m=  sp  lit//,  {q  w/lrdl  rlurud
        ru          du          ld          /}          ->
{$d};@  m=spli  t//,su  bstr'r  dllurd  ruuld'  ,3*i$d  ,3;@h=
sp  li      t/  ,{      qw  /l      ul  ld      rd  rr      uu
lu  urdrddl/}-  >{$d}if$l<  7;@m=split  //,substr'  ulldd'%}e;