// CL interpreter
// Oleg Mazonka 3 Dec 2003

/* tree representation: K & S rules

        A               _A_
       / \             /   \
      A   Z           A     A
     / \       =>    / \   / \
    A   Y           X   Z Y   Z
   / \
  S   X


       /              
      A         
     / \              /
    A   A    =>      X
   / \
  K   X

*/


// Input is a text file(stdin) - the binary code of the
// program and its input.
// Characters other then 1 and 0 are ignored

// Exapmles
/* Input:
	11000101	I
	101
   Output 1:
	code:        11000101
	code+input: 1110001011111001100101001100
	1010111001010011001011001100010101101011
	0001111100110010100110010101110010100110
	0101100110001010110101011111001100101001
	1001010111001010011001011001100010101101
	011000110101
	evaluated:  1100110011000101101100011011
	1001100110001011010110111001100110001011
	011000110110101
	list output: 101
   Output 2:
	code:        I
	code+input: I(P1(P0(P1$)))
	evaluated:  S(SI(01))(0(S(SI$)(0(S(SI(01))(0$)))))
	list output: 101

   Input:
	"1111100000111001011100001001100000101110011001010011001010111001"
	"0110010111001011001100010101110010110011001010011001011100101100"
	"1100010101110010110011000101110010101110000101110011001100010110"
	"1001010111001011001010111001011100001100110010100110010101001010"
	"0011010111000101";	U

	11000101	I
	101

   Output 1:
	code:        111110000011100101110000100
	1100000101110011001010011001010111001011
	0010111001011001100010101110010110011001
	0100110010111001011001100010101110010110
	0110001011100101011100001011100110011000
	1011010010101110010110010101110010111000
	0110011001010011001010100101000110101110
	00101
	code+input: 1111110000011100101110000100
	1100000101110011001010011001010111001011
	0010111001011001100010101110010110011001
	0100110010111001011001100010101110010110
	0110001011100101011100001011100110011000
	1011010010101110010110010101110010111000
	0110011001010011001010100101000110101110
	0010111110011001010011001010111001010011
	0010110011000101011010110001111100110010
	1001100101011100101001100101100110001010
	1101011000111110011001010011001010111001
	0100110010110011000101011010101111100110
	0101001100101011100101001100101100110001
	0101101010111110011001010011001010111001
	0100110010110011000101011010101111100110
	0101001100101011100101001100101100110001
	0101101011000111110011001010011001010111
	0010100110010110011000101011010101111100
	1100101001100101011100101001100101100110
	0010101101011000111110011001010011001010
	1110010100110010110011000101011010110001
	1111001100101001100101011100101001100101
	1001100010101101010111110011001010011001
	0101110010100110010110011000101011010110
	00110101
	evaluated:  1100110011000101101100011011
	1001100110001011010110111001100110001011
	011000110110101
	list output: 101
   Output 2:
	code:        U
	code+input: U(P1(P1(P0(P0(P0(P1(P0(P1(P1(P0(P1$)))))))))))
	evaluated:  S(SI(01))(0(S(SI$)(0(S(SI(01))(0$)))))
	list output: 101

   Input:
	010
   Output 1:
	code:        01
	code+input: 1011111001100101001100101011
	1001010011001011001100010101101010110101
	evaluated:  10111001100110001011010110110101
	list output: <broken>	
   Output 2:
	code:        0
	code+input: 0(P0$)
	evaluated:  0(S(SI$)(0$))
	list output: <broken>

   Input:
	110100
   Output:
	sysntax error

   Input:
	10001
   Output 1:
	code:        10001
	code+input: 10001
	evaluated:  10001
	list output: <broken>
   Output 2:
	code:        1
	code+input: 1
	evaluated:  1
	list output: <broken>

   Input:
	10100
   Output 2:
	code:        0S
	code+input: 0S
	evaluated:  0S
	list output: <broken>
*/
// Use the following variable to select the output

//use 0 for silent output
//use 1 for binary output
//use 2 for symbol output
const int DUMP = 2; 

#include <iostream>
using namespace std;

void readCode();
void readInput();
void evaluate();
void extractResult();
void deleteTree();

struct node;
node * root = 0;
void dump(node * n=root);
void dump(const char *);

int main(){

 try{
	readCode();
	dump("code:        "); dump();
	readInput();
	dump("\ncode+input: "); dump();
	evaluate();
	dump("\nevaluated:  "); dump();
	
	dump("\nlist output: ");
	extractResult();
	dump("\n");

	deleteTree();

 }catch(const char * s){
	cout<<s;
 }

}

struct node{
	enum type {S,K,A} t;
	node *left;
	node *right;
	node(type t):t(t),left(0),right(0){}
	~node(){
		if( t == A ){
		  delete left;
		  delete right;
		}
	}
	node(const node & n){
		t = n.t;
		if( t==A ){
		  left = new node(*n.left);
		  right = new node(*n.right);
		}
	}
	bool equal(const node *n){
		if( t!=n->t ) return false;
		else if( t!=A ) return true;
		return left->equal(n->left) && right->equal(n->right);
	}
};


int getBitCin(){
	char a='\0';
	while(1){
		cin.get(a);
		if(!cin) return -1;
		if( a== '0' ) return 0;
		if( a== '1' ) return 1;
	}
	return 0; // never
}

int (*getBit)() = getBitCin;

void readNode(node ** pn){

	int b = (*getBit)();
	switch(b){
		case -1:
			throw "\nsyntax error\n";
		case 1:
			*pn = new node(node::A);
			readNode(&(*pn)->left);
			readNode(&(*pn)->right);
			break;
		case 0:
			int b2 = (*getBit)();
			if( b2==0 ) *pn = new node(node::S);
			else if( b2==1 ) *pn = new node(node::K);
			else throw "\nerror: expecting 0 or 1\n";
			break;
	}
}

void readCode(){
	readNode(&root);
}

int getBitString_counter = 0;
const char * getBitString_string = 0;
int getBitString(){
	switch(getBitString_string[getBitString_counter++]){
	case '1': return 1;
	case '0': return 0;
	default: return -1;
	}
}

void initString(const char *s){
	getBitString_counter = 0;
	getBitString_string = s;
	getBit = getBitString;
}

void readNodeFrom(node ** n, const char *s)
{
  initString(s);
  readNode(n);
  getBit = getBitCin;
}

const char * opP = "11001100101001100101011100101001100101100110001010110101";
const char * opD = "10101";
const char * opQ = "10110110001";
const char * opI = "11000101";
const char * opU = 
	"1111100000111001011100001001100000101110011001010011001010111001"
	"0110010111001011001100010101110010110011001010011001011100101100"
	"1100010101110010110011000101110010101110000101110011001100010110"
	"1001010111001011001010111001011100001100110010100110010101001010"
	"0011010111000101";
const char * op0 = "01";
const char * op1 = "10001";
const char * opY = "11100000111001011100001001100000101";

void readInput(){
	int b = (*getBit)();
	if( b == -1 ) return;

	node *r =  new node(node::A);
	r->left = root;
	root = r;

	while( 1 ){
		
		node * a1 = new node(node::A);
		node * a2 = new node(node::A);
		r->right = a1;
		a1->left = a2;
		//a2->left**P
			readNodeFrom(&a2->left,opP);
		//a2->right**b
			if( b==1 ){
			  readNodeFrom(&a2->right,op1);
			}else{
			  readNodeFrom(&a2->right,op0);
			}

		getBit = getBitCin;
		b = (*getBit)();
		if( b==-1 ){
			readNodeFrom(&a1->right,opD);
			break;
		}
		r = a1;
	}
}

bool evaluateNode( node ** pn ){

	node * a = *pn;

	if( a->t == node::A )
	if( a->left->t == node::A )
	if( a->left->left->t == node::A )
	if( a->left->left->left->t == node::S ){
	
		node * a2 = a->left;
		node * a3 = a2->left;
		node * x = a3->right;
		node * y = a2->right;
		node * z = a->right;

		delete a3->left;
		*pn = a2;
		a2->right = a;
		a->left = y;
		a3->left = x;
		a3->right = new node(*z);

		return true;
	}
	
	if( a->t == node::A )
        if( a->left->t == node::A )
        if( a->left->left->t == node::K ){

		node * x = a->left->right;
		delete a->left->left;
		delete a->right;
		a->left->t = node::S;
		delete a->left;
		a->t = node::S;
		delete a;
		*pn = x;
	
		return true;
	}

	if( a->t == node::S || a->t == node::K )
		return false;

	return evaluateNode(&a->left) || evaluateNode(&a->right);

}

void evaluate(){
	while( evaluateNode(&root) );
}

node * apply(node * x, node * y){

	node * a = new node(node::A);
	a->left = new node(*x);
	a->right = new node(*y);
	while( evaluateNode(&a) );

	return a;
}

node * applyN(node * x, node * y, int n){

	node *b, *a = new node(*x);
	int i=0;
	for ( ; i<n; i++ ){
		b = apply(a,y);
		delete a;
		a = b;
	}
	return a;
}
		

void extractResult(){

	node *pQ;
	readNodeFrom(&pQ,opQ);

	node *p1;
	readNodeFrom(&p1,op1);

	node *p0;
	readNodeFrom(&p0,op0);

	int c=0;
	while(1){
        	// test for list
		node * v = applyN(root,p1,c++);
		node * r = apply(v,pQ);
		int m=0;

		if( r->equal(p1) ) m=1;
		else if( r->equal(p0) ) m=2;
	
		delete r;

		if( m==1 ){
			node * u = apply(v,p0);

			if( u->equal(p1) ) cout<<"1";
			else if( u->equal(p0) ) cout<<"0";
			else throw "\ninternal error: Y?=1 but Y0!=0or1\n";

			delete u;
		}

		delete v;
		if( m==2 ) break;
		if( m==0 ) { cout<<"<broken>"; return; }
	}

	delete pQ;
	delete p1;
	delete p0;
}

void deleteTree(){
	delete root;
}

void dump(const char * s){ if(DUMP) cout<<s; }

const char * recogn(node*);

void dump(node * n){

 if( n==0 ) throw "\ninternal error: 0-node\n";

 switch(DUMP){

 case 0: return;
 case 1:
	switch(n->t){
		case node::A:
			cout<<"1";
			dump(n->left);
			dump(n->right);
			break;
		case node::S:
			cout<<"00";
			break;
		case node::K:
			cout<<"01";
			break;
	}
	return;
 case 2:
	const char *c = recogn(n);
	if(c) {
		cout<<c;
		return;
	}

	switch(n->t){
		case node::A:

			//cout<<"A";
			dump(n->left);

			if( !(c=recogn(n->right)) ){
			  cout<<'(';
			  dump(n->right);
			  cout<<')';

			}else cout<<c;

			break;

		case node::S:
			cout<<"S";
			break;
		case node::K:
			cout<<"K";
			break;
	}
 }// switch DUMP
}


const char * recogn(node *n){

	static const char *m[] = { opP, "P", opD, "$", opY, "Y",
		op1, "1", op0, "0", opQ, "?", opI, "I", opU, "U" };

	int i;
	for ( i=0; i<sizeof(m)/sizeof(void*); i+=2 ){
		node *p;
		readNodeFrom(&p,m[i]);
		if( n->equal(p) ){
			delete p;
			return m[i+1];
		}
		delete p;
	}
	// if( n->t == node::K ) return "K"; is "0"
	if( n->t == node::S ) return "S";
	return 0;
}