#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <unistd.h>

using namespace std;

using strs = vector<vector<int>>;

class Befunge {
  private:
    const int dx[4] = {1, 0,-1, 0};
    const int dy[4] = {0, 1, 0,-1};

    strs code;
    vector<int> stack;

    int w, h;
    int x, y, d;

    bool lit;

    mt19937 mt;


    void push(int val);
    int pop();

    void set_out(int val);
    void set_out_s(string str);

    bool step();

  public:
    Befunge();

    void push_line(string str);
    void fill_space();

    void interpreter();

};

Befunge::Befunge(): code(), stack(), w(0), h(0), x(0), y(0), d(0), lit(false) {
  random_device rnd;
  mt.seed(rnd());

}



void Befunge::push(int val) {
  stack.push_back(val);
}

int Befunge::pop() {
  if(stack.empty())return 0;
  int val = stack.back();
  stack.pop_back();
  return val;
}


void Befunge::set_out(int val) {
  cout<<(char)val;
}

void Befunge::set_out_s(string str) {
  for(int i=0;i<(int)str.size();i++)set_out( (int)str[i] );
}


bool Befunge::step() {
  x += w+dx[d];
  y += h+dy[d];
  x %= w;
  y %= h;
  return code[y][x] == ' ';
}



void Befunge::push_line(string str) {
  vector<int> a;
  for(int i=0;i<(int)str.size();i++)a.push_back( (int)str[i] );
  code.push_back(a);
  w = max(w, (int)str.size());
  h++;
}

void Befunge::fill_space() {
  for(int i=0;i<(int)code.size();i++) {
    for(int j=(int)code[i].size();j<w;j++)code[i].push_back( (int)' ' );
  }
}


void Befunge::interpreter() {
  int a, b;
  char e;

  while(true) {

    if(lit) {
      if(code[y][x] == '"')lit = false;
      else push((int)code[y][x]);

    }else {
      switch(code[y][x]) {
        case '>':d = 0;break;
        case 'v':d = 1;break;
        case '<':d = 2;break;
        case '^':d = 3;break;
        case '_':
                 a = pop();
                 if(a)d = 2;
                 else d = 0;
                 break;
        case '|':
                 a = pop();
                 if(a)d = 3;
                 else d = 1;
                 break;
        case '?':d = mt()%4;break;
        case ' ':break;
        case '#':step();break;
        case '@':return;break;
        case '0':case '1':case '2':case '3':case '4':case '5':case '6':case '7':case '8':case '9':
                 push(code[y][x]-'0');
                 break;
        case '"':lit = true;break;
        case '&':
                 cin>>a;
                 push(a);
                 break;
        case '~':
                 cin>>e;
                 push((int)e);
                 break;
        case '.':
                 a = pop();
                 set_out_s(to_string(a));
                 set_out(' ');
                 break;
        case ',':
                 a = pop();
                 set_out(a);
                 break;
        case '+':
                 b = pop();
                 a = pop();
                 push(a+b);
                 break;
        case '-':
                 b = pop();
                 a = pop();
                 push(a-b);
                 break;
        case '*':
                 b = pop();
                 a = pop();
                 push(a*b);
                 break;
        case '/':
                 b = pop();
                 a = pop();
                 push(b?0:a/b);
                 break;
        case '%':
                 b = pop();
                 a = pop();
                 push(a%b);
                 break;
        case '`':
                 b = pop();
                 a = pop();
                 push(a>b);
                 break;
        case '!':
                 a = pop();
                 push(!a);
                 break;
        case ':':
                 a = pop();
                 push(a);
                 push(a);
                 break;
        case '\\':
                 b = pop();
                 a = pop();
                 push(b);
                 push(a);
                 break;
        case '$':
                 a = pop();
                 break;
        case 'g':
                 b = pop();
                 a = pop();
                 push(code[b][a]);
                 break;
        case 'p':
                 b = pop();
                 a = pop();
                 code[b][a] = pop();
                 break;
      }

    }

    a = x;
    b = y;
    if(lit)step();
    else while(step()) {
      if(a==x && b==y)return ;
    }

  }

}



Befunge befunge;

int main() {
  ios::sync_with_stdio(false);

  int n = 3;
  string str[] = {
"~~29*1+3*-#v_19+\"seY\",,,,@",
"           >29*1+3*-#v_19+\"seY\",,,,@",
"                     >19+\"oN\",,,@\""
  };
  
  for(int i=0;i<n;i++)befunge.push_line(str[i]);
  befunge.fill_space();

  befunge.interpreter();

  return 0;
}



Measured memory_bytes: 256