/* run the TM from a departure config (cells given) up to N steps; print HALT step or RUN */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc,char**argv){ const char *L=argv[1],*R=argv[2]; long long N=atoll(argv[3]);
  /* A..F = 0..5 ; transitions of 1RB0LC_1LA0RE_0RD1LF_1LC1LB_0LD0RB_0LA--- */
  int W[6][2]={{1,0},{1,0},{0,1},{1,1},{0,0},{0,-1}}; int M[6][2]={{1,-1},{-1,1},{1,-1},{-1,-1},{-1,1},{-1,0}}; int Q[6][2]={{1,2},{0,4},{3,5},{2,1},{3,1},{0,-1}};
  long long size=1<<24; unsigned char *t=calloc(size,1); long long pos=size/2; long long n=0;
  long long lp=pos-strlen(L); for(size_t i=0;i<strlen(L);i++) t[lp+i]=L[i]-'0'; for(size_t i=0;i<strlen(R);i++) t[pos+i]=R[i]-'0';
  int q=4; while(n<N){ int s=t[pos]; if(q==5&&s==1){ printf("HALT %lld\n",n); return 0;} t[pos]=W[q][s]; pos+=M[q][s]; q=Q[q][s]; n++; if(pos<2||pos>size-2){printf("OOB %lld\n",n);return 0;} }
  printf("RUN %lld\n",n); return 0; }