#include<stdio.h>
#include<stdlib.h>

int view(char *map)
/* 現在の升目の状態を確認する関数 */
{
    int i;
    printf("\tx---------x\n\t|");
    for(i=0; i<16; i++) {
        printf(" %X",map[i]);
        if(i%4==3) printf(" |\n\t|");
    }
    printf("\bx---------x\n");
    return 0;
}

int ini(char *map)
/* 初期化 */
{
    int i;
    for(i=0; i<16; i++) {
        map[i] = i+1;
    }
    map[i-1] = 0;
    return 0;
}

int randomize(char *map, char *now)
{
    char able, move;
    /* 1:Up 2:Down 4:Left 8:Right */

    able = movable(now);

    while(1) {
    move = 1;
    move = move << (rand()%4);
    if( (move & able) != 0 )break;
    }/* ランダムに移動方向を決める→動けるか判定 */
    switch(move)
    {
        case 1:
            swap(map+*now, map+*now-4);
            *now -= 4; break;
        case 2:
            swap(map+*now, map+*now+4);
            *now += 4; break;
        case 4:
            swap(map+*now, map+*now-1);
            *now -= 1; break;
        case 8:
            swap(map+*now, map+*now+1);
            *now += 1; break;
    }/* 移動実行 */

    return 0;
}

int swap(char *a, char *b)
{
    char swap;
    swap = *a;
    *a = *b;
    *b = swap;
    return 0;
}

int movable(char *now)
{
    /* 可動範囲判定 :  */
    char able=15;
    /* まずは上下左右自由に動けると仮定 */
    if(*now   <=  3) able -= 1;
    if(*now   >= 12) able -= 2;
    if(*now%4 ==  0) able -= 4;
    if(*now%4 ==  3) able -= 8;
    /* 可動性を削っていく */
    return able;
}

int trans(char *ch, char *move)
{

    *move = *ch - 'a';

    switch(*move)
    {
    case 22: *move = 1; break;
    case 18: *move = 2; break;
    case  0: *move = 4; break;
    case  3: *move = 8; break;
    default:
        printf("正しい選択をお願いします。\n");
        exit(1);
        break;
    }
}

int moving(char *map, char *now, char ch)
{
    char able, move;
    /* 1:Up 2:Down 4:Left 8:Right */

    trans(&ch, &move);
    /* 入力→移動コマンド変換 */

    able = movable(now);
    /* 動ける範囲を出力 */


    if( (move & able) == 0 ) {
        printf("そっちには動けない！！\n");
        return 1;
    }/* 動けるか判定 */

    switch(move)
    {
        case 1:
            swap(map+*now, map+*now-4);
            *now -= 4; break;
        case 2:
            swap(map+*now, map+*now+4);
            *now += 4; break;
        case 4:
            swap(map+*now, map+*now-1);
            *now -= 1; break;
        case 8:
            swap(map+*now, map+*now+1);
            *now += 1; break;
    }/* 移動実行 */

    return 0;
}

check(char *map)
{
    char i, flag = 0;
    for(i=0; i<15; i++) flag += ( map[i] != i+1 );
    if(!flag) {
        printf("\n完成！おめでとうございます！\n\n");
        exit(0);
    }
}

int main(void)
{
    char map[16], now = 15, ch;
    int re;
    srand((unsigned)time(NULL));
    ini(map);
    for(re=0; re<6; re++) randomize(map, &now);
    view(map);
    printf("\n\t初期化完了。\n");

    /* START */
    re = 0;
    while( (ch = getchar()) != EOF ) {
        if(ch == '\n') continue;
        fseek(stdin, 0, SEEK_END);
        re++;
        printf("\t%d回目\n",re);
        view(map);
        moving(map, &now, ch);
        check(map);
    }/* Ctrl+Dで終了　'\n'はエンター避け */

    return 0;
}