#include <stdio.h>
 
#define N 6
#define ROWS 6
#define COLS 6
#define data_in_save 100
#define MAX_COMMANDS 100
 
int count_data_save = 0;
int start_end[ROWS][COLS] = {
    {0, 0, 1, 0, 0, 2}, // 0
    {0, 0, 0, 0, 0, 0}, // 1
    {0, 0, 0, 0, 0, 0}, // 2
    {0, 0, 0, 0, 0, 0}, // 3
    {0, 0, 0, 0, 0, 0}, // 4
    {0, 0, 0, 0, 0, 0}  // 5
};
 
int m[N][N] = {
    { 1,1,1,1,1,1 }, //0
    { 0,1,0,0,1,1 }, //1
    { 0,1,1,1,1,0 }, //2
    { 0,0,0,0,1,1 }, //3
    { 0,1,1,1,1,0 }, //4
    { 1,0,0,0,1,1 }  //5
};
 
char data_save_in[ROWS][COLS][data_in_save];  
int data_go_in[ROWS][COLS][data_in_save];    
char movement_commands[MAX_COMMANDS][4];     
int command_index = 0;
 
// ฟังก์ชันตรวจสอบความปลอดภัย
int issafe(int m[N][N], int x, int y) {
    if (x < 0 || x >= N) return 0;
    if (y < 0 || y >= N) return 0;
    return (m[x][y] == 1);
}
 
// ฟังก์ชันแสดงผลทางออก
void print_solution(int m[N][N], char direction_grid[N][N], int data_go_in_current[N][COLS]) {
    static int nsol = 0;
    printf("Solution %d\n\n", ++nsol);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (direction_grid[i][j] != ' ') {
                printf("%c ", direction_grid[i][j]);
            } else {
                printf("%d ", m[i][j]);
            }
            if (count_data_save < data_in_save) {
                data_save_in[i][j][count_data_save] = direction_grid[i][j];
                data_go_in[i][j][count_data_save] = data_go_in_current[i][j];
            }
        }
        printf("\n");
    }
    printf("\n");
    count_data_save++;
}
 
// ฟังก์ชันค้นหาเส้นทาง
int maze(int m[N][N], int x, int y, int end_x, int end_y, char direction_grid[N][N], int data_go_in_current[N][COLS], int step, char prev_direction) {
    int nsol = 0;
 
    if (issafe(m, x, y)) {
        m[x][y] = 2;  
        direction_grid[x][y] = prev_direction;  
        data_go_in_current[x][y] = step;        
 
        if (x == end_x && y == end_y) {
            print_solution(m, direction_grid, data_go_in_current);
            nsol = 1;
        } else {
            nsol += maze(m, x, y + 1, end_x, end_y, direction_grid, data_go_in_current, step + 1, '>');  
            nsol += maze(m, x, y - 1, end_x, end_y, direction_grid, data_go_in_current, step + 1, '<');  
            nsol += maze(m, x + 1, y, end_x, end_y, direction_grid, data_go_in_current, step + 1, 'v');  
            nsol += maze(m, x - 1, y, end_x, end_y, direction_grid, data_go_in_current, step + 1, '^');  
        }
 
        m[x][y] = 1;          
        direction_grid[x][y] = ' ';  
        data_go_in_current[x][y] = 0; 
    }
 
    return nsol;
}
 
// ฟังก์ชันสร้างคำสั่งการเคลื่อนที่
void generate_movement_commands(int solution) {
    int dx[] = {0, 1, 0, -1};  
    int dy[] = {1, 0, -1, 0};  
    int prev_direction = -1;    
    command_index = 0;          
 
    int x = -1, y = -1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (data_go_in[i][j][solution] == 1) {  
                x = i;
                y = j;
                break;
            }
        }
        if (x != -1) break;
    }
 
    while (1) {
        int current_step = data_go_in[x][y][solution];
        int next_step = 0;
        int next_x = -1, next_y = -1;
 
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
 
            if (nx >= 0 && ny >= 0 && nx < N && ny < N && data_go_in[nx][ny][solution] == current_step + 1) {
                next_step = data_go_in[nx][ny][solution];
                next_x = nx;
                next_y = ny;
 
                if (prev_direction == -1 || d == prev_direction) {
                    snprintf(movement_commands[command_index++], sizeof(movement_commands[command_index]), "F");
                } else if ((prev_direction == 0 && d == 3) || (prev_direction == 1 && d == 0) || 
                           (prev_direction == 2 && d == 1) || (prev_direction == 3 && d == 2)) {
                    snprintf(movement_commands[command_index++], sizeof(movement_commands[command_index]), "L F");
                } else {
                    snprintf(movement_commands[command_index++], sizeof(movement_commands[command_index]), "R F");
                }
 
                prev_direction = d;
                break;
            }
        }
 
        if (next_step == 0) break;
 
        x = next_x;
        y = next_y;
    }
}
 
// ฟังก์ชันคำนวณคะแนน
int calculate_score() {
    int score = 0;
 
    for (int i = 0; i < command_index; i++) {
        if (movement_commands[i][0] == 'F') {
            score += 1;
        } else if (movement_commands[i][0] == 'L' || movement_commands[i][0] == 'R') {
            score += 2;
        }
    }
 
    return score;
}
 
int scores[100];  // ตัวแปรเก็บคะแนนของแต่ละ solution
 
// ฟังก์ชันแสดงข้อมูลทั้งหมด รวมถึงเส้นทางที่ดีที่สุด
void show_data_get() {
    int min_score = 99999;  // เก็บคะแนนต่ำสุด
    int best_solution = -1;  // เก็บ solution ที่ดีที่สุด
 
    printf("Data saved:\n");
    for (int sol = 0; sol < count_data_save; sol++) {
        printf("Solution %d:\n", sol + 1);
        printf("Directions:\n");
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                printf("%c ", data_save_in[i][j][sol]);
            }
            printf("\n");
        }
        printf("Step Numbers:\n");
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLS; j++) {
                printf("%d ", data_go_in[i][j][sol]);
            }
            printf("\n");
        }
 
        // สร้างและแสดงคำสั่งการเคลื่อนที่
        generate_movement_commands(sol);
        printf("Movement Commands: ");
        for (int i = 0; i < command_index; i++) {
            printf("%s ", movement_commands[i]);
        }
        printf("\n");
 
        // คำนวณและแสดงคะแนน
        int score = calculate_score();
        scores[sol] = score;  // บันทึกคะแนนของแต่ละ solution
        printf("Score: %d\n\n", score);
 
        // ตรวจสอบหา solution ที่มีคะแนนต่ำสุด
        if (score < min_score) {
            min_score = score;
            best_solution = sol;
        }
    }
 
    // แสดง solution ที่ดีที่สุด
    printf("Best Solution is Solution %d with the lowest score of %d:\n", best_solution + 1, min_score);
 
    // แสดง Movement Commands ของทางเลือกที่ดีที่สุด
    printf("Best Movement Commands: ");
    generate_movement_commands(best_solution);
    for (int i = 0; i < command_index; i++) {
        printf("%s ", movement_commands[i]);
    }
    printf("\n");
 
    // แสดงเส้นทางที่ดีที่สุด
    printf("Best Solution Path:\n");
 
 
    // แสดง Step Numbers ของทางเลือกที่ดีที่สุด
    printf("Step Numbers:\n");
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            printf("%d ", data_go_in[i][j][best_solution]);
        }
        printf("\n");
    }
    printf("Directions:\n");
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            printf("%c ", data_save_in[i][j][best_solution]);
        }
        printf("\n");
    }
    printf("\n\n");
}
 
// ฟังก์ชันหลัก
void Program_run() {
    int nsol;
    int start_x = -1, start_y = -1, end_x = -1, end_y = -1;
 
    // ค้นหาจุดเริ่มต้นและจุดสิ้นสุด
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            if (start_end[i][j] == 1) {
                start_x = i;
                start_y = j;
            } else if (start_end[i][j] == 2) {
                end_x = i;
                end_y = j;
            }
        }
    }
 
    // ตรวจสอบว่ามีจุดเริ่มต้นและจุดสิ้นสุด
    if (start_x == -1 || start_y == -1 || end_x == -1 || end_y == -1) {
        printf("Error: No start or end point defined in start_end array.\n");
        return;
    }
 
    char direction_grid[N][N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            direction_grid[i][j] = ' ';
        }
    }
 
    int data_go_in_current[N][COLS];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < COLS; j++) {
            data_go_in_current[i][j] = 0;
        }
    }
 
    nsol = maze(m, start_x, start_y, end_x, end_y, direction_grid, data_go_in_current, 1, 'S');
    printf("%d solutions.\n", nsol);
}
 
int main() {
    Program_run();
    printf("Count data saved: %d\n", count_data_save);
    show_data_get();
    return 0;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CgojZGVmaW5lIE4gNgojZGVmaW5lIFJPV1MgNgojZGVmaW5lIENPTFMgNgojZGVmaW5lIGRhdGFfaW5fc2F2ZSAxMDAKI2RlZmluZSBNQVhfQ09NTUFORFMgMTAwCgppbnQgY291bnRfZGF0YV9zYXZlID0gMDsKaW50IHN0YXJ0X2VuZFtST1dTXVtDT0xTXSA9IHsKICAgIHswLCAwLCAxLCAwLCAwLCAyfSwgLy8gMAogICAgezAsIDAsIDAsIDAsIDAsIDB9LCAvLyAxCiAgICB7MCwgMCwgMCwgMCwgMCwgMH0sIC8vIDIKICAgIHswLCAwLCAwLCAwLCAwLCAwfSwgLy8gMwogICAgezAsIDAsIDAsIDAsIDAsIDB9LCAvLyA0CiAgICB7MCwgMCwgMCwgMCwgMCwgMH0gIC8vIDUKfTsKCmludCBtW05dW05dID0gewogICAgeyAxLDEsMSwxLDEsMSB9LCAvLzAKICAgIHsgMCwxLDAsMCwxLDEgfSwgLy8xCiAgICB7IDAsMSwxLDEsMSwwIH0sIC8vMgogICAgeyAwLDAsMCwwLDEsMSB9LCAvLzMKICAgIHsgMCwxLDEsMSwxLDAgfSwgLy80CiAgICB7IDEsMCwwLDAsMSwxIH0gIC8vNQp9OwoKY2hhciBkYXRhX3NhdmVfaW5bUk9XU11bQ09MU11bZGF0YV9pbl9zYXZlXTsgIAppbnQgZGF0YV9nb19pbltST1dTXVtDT0xTXVtkYXRhX2luX3NhdmVdOyAgICAKY2hhciBtb3ZlbWVudF9jb21tYW5kc1tNQVhfQ09NTUFORFNdWzRdOyAgICAgCmludCBjb21tYW5kX2luZGV4ID0gMDsKCi8vIOC4n+C4seC4h+C4geC5jOC4iuC4seC4meC4leC4o+C4p+C4iOC4quC4reC4muC4hOC4p+C4suC4oeC4m+C4peC4reC4lOC4oOC4seC4ogppbnQgaXNzYWZlKGludCBtW05dW05dLCBpbnQgeCwgaW50IHkpIHsKICAgIGlmICh4IDwgMCB8fCB4ID49IE4pIHJldHVybiAwOwogICAgaWYgKHkgPCAwIHx8IHkgPj0gTikgcmV0dXJuIDA7CiAgICByZXR1cm4gKG1beF1beV0gPT0gMSk7Cn0KCi8vIOC4n+C4seC4h+C4geC5jOC4iuC4seC4meC5geC4quC4lOC4h+C4nOC4peC4l+C4suC4h+C4reC4reC4gQp2b2lkIHByaW50X3NvbHV0aW9uKGludCBtW05dW05dLCBjaGFyIGRpcmVjdGlvbl9ncmlkW05dW05dLCBpbnQgZGF0YV9nb19pbl9jdXJyZW50W05dW0NPTFNdKSB7CiAgICBzdGF0aWMgaW50IG5zb2wgPSAwOwogICAgcHJpbnRmKCJTb2x1dGlvbiAlZFxuXG4iLCArK25zb2wpOwogICAgCiAgICBmb3IgKGludCBpID0gMDsgaSA8IE47IGkrKykgewogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgTjsgaisrKSB7CiAgICAgICAgICAgIGlmIChkaXJlY3Rpb25fZ3JpZFtpXVtqXSAhPSAnICcpIHsKICAgICAgICAgICAgICAgIHByaW50ZigiJWMgIiwgZGlyZWN0aW9uX2dyaWRbaV1bal0pOwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgcHJpbnRmKCIlZCAiLCBtW2ldW2pdKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBpZiAoY291bnRfZGF0YV9zYXZlIDwgZGF0YV9pbl9zYXZlKSB7CiAgICAgICAgICAgICAgICBkYXRhX3NhdmVfaW5baV1bal1bY291bnRfZGF0YV9zYXZlXSA9IGRpcmVjdGlvbl9ncmlkW2ldW2pdOwogICAgICAgICAgICAgICAgZGF0YV9nb19pbltpXVtqXVtjb3VudF9kYXRhX3NhdmVdID0gZGF0YV9nb19pbl9jdXJyZW50W2ldW2pdOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHByaW50ZigiXG4iKTsKICAgIH0KICAgIHByaW50ZigiXG4iKTsKICAgIGNvdW50X2RhdGFfc2F2ZSsrOwp9CgovLyDguJ/guLHguIfguIHguYzguIrguLHguJnguITguYnguJnguKvguLLguYDguKrguYnguJnguJfguLLguIcKaW50IG1hemUoaW50IG1bTl1bTl0sIGludCB4LCBpbnQgeSwgaW50IGVuZF94LCBpbnQgZW5kX3ksIGNoYXIgZGlyZWN0aW9uX2dyaWRbTl1bTl0sIGludCBkYXRhX2dvX2luX2N1cnJlbnRbTl1bQ09MU10sIGludCBzdGVwLCBjaGFyIHByZXZfZGlyZWN0aW9uKSB7CiAgICBpbnQgbnNvbCA9IDA7CgogICAgaWYgKGlzc2FmZShtLCB4LCB5KSkgewogICAgICAgIG1beF1beV0gPSAyOyAgCiAgICAgICAgZGlyZWN0aW9uX2dyaWRbeF1beV0gPSBwcmV2X2RpcmVjdGlvbjsgIAogICAgICAgIGRhdGFfZ29faW5fY3VycmVudFt4XVt5XSA9IHN0ZXA7ICAgICAgICAKCiAgICAgICAgaWYgKHggPT0gZW5kX3ggJiYgeSA9PSBlbmRfeSkgewogICAgICAgICAgICBwcmludF9zb2x1dGlvbihtLCBkaXJlY3Rpb25fZ3JpZCwgZGF0YV9nb19pbl9jdXJyZW50KTsKICAgICAgICAgICAgbnNvbCA9IDE7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgbnNvbCArPSBtYXplKG0sIHgsIHkgKyAxLCBlbmRfeCwgZW5kX3ksIGRpcmVjdGlvbl9ncmlkLCBkYXRhX2dvX2luX2N1cnJlbnQsIHN0ZXAgKyAxLCAnPicpOyAgCiAgICAgICAgICAgIG5zb2wgKz0gbWF6ZShtLCB4LCB5IC0gMSwgZW5kX3gsIGVuZF95LCBkaXJlY3Rpb25fZ3JpZCwgZGF0YV9nb19pbl9jdXJyZW50LCBzdGVwICsgMSwgJzwnKTsgIAogICAgICAgICAgICBuc29sICs9IG1hemUobSwgeCArIDEsIHksIGVuZF94LCBlbmRfeSwgZGlyZWN0aW9uX2dyaWQsIGRhdGFfZ29faW5fY3VycmVudCwgc3RlcCArIDEsICd2Jyk7ICAKICAgICAgICAgICAgbnNvbCArPSBtYXplKG0sIHggLSAxLCB5LCBlbmRfeCwgZW5kX3ksIGRpcmVjdGlvbl9ncmlkLCBkYXRhX2dvX2luX2N1cnJlbnQsIHN0ZXAgKyAxLCAnXicpOyAgCiAgICAgICAgfQoKICAgICAgICBtW3hdW3ldID0gMTsgICAgICAgICAgCiAgICAgICAgZGlyZWN0aW9uX2dyaWRbeF1beV0gPSAnICc7ICAKICAgICAgICBkYXRhX2dvX2luX2N1cnJlbnRbeF1beV0gPSAwOyAKICAgIH0KCiAgICByZXR1cm4gbnNvbDsKfQoKLy8g4Lif4Lix4LiH4LiB4LmM4LiK4Lix4LiZ4Liq4Lij4LmJ4Liy4LiH4LiE4Liz4Liq4Lix4LmI4LiH4LiB4Liy4Lij4LmA4LiE4Lil4Li34LmI4Lit4LiZ4LiX4Li14LmICnZvaWQgZ2VuZXJhdGVfbW92ZW1lbnRfY29tbWFuZHMoaW50IHNvbHV0aW9uKSB7CiAgICBpbnQgZHhbXSA9IHswLCAxLCAwLCAtMX07ICAKICAgIGludCBkeVtdID0gezEsIDAsIC0xLCAwfTsgIAogICAgaW50IHByZXZfZGlyZWN0aW9uID0gLTE7ICAgIAogICAgY29tbWFuZF9pbmRleCA9IDA7ICAgICAgICAgIAogICAgCiAgICBpbnQgeCA9IC0xLCB5ID0gLTE7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IE47IGkrKykgewogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgTjsgaisrKSB7CiAgICAgICAgICAgIGlmIChkYXRhX2dvX2luW2ldW2pdW3NvbHV0aW9uXSA9PSAxKSB7ICAKICAgICAgICAgICAgICAgIHggPSBpOwogICAgICAgICAgICAgICAgeSA9IGo7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBpZiAoeCAhPSAtMSkgYnJlYWs7CiAgICB9CgogICAgd2hpbGUgKDEpIHsKICAgICAgICBpbnQgY3VycmVudF9zdGVwID0gZGF0YV9nb19pblt4XVt5XVtzb2x1dGlvbl07CiAgICAgICAgaW50IG5leHRfc3RlcCA9IDA7CiAgICAgICAgaW50IG5leHRfeCA9IC0xLCBuZXh0X3kgPSAtMTsKICAgICAgICAKICAgICAgICBmb3IgKGludCBkID0gMDsgZCA8IDQ7IGQrKykgewogICAgICAgICAgICBpbnQgbnggPSB4ICsgZHhbZF07CiAgICAgICAgICAgIGludCBueSA9IHkgKyBkeVtkXTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGlmIChueCA+PSAwICYmIG55ID49IDAgJiYgbnggPCBOICYmIG55IDwgTiAmJiBkYXRhX2dvX2luW254XVtueV1bc29sdXRpb25dID09IGN1cnJlbnRfc3RlcCArIDEpIHsKICAgICAgICAgICAgICAgIG5leHRfc3RlcCA9IGRhdGFfZ29faW5bbnhdW255XVtzb2x1dGlvbl07CiAgICAgICAgICAgICAgICBuZXh0X3ggPSBueDsKICAgICAgICAgICAgICAgIG5leHRfeSA9IG55OwoKICAgICAgICAgICAgICAgIGlmIChwcmV2X2RpcmVjdGlvbiA9PSAtMSB8fCBkID09IHByZXZfZGlyZWN0aW9uKSB7CiAgICAgICAgICAgICAgICAgICAgc25wcmludGYobW92ZW1lbnRfY29tbWFuZHNbY29tbWFuZF9pbmRleCsrXSwgc2l6ZW9mKG1vdmVtZW50X2NvbW1hbmRzW2NvbW1hbmRfaW5kZXhdKSwgIkYiKTsKICAgICAgICAgICAgICAgIH0gZWxzZSBpZiAoKHByZXZfZGlyZWN0aW9uID09IDAgJiYgZCA9PSAzKSB8fCAocHJldl9kaXJlY3Rpb24gPT0gMSAmJiBkID09IDApIHx8IAogICAgICAgICAgICAgICAgICAgICAgICAgICAocHJldl9kaXJlY3Rpb24gPT0gMiAmJiBkID09IDEpIHx8IChwcmV2X2RpcmVjdGlvbiA9PSAzICYmIGQgPT0gMikpIHsKICAgICAgICAgICAgICAgICAgICBzbnByaW50Zihtb3ZlbWVudF9jb21tYW5kc1tjb21tYW5kX2luZGV4KytdLCBzaXplb2YobW92ZW1lbnRfY29tbWFuZHNbY29tbWFuZF9pbmRleF0pLCAiTCBGIik7CiAgICAgICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgICAgIHNucHJpbnRmKG1vdmVtZW50X2NvbW1hbmRzW2NvbW1hbmRfaW5kZXgrK10sIHNpemVvZihtb3ZlbWVudF9jb21tYW5kc1tjb21tYW5kX2luZGV4XSksICJSIEYiKTsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICBwcmV2X2RpcmVjdGlvbiA9IGQ7CiAgICAgICAgICAgICAgICBicmVhazsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAKICAgICAgICBpZiAobmV4dF9zdGVwID09IDApIGJyZWFrOwogICAgICAgIAogICAgICAgIHggPSBuZXh0X3g7CiAgICAgICAgeSA9IG5leHRfeTsKICAgIH0KfQoKLy8g4Lif4Lix4LiH4LiB4LmM4LiK4Lix4LiZ4LiE4Liz4LiZ4Lin4LiT4LiE4Liw4LmB4LiZ4LiZCmludCBjYWxjdWxhdGVfc2NvcmUoKSB7CiAgICBpbnQgc2NvcmUgPSAwOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgY29tbWFuZF9pbmRleDsgaSsrKSB7CiAgICAgICAgaWYgKG1vdmVtZW50X2NvbW1hbmRzW2ldWzBdID09ICdGJykgewogICAgICAgICAgICBzY29yZSArPSAxOwogICAgICAgIH0gZWxzZSBpZiAobW92ZW1lbnRfY29tbWFuZHNbaV1bMF0gPT0gJ0wnIHx8IG1vdmVtZW50X2NvbW1hbmRzW2ldWzBdID09ICdSJykgewogICAgICAgICAgICBzY29yZSArPSAyOwogICAgICAgIH0KICAgIH0KCiAgICByZXR1cm4gc2NvcmU7Cn0KCmludCBzY29yZXNbMTAwXTsgIC8vIOC4leC4seC4p+C5geC4m+C4o+C5gOC4geC5h+C4muC4hOC4sOC5geC4meC4meC4guC4reC4h+C5geC4leC5iOC4peC4sCBzb2x1dGlvbgoKLy8g4Lif4Lix4LiH4LiB4LmM4LiK4Lix4LiZ4LmB4Liq4LiU4LiH4LiC4LmJ4Lit4Lih4Li54Lil4LiX4Lix4LmJ4LiH4Lir4Lih4LiUIOC4o+C4p+C4oeC4luC4tuC4h+C5gOC4quC5ieC4meC4l+C4suC4h+C4l+C4teC5iOC4lOC4teC4l+C4teC5iOC4quC4uOC4lAp2b2lkIHNob3dfZGF0YV9nZXQoKSB7CiAgICBpbnQgbWluX3Njb3JlID0gOTk5OTk7ICAvLyDguYDguIHguYfguJrguITguLDguYHguJnguJnguJXguYjguLPguKrguLjguJQKICAgIGludCBiZXN0X3NvbHV0aW9uID0gLTE7ICAvLyDguYDguIHguYfguJogc29sdXRpb24g4LiX4Li14LmI4LiU4Li14LiX4Li14LmI4Liq4Li44LiUCgogICAgcHJpbnRmKCJEYXRhIHNhdmVkOlxuIik7CiAgICBmb3IgKGludCBzb2wgPSAwOyBzb2wgPCBjb3VudF9kYXRhX3NhdmU7IHNvbCsrKSB7CiAgICAgICAgcHJpbnRmKCJTb2x1dGlvbiAlZDpcbiIsIHNvbCArIDEpOwogICAgICAgIHByaW50ZigiRGlyZWN0aW9uczpcbiIpOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgUk9XUzsgaSsrKSB7CiAgICAgICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgQ09MUzsgaisrKSB7CiAgICAgICAgICAgICAgICBwcmludGYoIiVjICIsIGRhdGFfc2F2ZV9pbltpXVtqXVtzb2xdKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBwcmludGYoIlxuIik7CiAgICAgICAgfQogICAgICAgIHByaW50ZigiU3RlcCBOdW1iZXJzOlxuIik7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBST1dTOyBpKyspIHsKICAgICAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBDT0xTOyBqKyspIHsKICAgICAgICAgICAgICAgIHByaW50ZigiJWQgIiwgZGF0YV9nb19pbltpXVtqXVtzb2xdKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBwcmludGYoIlxuIik7CiAgICAgICAgfQoKICAgICAgICAvLyDguKrguKPguYnguLLguIfguYHguKXguLDguYHguKrguJTguIfguITguLPguKrguLHguYjguIfguIHguLLguKPguYDguITguKXguLfguYjguK3guJnguJfguLXguYgKICAgICAgICBnZW5lcmF0ZV9tb3ZlbWVudF9jb21tYW5kcyhzb2wpOwogICAgICAgIHByaW50ZigiTW92ZW1lbnQgQ29tbWFuZHM6ICIpOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgY29tbWFuZF9pbmRleDsgaSsrKSB7CiAgICAgICAgICAgIHByaW50ZigiJXMgIiwgbW92ZW1lbnRfY29tbWFuZHNbaV0pOwogICAgICAgIH0KICAgICAgICBwcmludGYoIlxuIik7CgogICAgICAgIC8vIOC4hOC4s+C4meC4p+C4k+C5geC4peC4sOC5geC4quC4lOC4h+C4hOC4sOC5geC4meC4mQogICAgICAgIGludCBzY29yZSA9IGNhbGN1bGF0ZV9zY29yZSgpOwogICAgICAgIHNjb3Jlc1tzb2xdID0gc2NvcmU7ICAvLyDguJrguLHguJnguJfguLbguIHguITguLDguYHguJnguJnguILguK3guIfguYHguJXguYjguKXguLAgc29sdXRpb24KICAgICAgICBwcmludGYoIlNjb3JlOiAlZFxuXG4iLCBzY29yZSk7CgogICAgICAgIC8vIOC4leC4o+C4p+C4iOC4quC4reC4muC4q+C4siBzb2x1dGlvbiDguJfguLXguYjguKHguLXguITguLDguYHguJnguJnguJXguYjguLPguKrguLjguJQKICAgICAgICBpZiAoc2NvcmUgPCBtaW5fc2NvcmUpIHsKICAgICAgICAgICAgbWluX3Njb3JlID0gc2NvcmU7CiAgICAgICAgICAgIGJlc3Rfc29sdXRpb24gPSBzb2w7CiAgICAgICAgfQogICAgfQoKICAgIC8vIOC5geC4quC4lOC4hyBzb2x1dGlvbiDguJfguLXguYjguJTguLXguJfguLXguYjguKrguLjguJQKICAgIHByaW50ZigiQmVzdCBTb2x1dGlvbiBpcyBTb2x1dGlvbiAlZCB3aXRoIHRoZSBsb3dlc3Qgc2NvcmUgb2YgJWQ6XG4iLCBiZXN0X3NvbHV0aW9uICsgMSwgbWluX3Njb3JlKTsKICAgIAogICAgLy8g4LmB4Liq4LiU4LiHIE1vdmVtZW50IENvbW1hbmRzIOC4guC4reC4h+C4l+C4suC4h+C5gOC4peC4t+C4reC4geC4l+C4teC5iOC4lOC4teC4l+C4teC5iOC4quC4uOC4lAogICAgcHJpbnRmKCJCZXN0IE1vdmVtZW50IENvbW1hbmRzOiAiKTsKICAgIGdlbmVyYXRlX21vdmVtZW50X2NvbW1hbmRzKGJlc3Rfc29sdXRpb24pOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBjb21tYW5kX2luZGV4OyBpKyspIHsKICAgICAgICBwcmludGYoIiVzICIsIG1vdmVtZW50X2NvbW1hbmRzW2ldKTsKICAgIH0KICAgIHByaW50ZigiXG4iKTsKCiAgICAvLyDguYHguKrguJTguIfguYDguKrguYnguJnguJfguLLguIfguJfguLXguYjguJTguLXguJfguLXguYjguKrguLjguJQKICAgIHByaW50ZigiQmVzdCBTb2x1dGlvbiBQYXRoOlxuIik7CgoKICAgIC8vIOC5geC4quC4lOC4hyBTdGVwIE51bWJlcnMg4LiC4Lit4LiH4LiX4Liy4LiH4LmA4Lil4Li34Lit4LiB4LiX4Li14LmI4LiU4Li14LiX4Li14LmI4Liq4Li44LiUCiAgICBwcmludGYoIlN0ZXAgTnVtYmVyczpcbiIpOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBST1dTOyBpKyspIHsKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IENPTFM7IGorKykgewogICAgICAgICAgICBwcmludGYoIiVkICIsIGRhdGFfZ29faW5baV1bal1bYmVzdF9zb2x1dGlvbl0pOwogICAgICAgIH0KICAgICAgICBwcmludGYoIlxuIik7CiAgICB9CiAgICBwcmludGYoIkRpcmVjdGlvbnM6XG4iKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgUk9XUzsgaSsrKSB7CiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBDT0xTOyBqKyspIHsKICAgICAgICAgICAgcHJpbnRmKCIlYyAiLCBkYXRhX3NhdmVfaW5baV1bal1bYmVzdF9zb2x1dGlvbl0pOwogICAgICAgIH0KICAgICAgICBwcmludGYoIlxuIik7CiAgICB9CiAgICBwcmludGYoIlxuXG4iKTsKfQoKLy8g4Lif4Lix4LiH4LiB4LmM4LiK4Lix4LiZ4Lir4Lil4Lix4LiBCnZvaWQgUHJvZ3JhbV9ydW4oKSB7CiAgICBpbnQgbnNvbDsKICAgIGludCBzdGFydF94ID0gLTEsIHN0YXJ0X3kgPSAtMSwgZW5kX3ggPSAtMSwgZW5kX3kgPSAtMTsKCiAgICAvLyDguITguYnguJnguKvguLLguIjguLjguJTguYDguKPguLTguYjguKHguJXguYnguJnguYHguKXguLDguIjguLjguJTguKrguLTguYnguJnguKrguLjguJQKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgUk9XUzsgaSsrKSB7CiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBDT0xTOyBqKyspIHsKICAgICAgICAgICAgaWYgKHN0YXJ0X2VuZFtpXVtqXSA9PSAxKSB7CiAgICAgICAgICAgICAgICBzdGFydF94ID0gaTsKICAgICAgICAgICAgICAgIHN0YXJ0X3kgPSBqOwogICAgICAgICAgICB9IGVsc2UgaWYgKHN0YXJ0X2VuZFtpXVtqXSA9PSAyKSB7CiAgICAgICAgICAgICAgICBlbmRfeCA9IGk7CiAgICAgICAgICAgICAgICBlbmRfeSA9IGo7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgLy8g4LiV4Lij4Lin4LiI4Liq4Lit4Lia4Lin4LmI4Liy4Lih4Li14LiI4Li44LiU4LmA4Lij4Li04LmI4Lih4LiV4LmJ4LiZ4LmB4Lil4Liw4LiI4Li44LiU4Liq4Li04LmJ4LiZ4Liq4Li44LiUCiAgICBpZiAoc3RhcnRfeCA9PSAtMSB8fCBzdGFydF95ID09IC0xIHx8IGVuZF94ID09IC0xIHx8IGVuZF95ID09IC0xKSB7CiAgICAgICAgcHJpbnRmKCJFcnJvcjogTm8gc3RhcnQgb3IgZW5kIHBvaW50IGRlZmluZWQgaW4gc3RhcnRfZW5kIGFycmF5LlxuIik7CiAgICAgICAgcmV0dXJuOwogICAgfQoKICAgIGNoYXIgZGlyZWN0aW9uX2dyaWRbTl1bTl07CiAgICBmb3IgKGludCBpID0gMDsgaSA8IE47IGkrKykgewogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgTjsgaisrKSB7CiAgICAgICAgICAgIGRpcmVjdGlvbl9ncmlkW2ldW2pdID0gJyAnOwogICAgICAgIH0KICAgIH0KCiAgICBpbnQgZGF0YV9nb19pbl9jdXJyZW50W05dW0NPTFNdOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBOOyBpKyspIHsKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IENPTFM7IGorKykgewogICAgICAgICAgICBkYXRhX2dvX2luX2N1cnJlbnRbaV1bal0gPSAwOwogICAgICAgIH0KICAgIH0KCiAgICBuc29sID0gbWF6ZShtLCBzdGFydF94LCBzdGFydF95LCBlbmRfeCwgZW5kX3ksIGRpcmVjdGlvbl9ncmlkLCBkYXRhX2dvX2luX2N1cnJlbnQsIDEsICdTJyk7CiAgICBwcmludGYoIiVkIHNvbHV0aW9ucy5cbiIsIG5zb2wpOwp9CgppbnQgbWFpbigpIHsKICAgIFByb2dyYW1fcnVuKCk7CiAgICBwcmludGYoIkNvdW50IGRhdGEgc2F2ZWQ6ICVkXG4iLCBjb3VudF9kYXRhX3NhdmUpOwogICAgc2hvd19kYXRhX2dldCgpOwogICAgcmV0dXJuIDA7Cn0K