Turing

//http://www.reddit.com/r/dailyprogrammer/comments/31aja8/20150403_challenge_208_hard_the_universal_machine/

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <algorithm>
#include <cmath>
#include <sstream>
using namespace std;

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<char> VC;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef pair<string, char> PSC;
typedef pair<int, P> PP;
typedef vector<P> VP;
typedef vector<PP> VPP;
typedef pair<PSC, int> PSCI;
typedef map<PSC, PSCI> M;
typedef M::iterator MIT;
#define pb push_back
#define X first
#define Y second
#define L(v) (int)v.size()




int main() {
    string alphabet;
    cin >> alphabet;
    string s;
    cin >> s;
    getline(cin, s);
    string actual;
    cin >> actual;
    string accepted;
    cin >> accepted;
    string word;
    cin >> word;
    string a;
    M conditions;
    while (cin >> a) {
        char c;
        cin >> c;
        char igual;
        cin >> igual;
        string res;
        cin >> res;
        char def;
        cin >> def;
        char pos;
        cin >> pos;
        int x;
        if (pos == '<') x = -1;
        else x = 1;
        conditions[PSC(a,c)] = PSCI(PSC(res,def),x);
    }

    int i = 0;
    while (actual != accepted) {
        char c;
        if (i >= 0 and i < L(word)) c = word[i];
        else c = '_';
        PSC f = PSC(actual, c);
        MIT it = conditions.find(f);
        actual = it->Y.X.X;
        if (i >= 0 and i < L(word)) {
            char def = it->Y.X.Y;
            word[i] = def;
            i += it->Y.Y;
        }
        else if (i >= L(word)) {
            char def = it->Y.X.Y;
            if (def != '_') word += def;
            i += it->Y.Y;
        }
        else {
            char def = it->Y.X.Y;
            if (def != '_') {
                string p = word;
                word = def;
                word += p;
            }
            i += it->Y.Y;
        }
    }
    cout << word << endl;
    cout << "|";
    if (i == 0) cout << endl;
    else {
        i--;
        for (int j = 0; j < i; ++j) cout << " ";
        cout << "^" << endl;
    }

}