Esoteric languages are pretty hard to program, but it's fairly interesting to write interpreters for them!

Your task is to write a method which will interpret Befunge-93 code! Befunge-93 is a language in which the code is presented not as a series of instructions, but as instructions scattered on a 2D plane; your pointer **starts at the top-left corner** and defaults to **moving right** through the code. Note that the instruction pointer **wraps** around the screen! There is a singular stack which we will assume is unbounded and only contain integers. While Befunge-93 code is supposed to be restricted to 80x25, you need not be concerned with code size. Befunge-93 supports the following instructions (from [Wikipedia](https://en.wikipedia.org/wiki/Befunge)):

- `0-9` Push this number onto the stack.
- `+` Addition: Pop `a` and `b`, then push `a+b`.
- `-` Subtraction: Pop `a` and `b`, then push `b-a`.
- `*` Multiplication: Pop `a` and `b`, then push `a*b`.
- `/` Integer division: Pop `a` and `b`, then push `b/a`, rounded down. If `a` is zero, push zero.
- `%` Modulo: Pop `a` and `b`, then push the `b%a`. If `a` is zero, push zero.
- `!`   Logical NOT: Pop a value. If the value is zero, push `1`; otherwise, push zero.
- ``` ` ``` (backtick) Greater than: Pop `a` and `b`, then push `1` if `b>a`, otherwise push zero.
- `>` Start moving right.
- `<` Start moving left.
- `^` Start moving up.
- `v` Start moving down.
- `?` Start moving in a random cardinal direction.
- `_` Pop a value; move right if `value = 0`, left otherwise.
- `|` Pop a value; move down if `value = 0`, up otherwise.
- `"` Start string mode: push each character's ASCII value all the way up to the next `"`.
- `:` Duplicate value on top of the stack. If there is nothing on top of the stack, push a `0`.
- `\` Swap two values on top of the stack. If there is only one value, pretend there is an extra `0` on bottom of the stack.
- `$` Pop value from the stack and discard it.
- `.` Pop value and output as an integer.
- `,` Pop value and output the ASCII character represented by the integer code that is stored in the value.
- `#` Trampoline: Skip next cell.
- `p` A "put" call (a way to store a value for later use). Pop `y`, `x` and `v`, then change the character at the position `(x,y)` in the program to the character with ASCII value `v`.
- `g` A "get" call (a way to retrieve data in storage). Pop `y` and `x`, then push ASCII value of the character at that position in the program.
- `@` End program.
- ` ` (i.e. a space)    No-op. Does nothing.

The above list is slightly modified: you'll notice if you look at the Wikipedia page that we do not use the user input instructions and dividing by zero simply yields zero.

Here's an example:

```
>987v>.v
v456<  :
>321 ^ _@
```

will create the output `123456789`.

So what you must do is create a function such that when you pass in the Befunge code, the function returns the output that would be generated by the code. So, for example:

```
"123456789".equals(new BefungeInterpreter().interpret(">987v>.v\nv456<  :\n>321 ^ _@")
```

This test case will be added for you.

Difficulty: interview

Starter code:

def interpret(code):
	

Solutions:
from random import choice

def interpret(code):
    code = [list(l) for l in code.split('\n')]
    x, y = 0, 0
    dx, dy = 1, 0
    output = ''
    stack = []
    string_mode = False
    
    while True:
        move = 1
        i = code[y][x]
        
        if string_mode:
            if i == '"':
                string_mode = False
            else:
                stack.append(ord(i))
        else:
        
            if i.isdigit(): stack.append(int(i))
            elif i == '+': stack[-2:] = [stack[-2] + stack[-1]]
            elif i == '-': stack[-2:] = [stack[-2] - stack[-1]]
            elif i == '*': stack[-2:] = [stack[-2] * stack[-1]]
            elif i == '/': stack[-2:] = [stack[-2] and stack[-2] / stack[-1]]
            elif i == '%': stack[-2:] = [stack[-2] and stack[-2] % stack[-1]]
            elif i == '!': stack[-1] = not stack[-1]
            elif i == '`': stack[-2:] = [stack[-2] > stack[-1]]
            elif i in '><^v?':
                if i == '?':   i = choice('><^v')
                if i == '>':   dx, dy =  1,  0
                elif i == '<': dx, dy = -1,  0
                elif i == '^': dx, dy =  0, -1
                elif i == 'v': dx, dy =  0,  1
            elif i == '_': dx, dy = (-1 if stack.pop() else 1), 0
            elif i == '|': dx, dy = 0, (-1 if stack.pop() else 1)
            elif i == '"': string_mode = True
            elif i == ':': stack.append(stack[-1] if stack else 0)
            elif i == '\\': stack[-2:] = stack[-2:][::-1]
            elif i == '$': stack.pop()
            elif i == '.': output += str(stack.pop())
            elif i == ',': output += chr(stack.pop())
            elif i == '#': move += 1
            elif i == 'p':
                ty, tx, tv = stack.pop(), stack.pop(), stack.pop()
                code[ty][tx] = chr(tv)
            elif i == 'g':
                ty, tx = stack.pop(), stack.pop()
                stack.append(ord(code[ty][tx]))
            elif i == '@':
                return output
        
        for _ in range(move):
            x = (x + dx) % len(code[y])
            y = (y + dy) % len(code)

import random
class Interpretor(object):
    """
    0-9 Push this number onto the stack.
    " Start string mode: push each character's ASCII value all the way up to the next ".
    """

    def __init__(self, lines):
        self.code = [list(line) for line in lines.split('\n')]
        push = lambda a: self.stack.append(a)
        
        self.no_parameter_ops = {
            '>': lambda: self.change_dir(1,0),
            '<': lambda: self.change_dir(-1,0),
            '^': lambda: self.change_dir(0,-1),
            'v': lambda: self.change_dir(0,1),
            '?': lambda: self.change_dir(*random.choice([[1,0], [-1,0], [0,-1], [0,1]])),
            '#': self.move,
            ' ': lambda: None,
            '@': self.stop,
            '"': self.toggle_string
        }
        
        self.one_parameter_ops = {
            '!': lambda a: push(1 if a == 0 else 0),
            '_': lambda a: self.change_dir(1,0) if a == 0 else self.change_dir(-1,0),
            '|': lambda a: self.change_dir(0,1) if a == 0 else self.change_dir(0,-1),
            ':': lambda a: push(0) if a is None else [push(a), push(a)],
            '$': lambda a: None,
            '.': lambda a: self.output.append(a),
            ',': lambda a: self.output.append(chr(a))
        }
    
        self.two_parameter_ops = {
            '+': lambda a,b: push(b+a),
            '-': lambda a,b: push(b-a),
            '*': lambda a,b: push(a*b),
            '/': lambda a,b: push(0 if a == 0 else b/a),
            '%': lambda a,b: push(0 if a == 0 else b%a),
            '`': lambda a,b: push(1 if b > a else 0),
            '\\': lambda a,b: [push(a), push(0)] if b is None else [push(a), push(b)],
            'g': lambda y,x: push(ord(self.code[y][x]))
        }
        
        self.tri_parameter_ops = {
            'p': self.put
        }
    
    def put(self,y,x,v): self.code[y][x] = chr(v)
    def stop(self): self.running = False
    def change_dir(self, nx, ny): self.dx, self.dy = nx, ny
    def toggle_string(self): self.string = not self.string
    def move(self):
        self.x += self.dx
        self.y += self.dy
        
    def interpret(self):
        self.stack = []
        self.output = []
        self.x, self.y = 0, 0
        self.dx, self.dy = 1,0
        self.running = True
        self.string = False
        
        pop = lambda: self.stack.pop() if self.stack else None
        
        while self.running:
            self.y = self.y % len(self.code)
            self.x = self.x % len(self.code[self.y])
            token = self.code[self.y][self.x]
            
            if self.string and token != "\"":     self.stack.append(ord(token))
            elif token in self.no_parameter_ops:  self.no_parameter_ops[token]()
            elif token in self.one_parameter_ops: self.one_parameter_ops[token](pop())
            elif token in self.two_parameter_ops: self.two_parameter_ops[token](pop(),pop())
            elif token in self.tri_parameter_ops: self.tri_parameter_ops[token](pop(),pop(),pop())
            elif token in "0123456789":           self.stack.append(int(token))
            
            self.move()
        return ''.join(str(x) for x in self.output)

def interpret(code):
    interpretor = Interpretor(code)
    return interpretor.interpret()

from random import choice

DIR = (1, 0), (-1, 0), (0, 1), (0, -1)
def interpret(code):
    grid, stack, out, direction = [*map(list, code.splitlines())], [], '', DIR[0]
    x = y = smode = value = 0
    while True:
        value, jump = grid[y][x], 1
        if value is '"':               smode  = not smode
        elif smode or value.isdigit(): stack += [(int, ord)[smode](value)]
        elif value in '+-*/%':         stack += [eval(str(stack.pop(~1)) + value + str(stack.pop()))]
        elif value in '!':             stack += [not stack.pop()]
        elif value in '`':             stack += [stack.pop() < stack.pop()]
        elif value in ':':             stack += [stack and stack[-1] or 0]
        elif value in '\\':            stack += [len(stack) > 1 and stack.pop(-2) or 0]
        elif value in 'g':             stack += [ord(grid[stack.pop()][stack.pop()])]
        elif value in 'p':             grid[stack.pop()][stack.pop()] = chr(stack.pop(-3))
        elif value in '$':             stack.pop()
        elif value in '.,':            out += (str, chr)[value is ','](+stack.pop())
        elif value in '?':             direction = choice(DIR)
        elif value in '_|':            direction = DIR[(value is '|') * 2 + bool(stack.pop())]
        elif value in '><v^':          direction = DIR['><v^'.index(value)]
        elif value in '#':             jump = 2
        elif value in '@':             return out
        x, y = x + direction[0] * jump, y + direction[1] * jump

import random

def const(n):
    return lambda itp: itp.push(n)

def unary(f):
    return lambda itp: itp.push(f(itp.pop()))

def binary(f):
    return lambda itp: itp.push(f(itp.pop(), itp.pop()))

def direction(x, y):
    return lambda itp: itp.set_vpc(x, y)

def dup(itp):
    x = itp.pop()
    itp.push(x)
    itp.push(x)

def swap(itp):
    x = itp.pop()
    y = itp.pop()
    itp.push(x)
    itp.push(y)

opcodes = {
    '+': binary(lambda a, b: b + a),
    '-': binary(lambda a, b: b - a),
    '*': binary(lambda a, b: b * a),
    '/': binary(lambda a, b: b / a),
    '%': binary(lambda a, b: b % a),
    '!': unary(lambda a: not a),
    '`': binary(lambda a, b: b > a),
    
    '>': direction(1, 0),
    '<': direction(-1, 0),
    'v': direction(0, 1),
    '^': direction(0, -1),
    
    '?': lambda itp: itp.set_vpc(*random.choice(((1, 0), (-1, 0), (0, 1), (0, -1)))),
                          
    '_': lambda itp: itp.set_vpc((-1)**(itp.pop() != 0), 0),
    '|': lambda itp: itp.set_vpc(0, (-1)**(itp.pop() != 0)),
    
    ':': dup,
    '\\': swap,
    
    '$': lambda itp: itp.pop(),
    '.': lambda itp: itp.output(str(itp.pop())),
    ',': lambda itp: itp.output(chr(itp.pop())),
    
    'p': lambda itp: itp.put(itp.pop(), itp.pop(), itp.pop()),
    'g': lambda itp: itp.push(itp.get(itp.pop(), itp.pop())),
    
    '#': lambda itp: itp.advance(),
    '@': lambda itp: itp.end(), 
    ' ': lambda itp: None,
}

for i in range(10):
    opcodes[str(i)] = const(i)

class Interpreter:
    def __init__(self, code):
        self.mem = [list(l) for l in code.split('\n')]
        self.stack = []
        self.pc = 0, 0
        self.vpc = 1, 0
        self.obuf = []
        self.ended = False
        self.stringmode = False
    
    def run(self):
        while not self.ended:
            x, y = self.pc
            op = self.mem[y][x]
        
            if op == '"':
                self.stringmode = not self.stringmode
            elif self.stringmode:
                self.push(ord(op))
            else:
                opcodes[op](self)
        
            self.advance()
    
    def advance(self):
        x, y = self.pc
        vx, vy = self.vpc
        y = (y + vy) % len(self.mem)
        x = (x + vx) % len(self.mem[y])
        self.pc = x, y
    
    def set_vpc(self, x, y):
        self.vpc = x, y
    
    def push(self, x):
        self.stack.append(int(x))
    
    def pop(self):
        try:
            return self.stack.pop(-1)
        except IndexError:
            return 0
    
    def output(self, s):
        self.obuf.append(s)

    def end(self):
        self.ended = True

    def get(self, y, x):
        return ord(self.mem[y][x])

    def put(self, y, x, n):
        self.mem[y][x] = chr(n)

def interpret(code):
    itp = Interpreter(code)
    
    itp.run()
    
    return ''.join(itp.obuf)

import random

def interpret(code):
    output = ""
    coordinates = code.split("\n")
    coordinate = [list(row) for row in coordinates]
    stack = []
    x = 0 
    y = 0
    dx = 1
    dy = 0
    a = ""
    temp=1
    ascii_code = 0
    opened = False
    skip_next = False
    
    while True:
        command = coordinate[y][x]
        if skip_next:
            skip_next = False
            x += dx
            y += dy
            continue
        elif command.isnumeric():
            stack.append(int(command))
        elif command == '>':
            dx = 1
            dy = 0
        elif command == '<':
            dx = -1
            dy = 0
        elif command == '^':
            dx = 0
            dy = -1
        elif command == 'v':
            dx = 0
            dy = 1
        elif command == '?':
            dx = random.randint(-1,1)
            if dx != 0:
                dy = 0
            else:
                dy = random.choice([-1, 1])
        elif command == '"':
            opened = not opened
        elif opened:
            stack.append(ord(command))
        elif command == "+":
            a, b = stack.pop(), stack.pop()
            stack.append(a + b)
        elif command == "-":
            a, b = stack.pop(), stack.pop()
            stack.append(b - a)
        elif command == "*":
            a, b = stack.pop(), stack.pop()
            stack.append(a * b)
        elif command == "/":
            a, b = stack.pop(), stack.pop()
            stack.append(int(b / a) if a != 0 else 0)
        elif command == "%":
            a, b = stack.pop(), stack.pop()
            stack.append(b % a if a != 0 else 0)
        elif command == "!":
            if int(stack[-1]) == 0:
                stack[-1] = 1
            else:
                stack[-1] = 0
        elif command == "`":
            a, b = stack.pop(), stack.pop()
            if b > a:
                stack.append(1)
            else:
                stack.append(0)
        elif command == "_":
            if stack.pop() == 0:
                dx = 1
                dy = 0
            else:
                dx = -1
                dy = 0
        elif command == "|":
            if stack.pop()  == 0:
                dx = 0
                dy = 1
            else:
                dx = 0
                dy = -1
        elif command == ":":
            if len(stack) == 0:
                stack.append(0)
            else:
                stack.append(stack[-1])
        elif command == "\\":
            if len(stack) < 2:
                stack.append(0)
            else:
                a = stack[-1]
                stack[-1] = stack[-2]
                stack[-2] = a
        elif command == "$":
            if len(stack) != 0:
                stack.pop()
        elif command == ".":
            if len(stack) !=0:
                output += str(stack.pop())
        elif command == ",":
            if len(stack) !=0:
                ascii_code = stack[-1]
                output += chr(ascii_code)
            stack.pop()
        elif command == "#":
            skip_next = True
        elif command == "p":
            y1, x1, v = stack.pop(), stack.pop(), stack.pop()
            coordinate[y1][x1] = chr(v)
        elif command == "g":
            y1, x1 = stack.pop(), stack.pop()
            stack.append(ord(coordinate[y1][x1]))
        elif command == '@':
            break
        x += dx
        y += dy
    return output

import random

directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]


class Befunge93Instance:
    def __init__(self, code, step_limit=9999):
        self.code = [[i for i in line] for line in code.split('\n')]  # code can be mutated so can't leave as string
        for line in code.split('\n'):
            print(line)
        self.head = [0, 0]  # current execution point
        self.stack = []
        self.direction = directions[0]
        self.output = ''
        self.string_mode = False
        self.steps = 0
        self.step_limit = step_limit

    def get_instr(self):
        try:
            return self.code[self.head[0]][self.head[1]]
        except IndexError:
            print(('head out of range: {}'.format(self.head)))
            return 0

    def set_direction(self, direction_index):
        self.direction = directions[direction_index]

    def advance_head(self):
        self.head[0] += self.direction[0]
        self.head[1] += self.direction[1]

    # return 0 if empty
    def pop_stack(self) -> int:
        try:
            return self.stack.pop()
        except IndexError:
            return 0

    # "singular stack which we will assume is unbounded and only contain integers"
    def push_stack(self, item):
        try:
            self.stack.append(int(item))
        except ValueError:
            self.stack.append(int(ord(item)))  # ascii to int

    def operation(self, op):
        try:
            a = self.pop_stack()
            b = self.pop_stack()
            self.stack.append(op(a, b))
        except ZeroDivisionError:
            self.stack.append(0)

    def print_status(self):
        print()
        print(('{} output({})'.format(self.steps, self.output)))
        print((self.stack))
        print(('head {} dir {} instr {}'.format(self.head, self.direction, self.get_instr())))

    def exec_instr(self) -> bool:
        self.steps += 1

        if self.steps > self.step_limit:
            return False

        instr = self.get_instr()
        #self.print_status()

        if self.string_mode:
            if instr == '\"':
                self.string_mode = False
            else:
                self.push_stack(instr)
            self.advance_head()
            return True

        if instr in '0123456789':
            self.stack.append(int(instr))
        elif instr == '+':
            self.operation(lambda a, b: a + b)
        elif instr == '-':
            self.operation(lambda a, b: b - a)
        elif instr == '*':
            self.operation(lambda a, b: a * b)
        elif instr == '/':
            self.operation(lambda a, b: b // a)
        elif instr == '%':
            self.operation(lambda a, b: b % a)
        elif instr == '!':
            self.push_stack(not self.pop_stack())
        elif instr == '`':
            self.operation(lambda a, b: int(b > a))
        elif instr in '><v^':
            self.set_direction('><v^'.index(instr))
        elif instr == '?':
            self.set_direction(random.randint(0, 3))
        elif instr == '_':
            if self.pop_stack() == 0:
                self.set_direction(0)
            else:
                self.set_direction(1)
        elif instr == '|':
            if self.pop_stack() == 0:
                self.set_direction(2)
            else:
                self.set_direction(3)
        elif instr == '\"':
            self.string_mode = True
        elif instr == ':':  # duplicate top value
            try:
                self.stack.append(self.stack[-1])
            except IndexError:
                self.stack.append(0)
        elif instr == '\\':  # swap top of stack
            try:
                self.stack[-1], self.stack[-2] = self.stack[-2], self.stack[-1]
            except IndexError:
                self.stack.append(0)
        elif instr == '$':
            self.pop_stack()
        elif instr == '.':  # int
            self.output += str(self.pop_stack())
        elif instr == ',':
            self.output += chr(self.pop_stack())  # int code to ascii char, 10 = \n, etc
        elif instr == '#':
            self.advance_head()
        elif instr == 'p':  # put
            x = self.pop_stack()
            y = self.pop_stack()
            value = self.pop_stack()
            self.code[x][y] = chr(value)  # int code to ascii char, 10 = \n, etc
            # print(self.code[x])
        elif instr == 'g':  # get
            x = self.pop_stack()
            y = self.pop_stack()
            self.push_stack(ord(self.code[x][y]))  # ascii char to int code
        elif instr == '@':  # end
            return False

        self.advance_head()
        return True

    def run(self):
        while self.exec_instr():
            pass


def interpret(code):
    interpreter = Befunge93Instance(code)
    interpreter.run()
    return interpreter.output


from math import floor
import random
def interpret(s):
    s,j,k = [[j for j in i] for i in s.splitlines()],0,-1
    direction,stack,output = 'right',[],[]
    while 1:
        if direction == "right" : k += 1
        elif direction == "left" : k -= 1
        elif direction == "up" : j -= 1
        elif direction == "down" : j += 1
        i = s[j][k]
        if i in "+-*/%`g" :     a,b = stack.pop(),stack.pop()
        if i.isdigit() :        stack.append(int(i))
        elif i == '+' :         stack.append(a + b)
        elif i == '-' :         stack.append(b - a)
        elif i == '*' :         stack.append(a * b)
        elif i == '/' :         stack.append(0 if not a else int(floor(b / a)))
        elif i == '%' :         stack.append(0 if not a else b % a)
        elif i == '!' :         stack.append(1 if not stack.pop() else 0)
        elif i == '`' :         stack.append(1 if b > a else 0)
        elif i == '>' :         direction = 'right'
        elif i == "<" :         direction = 'left'
        elif i == "^" :         direction = 'up'
        elif i == 'v' :         direction = 'down'
        elif i == '?' :         direction = random.choice(['right', 'left', 'down', 'up'])
        elif i == '_' :         direction = 'right' if not stack.pop() else 'left'
        elif i == '|' :         direction = 'down' if not stack.pop()else 'up'
        elif i == ':' :         stack.append(0 if not stack else stack[-1])
        elif i == '$' :         stack.pop()
        elif i == '.' :         output.append(stack.pop())
        elif i == ',' :         output.append(chr(stack.pop()))
        elif i == 'p' :         y,x,v = stack.pop(),stack.pop(),stack.pop() ; s[y][x] = chr(v)
        elif i == 'g' :         stack.append(ord(s[a][b]))
        elif i == '\\':
          if len(stack) == 1 : stack.insert(0, 0)
          else :               stack[-1], stack[-2] = stack[-2], stack[-1]
        if i == '#':
            if direction == 'right' : k += 1
            elif direction == 'left': k -= 1
            elif direction == 'up' :  j -= 1
            elif direction == 'down': j += 1
        if i == '"':
            k += (1 if direction =='right' else -1)
            while s[j][k] != '"':
                stack.append(ord(s[j][k])) ; k += (1 if direction =='right' else -1)
        if i == '@' :           break
    return "".join(map(str,output))

from random import choice
#题目太复杂,跳过这个题
def interpret(code):
    code = [list(l) for l in code.split('\n')]
    x, y = 0, 0
    dx, dy = 1, 0
    output = ''
    stack = []
    string_mode = False
    
    while True:
        move = 1
        i = code[y][x]
        
        if string_mode:
            if i == '"':
                string_mode = False
            else:
                stack.append(ord(i))
        else:
        
            if i.isdigit(): stack.append(int(i))
            elif i == '+': stack[-2:] = [stack[-2] + stack[-1]]
            elif i == '-': stack[-2:] = [stack[-2] - stack[-1]]
            elif i == '*': stack[-2:] = [stack[-2] * stack[-1]]
            elif i == '/': stack[-2:] = [stack[-2] and stack[-2] / stack[-1]]
            elif i == '%': stack[-2:] = [stack[-2] and stack[-2] % stack[-1]]
            elif i == '!': stack[-1] = not stack[-1]
            elif i == '`': stack[-2:] = [stack[-2] > stack[-1]]
            elif i in '><^v?':
                if i == '?':   i = choice('><^v')
                if i == '>':   dx, dy =  1,  0
                elif i == '<': dx, dy = -1,  0
                elif i == '^': dx, dy =  0, -1
                elif i == 'v': dx, dy =  0,  1
            elif i == '_': dx, dy = (-1 if stack.pop() else 1), 0
            elif i == '|': dx, dy = 0, (-1 if stack.pop() else 1)
            elif i == '"': string_mode = True
            elif i == ':': stack.append(stack[-1] if stack else 0)
            elif i == '\\': stack[-2:] = stack[-2:][::-1]
            elif i == '$': stack.pop()
            elif i == '.': output += str(stack.pop())
            elif i == ',': output += chr(stack.pop())
            elif i == '#': move += 1
            elif i == 'p':
                ty, tx, tv = stack.pop(), stack.pop(), stack.pop()
                code[ty][tx] = chr(tv)
            elif i == 'g':
                ty, tx = stack.pop(), stack.pop()
                stack.append(ord(code[ty][tx]))
            elif i == '@':
                return output
        
        for _ in range(move):
            x = (x + dx) % len(code[y])
            y = (y + dy) % len(code)

from random import randint, seed
def interpret(code):
    i = list(map(list,code.split('\n')))
    res = ''
    dir = ((1,0),(-1,0),(0,-1),(0,1))
    x, y = 0, 0
    dx, dy = 1, 0
    seed()
    s = []
    str_mode = False
    while True:
        o = i[y][x]
        if str_mode and o != '"':s.append(ord(o))
        elif o in '0123456789': s.append(int(o))
        elif o == '+':s.append(s.pop()+s.pop())
        elif o == '-':s.append(-s.pop()+s.pop())
        elif o == '*':s.append(s.pop()*s.pop())
        elif o in '/%' :
            a = s.pop()
            if a:
                if o == '/':
                    s.append(s.pop()//a)
                else:
                    s.append(s.pop()%a)
            else:
                s[len(s)-1] = 0
        elif o == '!':s.append(0 if s.pop() else 1)
        elif o == '`':s.append(int(s.pop()<s.pop()))
        elif o == '>':dx, dy = dir[0]
        elif o == '<':dx, dy = dir[1]
        elif o == '^':dx, dy = dir[2]
        elif o == 'v':dx, dy = dir[3]
        elif o == '?':dx, dy = dir[randint(0,3)]
        elif o == '_':dx, dy = dir[1 if s.pop() else 0]
        elif o == '|':dx, dy = dir[2 if s.pop() else 3]
        elif o == '"':str_mode = not str_mode
        elif o == ':':
            if s:s.append(s[len(s)-1])
            else:s = [0,0]
        elif o == '\\':
            if s:
                if len(s)==1:
                    s.insert(0,0)
                else:
                    s.insert(len(s)-2, s.pop())
            else:s = [0,0]
        elif o == '$':s.pop()
        elif o == '.':res += str(s.pop())
        elif o == ',':res += chr(s.pop())
        elif o == '#':x, y = x+dx, y+dy
        elif o == 'p':
            py = s.pop()
            px = s.pop()
            i[py][px] = chr(s.pop())
        elif o == 'g':s.append(ord(i[s.pop()][s.pop()]))
        elif o == '@':
            return res
        x+=dx
        y+=dy

import inspect
import random


def interpret(s):
    return Befunge93(s.splitlines()).run()


class Befunge93:

    instructions = {}

    def __init__(self, plane):
        self.plane = [list(row) for row in plane]
        self.stack = []
        self.direction = [0, 1]
        self.row, self.col = 0, 0
        self.running = True
        self.output = []
        self.number = 0

    def forward(self):
        if self.number:
            self.row += self.direction[0]
            self.col += self.direction[1]
        self.number += 1
        return self.plane[self.row][self.col]

    def string_literal(self):
        self.stack.extend(ord(ch) for ch in iter(self.forward, '"'))

    def run(self):
        while self.running:
            self.instructions[self.forward()](self)
        return ''.join(self.output)


def pop_push_on(ch):
    def deco(f):
        nargs = len(inspect.getargspec(f).args)
        def wrapper(self):
            self.stack.append(f(*[self.stack.pop() for i in range(nargs)]))
        Befunge93.instructions[ch] = wrapper
        return wrapper
    return deco

def on(ch): return lambda f: Befunge93.instructions.__setitem__(ch, f)

pop_push_on('+')(lambda a, b: a + b)
pop_push_on('-')(lambda a, b: b - a)
pop_push_on('*')(lambda a, b: a * b)
pop_push_on('/')(lambda a, b: b // a if a else 0)
pop_push_on('%')(lambda a, b: b % a if a else 0)
pop_push_on('!')(lambda a: 0 if a else 1)
pop_push_on('`')(lambda a, b: 1 if b > a else 0)
on('>')(lambda self: self.direction.__setitem__(slice(None), [0, +1]))
on('<')(lambda self: self.direction.__setitem__(slice(None), [0, -1]))
on('^')(lambda self: self.direction.__setitem__(slice(None), [-1, 0]))
on('v')(lambda self: self.direction.__setitem__(slice(None), [+1, 0]))
on('?')(lambda self: self.direction.__setitem__(slice(None), random.choice([[0, +1], [0, -1], [-1, 0], [+1, 0]])))
on('_')(lambda self: self.direction.__setitem__(slice(None), [0, +1] if self.stack.pop() == 0 else [0, -1]))
on('|')(lambda self: self.direction.__setitem__(slice(None), [+1, 0] if self.stack.pop() == 0 else [-1, 0]))
on('|')(lambda self: self.direction.__setitem__(slice(None), [+1, 0] if self.stack.pop() == 0 else [-1, 0]))
on(':')(lambda self: self.stack.append(self.stack[-1] if self.stack else 0))
on('\\')(lambda self: self.stack.append(self.stack.pop(-2) if len(self.stack) >= 2 else 0))
on(' ')(lambda self: 0)
on('@')(lambda self: setattr(self, 'running', False))
on('$')(lambda self: self.stack.pop())
on('.')(lambda self: self.output.append(str(self.stack.pop())))
on(',')(lambda self: self.output.append(chr(self.stack.pop())))
on('#')(lambda self: self.forward())
on('"')(lambda self: self.string_literal())
on('p')(lambda self: self.plane[self.stack.pop()].__setitem__(self.stack.pop(), chr(self.stack.pop())))
on('g')(lambda self: self.stack.append(ord(self.plane[self.stack.pop()][self.stack.pop()])))
for ch in '0123456789': on(ch)(lambda self, ch=int(ch): self.stack.append(ch))