#include <stdio.h>

void next_rand(unsigned int *rand);
void init_arr_puyo(int arr[256], int color);
void shuffle_arr_puyo(int arr[256], unsigned int *rand);
void init_arr_sort(int arr[126]);
void count_puyo_color(int arr_12[24], int arr_count[4]);
void dispos_puyo(long long int board[3], int arr[24], int num);
int count_bit(long long int bits);
int count_erase_puyo(long long int board[5]);

int main(void) {
    int i, j, k;

    unsigned int seed;
    unsigned int tmp_seed;
    unsigned int rand;

    int arr_amakuchi[256];
    int arr_tyukara[256];
    int arr_sort[126];
    int arr_puyo_12[24];
    int arr_num_puyo_color[4];
    long long int board_puyo[5];

    int num_erase_puyo;

    board_puyo[0] = 0;
    board_puyo[4] = 0;

    long long int tmp[3];


    for (i = 0x42000; i <= 0x400000; i++) {
        seed = i;   // First Seed
        tmp_seed = seed;

        for (j = 0; j < 5; j++) {
            next_rand(&tmp_seed);
        }

        /* Init Rand */
        rand = tmp_seed >> 16;
        for (j = 0; j < 5; j++) {
            next_rand(&rand);
        }

        /* Init Memory */
        init_arr_puyo(arr_amakuchi, 3);
        init_arr_puyo(arr_tyukara, 4);

        /* Shuffle Memory */
        shuffle_arr_puyo(arr_amakuchi, &rand);
        shuffle_arr_puyo(arr_tyukara, &rand);

        for (j = 0; j < 4; j++) {
            arr_tyukara[j] = arr_amakuchi[j];
            arr_num_puyo_color[j] = 0;
        }

        /* Make Sort Array*/
        init_arr_sort(arr_sort);

        /* Init 12 Puyo Array */
        for (j = 0; j < 24; j++) {
            arr_puyo_12[j] = arr_tyukara[j];

        }

        /* Count Each Puyo Color */
        count_puyo_color(arr_puyo_12, arr_num_puyo_color);

        if (arr_num_puyo_color[0] < 8 | arr_num_puyo_color[3] < 4) {
            continue;
        }


        for (j = 0; j < 126; j++) {
            /* Disposition Puyo*/
            dispos_puyo(&board_puyo[1], arr_puyo_12, arr_sort[j]);

            tmp[2] = board_puyo[3];
            tmp[1] = board_puyo[2];
            tmp[0] = board_puyo[1];

            /* Rensa and Count Erasing Puyo */
            num_erase_puyo = count_erase_puyo(board_puyo);
            if (num_erase_puyo >= 4) {
                num_erase_puyo = count_erase_puyo(board_puyo);
                if (num_erase_puyo >= 19) {
                    printf("seed: %08x, sort_num: %d\n", seed, j);

                    printf("\nsort: %d\n", arr_sort[j]);
                    printf("\n%016llx\n", tmp[2]);
                    printf("%016llx\n", tmp[1]);
                    printf("%016llx\n", tmp[0]);

                    printf("\n%016llx\n", board_puyo[3]);
                    printf("%016llx\n", board_puyo[2]);
                    printf("%016llx\n", board_puyo[1]);

                    printf("\n%d\n", num_erase_puyo);
                }
            }
        }
    }


    printf("end.");

    return 0;
}


void next_rand(unsigned int *rand) {
    *rand = (*rand * 0x5D588B65 + 0x269EC3) & 0xFFFFFFFF;
}

void init_arr_puyo(int arr[256], int color) {
    int i;
    for (i = 0; i < 256; i++) {
        arr[i] = i % color;
    }
}

void shuffle_arr_puyo(int arr[256], unsigned int *rand) {
    int i, j;
    int tmp;
    unsigned int num1, num2;

    for (i = 0; i < 15; i++) {
        for (j = 0; j < 8; j++) {
            next_rand(rand);
            num1 = (*rand >> 28) + i * 0x10;
            next_rand(rand);
            num2 = (*rand >> 28) + (i + 1) * 0x10;

            tmp = arr[num1];
            arr[num1] = arr[num2];
            arr[num2] = tmp;
        }
    }

    for (i = 0; i < 7; i++) {
        for (j = 0; j < 16; j++) {
            next_rand(rand);
            num1 = (*rand >> 27) + i * 0x20;
            next_rand(rand);
            num2 = (*rand >> 27) + (i + 1) * 0x20;

            tmp = arr[num1];
            arr[num1] = arr[num2];
            arr[num2] = tmp;
        }
    }

    for (i = 0; i < 3; i++) {
        for (j = 0; j < 32; j++) {
            next_rand(rand);
            num1 = (*rand >> 26) + i * 0x40;
            next_rand(rand);
            num2 = (*rand >> 26) + (i + 1) * 0x40;

            tmp = arr[num1];
            arr[num1] = arr[num2];
            arr[num2] = tmp;
        }
    }
}

void init_arr_sort(int arr[126]) {
    int i, j;
    int bit_cnt, arr_cnt = 0;

    for (i = 0; i < 512; i++) {

        bit_cnt = 0;
        for (j = 0; j < 9; j++) {
            if (i & (1 << j)) bit_cnt++;
        }

        if (bit_cnt == 4) {
            arr[arr_cnt] = i;
            arr_cnt++;
        }
    }
}

void count_puyo_color(int arr_12[24], int arr_count[4]) {
    int i, j;

    for (i = 0; i < 24; i++) {
        arr_count[arr_12[i]]++;
    }

    for (i = 0; i < 3; i++) {
        for (j = 3; j > i; j--) {
            if (arr_count[j - 1] < arr_count[j]) {
                arr_count[j - 1] ^= arr_count[j] ^= arr_count[j - 1] ^= arr_count[j];
            }
        }
    }
}

void dispos_puyo(long long int board[3], int arr[24], int num) {
    int i, j;
    unsigned long long int bit_mask;
    int cnt_column_4, cnt_column_5;

    for (i = 0; i < 3; i++) {
        board[i] = 0;
    }
    cnt_column_4 = 1;
    cnt_column_5 = 1;


    for (j = 0; j <= 11; j++) {
        if (j == 0) {
            board[1] |= (long long int)1 << arr[1];
            board[2] |= (long long int)1 << arr[0];
        }
        if (j >= 1 && j <= 9) {
            if (num & (1 << (j - 1))) {
                board[2] |= (long long int)1 << (arr[j * 2 + 1] + cnt_column_5 * 4);
                board[2] |= (long long int)1 << (arr[j * 2] + (cnt_column_5 + 1) * 4);
                cnt_column_5 += 2;
            }
            else {
                board[1] |= (long long int)1 << (arr[j * 2 + 1] + cnt_column_4 * 4);
                board[1] |= (long long int)1 << (arr[j * 2] + (cnt_column_4 + 1) * 4);
                cnt_column_4 += 2;
            }
        }
        if (j == 10) {
            board[1] |= (long long int)1 << (arr[20] + 44);
            board[1] |= (long long int)1 << (arr[21] + 48);
        }
        if (j == 11) {
            board[0] |= (long long int)1 << arr[23];
            board[0] |= (long long int)1 << (arr[22] + 4);
        }
    }

    bit_mask = ((board[1] >> 4) ^ board[1]) & 0x00000f000000000;
    bit_mask = (bit_mask << 4) | bit_mask;
    board[1] ^= bit_mask;

}

int count_bit(long long int bits) {
    const int bit_table[256] = {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
    };

    return  bit_table[bits & 0xff] + bit_table[(bits >> 8) & 0xff]
            + bit_table[(bits >> 16) & 0xff] + bit_table[(bits >> 24) & 0xff]
            + bit_table[(bits >> 32) & 0xff] + bit_table[(bits >> 40) & 0xff]
            + bit_table[(bits >> 48) & 0xff] + bit_table[(bits >> 56) & 0xff];
}

int count_erase_puyo(long long int board[5]) {
    int i, j;

    long long int link[5];
    long long int link_link_2[5];
    long long int link_3[5];
    long long int erase_color[5];
    long long int erase_integ[5];
    long long int abst_color[5];

    long long int drop_prot_mask[5];
    long long int drop_diff_mask[5];
    long long int tmp_board;

    int num_erase_puyo = 0;

    for (i = 0; i < 5; i++) {
        erase_integ[i] = 0;
    }

    for (i = 0; i < 4; i++) {
        for (j = 0; j < 5; j++) {
            link[j] = 0;
            link_link_2[j] = 0;
            link_3[j] = 0;
            erase_color[j] = 0;
            abst_color[j] = (board[j] >> i) & 0x1111111111111111;
            drop_prot_mask[j] = 0;
            drop_diff_mask[j] = 0;
        }

        for (j = 1; j <= 3; j++) {
            link[j] += (abst_color[j] & abst_color[j - 1]) & 0x0000ffffffffffff;
            link[j] += (abst_color[j] & abst_color[j + 1]) & 0x0000ffffffffffff;
            link[j] += (abst_color[j] & (abst_color[j] << 4)) & 0x0000ffffffffffff;
            link[j] += (abst_color[j] & ((abst_color[j] & 0x0000ffffffffffff) >> 4)) & 0x0000ffffffffffff;
        }

        for (j = 1; j <= 3; j++) {
            link_3[j] |= (link[j] + 0x1111111111111111 >> 2) & 0x1111111111111111;
        }

        for (j = 1; j <= 3; j++) {
            link[j] = ((link[j] + 0x2222222222222222) >> 2) & 0x1111111111111111;
        }

        for (j = 1; j <= 3; j++) {
            link_link_2[j] |= link[j] & link[j - 1] & 0x1111111111111111;
            link_link_2[j] |= link[j] & link[j + 1] & 0x1111111111111111;
            link_link_2[j] |= link[j] & (link[j] << 4) & 0x1111111111111111;
            link_link_2[j] |= link[j] & (link[j] >> 4) & 0x1111111111111111;
        }

        for (j = 1; j <= 3; j++) {
            erase_color[j] |= abst_color[j] & (link_link_2[j] | link_3[j]);
            erase_color[j] |= abst_color[j] & (link_link_2[j - 1] | link_3[j - 1]);
            erase_color[j] |= abst_color[j] & (link_link_2[j + 1] | link_3[j + 1]);
            erase_color[j] |= abst_color[j] & ((link_link_2[j] | link_3[j]) >> 4);
            erase_color[j] |= abst_color[j] & ((link_link_2[j] | link_3[j]) << 4);
            num_erase_puyo += count_bit(erase_color[j]);

            erase_color[j] = erase_color[j] + (erase_color[j] << 1) + (erase_color[j] << 2) + (erase_color[j] << 3);

            erase_integ[j] |= erase_color[j];
        }
    }

    while (erase_integ[1] | erase_integ[2] | erase_integ[3]) {
        for (j = 1; j <= 3; j++) {
            drop_prot_mask[j] = (erase_integ[j] ^ (erase_integ[j] - (long long int)1)) >> 1;
            drop_diff_mask[j] = (~erase_integ[j] - ((erase_integ[j] - 1) ^ erase_integ[j])) & erase_integ[j];

            tmp_board = board[j] & drop_prot_mask[j];
            board[j] = ((board[j] >> count_bit(drop_diff_mask[j])) & ~drop_prot_mask[j]) | tmp_board;

            erase_integ[j] = (erase_integ[j] ^ drop_diff_mask[j]) >> count_bit(drop_diff_mask[j]);
        }
    }

    return num_erase_puyo;
}