/*
PROBLEM: 1405 - The Halting Problem
ANSWER: Accepted
LANGUAGE: C++17 (g++ 7.3.0, -std=c++17 -O2 -lm) [+0s]
RUNTIME: 0.004s
FILE SIZE: 8.53 KB
SUBMISSION: 10/16/18, 3:31:00 PM
*/
#include <iostream>
#include <sstream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <memory>
#include <exception>

enum class CommandType {
	OP = 0,
	IF = 1,
	ENDIF = 2,
	CALL = 3,
	RET = 4
};

class Program;

class Param {
public:
	Param() {};
	virtual int getValue() const = 0;
	virtual std::string toString() const = 0;
	virtual int &getRef() = 0;
};

class Constant : public Param {
public:
	Constant(int value) : Param(), value(value) {};
	int getValue() const {
		return value;
	};
	int &getRef() {
		throw std::logic_error("can't get a ref to a constant parameter.");
	};
	std::string toString() const {return std::to_string(value);};
private:
	int value;
};

class Register : public Param {
public:
	Register(int &value, int r) : Param(), value(value), r(r) {};
	int getValue() const {
		return value;
	};
	int &getRef() {
		return value;
	};
	std::string toString() const {return "R"+std::to_string(r);};
private:
	int &value;
	int r;
};

Param *makeParam(Program &, std::string);

class Command {
public:
	Command(Program &program, std::string cmd, Param *p1, Param *p2) : program(program), cmd(cmd), p1(p1), p2(p2) {};
	virtual ~Command() {};
	virtual void execute() = 0;
	virtual CommandType type() {return CommandType::OP;};
	std::string toString() {
		std::string p1str, p2str;
		if (p1)
			p1str = p1->toString();

		if (p2)
			p2str = ","+p2->toString();

		return cmd + " " + p1str + p2str;
	};
protected:
	Program &program;
	std::string cmd;
	std::unique_ptr<Param> p1, p2;
};

Command *makeCommand(Program &p, std::string cmd, std::string p1, std::string p2);

class Program {
public:
	Program(int r0) : r0(r0) {};
	int &getRegister(int r) {return registers[r];};
	void addCommand(std::string cmd, std::string p1, std::string p2) {
		commands.emplace_back(makeCommand(*this, cmd, p1, p2));
	};

	void incIP() {++IP;};
	void resetIP() {IP = 0;};
	void branchIP() {IP = branches[IP];};

	void run(bool debug) {
		init();

		while (!terminated) {
			if (debug) {
				std::cerr << IP << ": " << commands[IP]->toString() << " [ ";
				for (auto r: registers)
					std::cerr << r << " ";
				std::cerr << "]" << std::endl;
			}

			commands[IP]->execute();
		}
	};

	void pushRegisters(int callValue) {
		if (callValues.count(callValue) > 0)
			throw std::logic_error("this program entered an infinite loop.");

		callValues.insert(callValue);
		callStack.push_back(callValue);
		stack.push_back(std::make_pair(registers, std::make_pair(IP, callValue)));
	};

	int popRegisters() {
		if (stack.size() > 0) {
			for (size_t i = 0; i < registers.size(); ++i) // copy to keep the register references
				registers[i] = stack.back().first[i];

			IP = stack.back().second.first;
			int callValue = stack.back().second.second;
			stack.pop_back();
			callValues.erase(callValue);
			callStack.pop_back();
			return callValue;
		}
		terminated = true;
		return -1;
	};

	int getMemoizedCall(int callValue) {
		auto it = memoizedCalls.find(callValue);
		if (it != memoizedCalls.end())
			return it->second;
		return -1;
	}

	void setMemoizedCall(int callValue, int retValue) {
		memoizedCalls[callValue] = retValue;
	}
private:
	bool terminated = false;
	int IP = 0; // instruction pointer
	int r0;
	std::unordered_map<int, int> branches;
	std::vector<std::unique_ptr<Command> > commands; // the program itself
	std::vector<int> registers = {0,0,0,0,0,0,0,0,0,0};
	std::vector<std::pair<std::vector<int>, std::pair<int, int> > > stack; // save/restore regsiters+IP+CALL_VALUE for CALL & RET
	std::unordered_map<int, int> memoizedCalls; // speed up cache

	// infinite loop control (parallel structures for faster access)
	std::unordered_set<int> callValues;
	std::vector<int> callStack;

	void computeBranches() {
		branches.clear();
		std::vector<int> branchCtrl;
		for (size_t i = 0; i < commands.size(); ++i) {
			if (commands[i]->type() == CommandType::IF)
				branchCtrl.push_back(i);
			if (commands[i]->type() == CommandType::ENDIF) {
				branches[branchCtrl.back()] = i+1;
				branchCtrl.pop_back();
			}
		}
	};

	void init() {
		terminated = false;
		computeBranches();

		resetIP();
		std::for_each(registers.begin(), registers.end(), [](int &r){r=0;});
		memoizedCalls.clear();
		callValues.clear();
		callStack.clear();

		registers[0] = r0;
		callValues.insert(r0);
		callStack.push_back(r0);
	};
};

class OP : public Command {
public:
	OP(Program &program, std::string cmd, Param *p1, Param *p2, std::function<void(int &, int)> op) :
	Command(program, cmd, p1, p2), op(op) {};
	void execute() override {
		op(p1->getRef(), p2->getValue());
		program.incIP();
	};
private:
	std::function<void(int &, int)> op;
};

class ENDIF : public Command {
public:
	ENDIF(Program &program, std::string cmd) : Command(program, cmd, nullptr, nullptr) {};
	void execute() override {
		program.incIP();
	};
	CommandType type() override {return CommandType::ENDIF;};
};

class IF : public Command {
public:
	IF(Program &program, std::string cmd, Param *p1, Param *p2, std::function<bool(int, int)> comp) :
		Command(program, cmd, p1, p2), comp(comp) {};
	void execute() override {
		if (comp(p1->getValue(),p2->getValue()))
			program.incIP();
		else
			program.branchIP();
	};
	CommandType type() override {return CommandType::IF;};
protected:
	std::function<bool(int, int)> comp;
};

class CALL : public Command {
public:
	CALL(Program &program, std::string cmd, Param *p1) : Command(program, cmd, p1, nullptr) {};
	void execute() override {
		int callValue = p1->getValue();
		int retValue = program.getMemoizedCall(callValue);
		if (retValue == -1) { // first time this call shows up
			program.pushRegisters(callValue);
			program.getRegister(0) = callValue;
			program.resetIP();
		} else { // reuse previously run call, simulate a return
			program.incIP();
			program.getRegister(9) = retValue;
		}
	};
	CommandType type() override {return CommandType::CALL;};
};

class RET : public Command {
public:
	RET(Program &program, std::string cmd, Param *p1) : Command(program, cmd, p1, nullptr) {};
	void execute() override {
		int retValue = p1->getValue();
		int callValue = program.popRegisters();
		program.setMemoizedCall(callValue, retValue); // save this call/ret values for reuse (memoize it)
		program.getRegister(9) = retValue;
		program.incIP();
	};
	CommandType type() override {return CommandType::RET;};
};

Param *makeParam(Program &p, std::string param) {
	if (param[0] == 'R') {
		int reg = std::stoi(param.substr(1));
		return new Register(p.getRegister(reg), reg);
	} else if (param.size() > 0)
		return new Constant(std::stoi(param));
	else
		return nullptr;
}

Command *makeCommand(Program &p, std::string cmd, std::string p1, std::string p2) {
	if (cmd == "MOV")
		return new OP(p, cmd, makeParam(p, p1), makeParam(p, p2), [](int &a, int b){a=b;});
	if (cmd == "ADD")
		return new OP(p, cmd, makeParam(p, p1), makeParam(p, p2), [](int &a, int b){a+=b; if (a>999) a-=1000;});
	if (cmd == "SUB")
		return new OP(p, cmd, makeParam(p, p1), makeParam(p, p2), [](int &a, int b){a-=b; if (a<0) a+=1000;});
	if (cmd == "MUL")
		return new OP(p, cmd, makeParam(p, p1), makeParam(p, p2), [](int &a, int b){a*=b; a %= 1000;});
	if (cmd == "DIV")
		return new OP(p, cmd, makeParam(p, p1), makeParam(p, p2), [](int &a, int b){
			if((a*b)==0)
				a = 0;
			else
				a /= b;
		});
	if (cmd == "MOD")
		return new OP(p, cmd, makeParam(p, p1), makeParam(p, p2), [](int &a, int b){
			if((a*b)==0)
				a = 0;
			else
				a %= b;
		});
	if (cmd == "ENDIF")
		return new ENDIF(p, cmd);
	if (cmd == "IFEQ")
		return new IF(p, cmd, makeParam(p, p1), makeParam(p, p2), [](int a, int b){return a==b;});
	if (cmd == "IFNEQ")
		return new IF(p, cmd, makeParam(p, p1), makeParam(p, p2), [](int a, int b){return a!=b;});
	if (cmd == "IFG")
		return new IF(p, cmd, makeParam(p, p1), makeParam(p, p2), [](int a, int b){return a>b;});
	if (cmd == "IFL")
		return new IF(p, cmd, makeParam(p, p1), makeParam(p, p2), [](int a, int b){return a<b;});
	if (cmd == "IFGE")
		return new IF(p, cmd, makeParam(p, p1), makeParam(p, p2), [](int a, int b){return a>=b;});
	if (cmd == "IFLE")
		return new IF(p, cmd, makeParam(p, p1), makeParam(p, p2), [](int a, int b){return a<=b;});
	if (cmd == "CALL")
		return new CALL(p, cmd, makeParam(p, p1));
	if (cmd == "RET")
		return new RET(p, cmd, makeParam(p, p1));
	return nullptr;
}

int main(int argc, char **argv) {
	int nlin, r0, pos = 0, prob = 0;

	std::cin >> nlin >> r0;
	while (nlin != 0) {
		if (argc > 1)
			std::cerr << "*** " << prob << " = " << pos << std::endl;
		std::string line;
		std::getline(std::cin, line); ++pos;

		Program program(r0);

		for (int i = 0; i < nlin; ++i) {
			std::getline(std::cin, line); ++ pos;
			std::transform(line.begin(), line.end(), line.begin(),
				[](char ch) {
					if (ch == ',')
						return ' ';
					else
						return ch;
			});
			std::stringstream ss(line);
			std::string cmd;
			std::string p1, p2;

			ss >> cmd >> p1 >> p2;
			program.addCommand(cmd, p1, p2);
		}
		try {
			program.run(argc > 1);
			std::cout << program.getRegister(9) << std::endl;
		} catch (...) {
			std::cout << "*" << std::endl;
		}

		std::cin >> nlin >> r0;
		++prob;
	}
}