#include <stdio.h>  // для ввода/вывода
#include <string.h> // для строк
#include <stdlib.h>
#include <time.h>
 
int isCorrectMatrix(const char type[])
{
    char input[100];
    while (1)
    {
        printf("Write sequence number of matrix: ");
 
        fgets(input, sizeof(input), stdin);
 
        input[strcspn(input, "\n")] = 0;
 
        int temp, n;
        if (sscanf(input, "%d%n", &temp, &n) == 1 && n == strlen(input) && temp > 0)
        {
            return temp;
        }
        else
        {
            printf("-------------------------\nIncorrect input!\n");
        };
    }
}
 
int determinantFunc(int **matrix, int n) {
    // порядок равен 2 => детерминант равен единственному элементу
    if (n == 1) {
        return matrix[0][0];
    }
 
    // порядок равен 2 => используем формулу для 2x2 детерминанта
    if (n == 2) {
        return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
    }
 
    // инициализируем переменную для хранения итогового детерминанта
    int det = 0;
 
    // инициализируем знак для чередования плюса и минуса в сумме (начинаем с +)
    int sign = 1;
 
    // для каждого i создаём подматрицу, учитывая минор, исключая строку 0 и столбец i.
    for (int i = 0; i < n; i++) {
 
        // выделяем память для подматрицы размером n x n, исключая строку 0 и столбец i
        int **submatrix = (int **)malloc((n-1) * sizeof(int *));
        for (int k = 0; k < n-1; k++) {
            submatrix[k] = (int *)malloc((n-1) * sizeof(int));
        }
 
        // заполняем подматрицу: копируем элементы из строк 1 до n-1, пропуская столбец i
        for (int row = 1; row < n; row++) {
            int col_index = 0;  // индекс столбца в подматрице
            for (int col = 0; col < n; col++) {
                if (col != i) {  // пропускаем столбец i
                    submatrix[row-1][col_index++] = matrix[row][col];
                }
            }
        }
 
        // добавляем к детерминанту: (+1 или -1) * элемент первой строки и столбца i * детерминант подматрицы
        det += sign * matrix[0][i] * determinantFunc(submatrix, n-1);
 
        // чередуем -1 и +1
        sign = -sign;
 
        for (int k = 0; k < n-1; k++) {
            free(submatrix[k]);
        }
        free(submatrix);
    }
 
    return det;
}
 
int CramerMethod(int **matrix, int sequence_number, int *linesResultInSystem)
{
    int **delta = (int **)malloc(sequence_number * sizeof(int *));
 
    if (delta == NULL)
    {
        printf("Memory error!\n");
        free(delta);
        return 1;
    }
 
    for (int i = 0; i < sequence_number; i++)
    {
        delta[i] = (int *)malloc(sequence_number * sizeof(int));
 
        if (delta[i] == NULL)
        {
            printf("Memory error!\n");
            for (int k = 0; k < i; k++)
            {
                free(delta[k]);
            }
            free(delta);
            return 1;
        }
 
        for (int j = 0; j < sequence_number; j++)
        {
            delta[i][j] = matrix[i][j];
        }
    }
 
    // главный детерминант
    int determinantNumber = determinantFunc(delta, sequence_number);
 
    for (int i = 0; i < sequence_number; i++)
    {
        free(delta[i]);
    }
 
    free(delta);
 
    printf("\n------------------\n\nDeterminant of main delta: %d\n", determinantNumber);
 
    // остальные детерминанты и высчитывание иксов
    if (determinantNumber == 0)
    {
        printf("\n!!!!!!!!!!!!!!\nInvalid method of Cramer, continue on next method...\n!!!!!!!!!!!!!!\n");
        return 1;
    }
    for (int delta_numeric = 1; delta_numeric <= sequence_number; delta_numeric++)
    {
        int **delta_another = (int **)malloc(sequence_number * sizeof(int *));
        for (int i = 0; i < sequence_number; i++)
        {
            delta_another[i] = (int *)malloc(sequence_number * sizeof(int));
 
            if (delta_another[i] == NULL)
            {
                printf("Memory error!\n");
                for (int k = 0; k < i; k++)
                {
                    free(delta_another[k]);
                }
                free(delta_another);
                return 1;
            }
 
            for (int j = 0; j < sequence_number; j++)
            {
                delta_another[i][j] = matrix[i][j];
            }
            delta_another[i][delta_numeric - 1] = linesResultInSystem[i];
        }
 
        int anotherDeterminantNumber = determinantFunc(delta_another, sequence_number);
 
        float mainX;
 
        mainX = (float)anotherDeterminantNumber / determinantNumber;
 
        printf("x%d: %.2f; ", delta_numeric, mainX);
        for (int i = 0; i < sequence_number; i++)
        {
            free(delta_another[i]);
        }
        free(delta_another);
    }
}
 
int main()
{
    // рандом
    srand(time(NULL));
 
    // порядок матрицы
    int sequence_number;
 
    // проверка целочисленности матрицы
    sequence_number = isCorrectMatrix("sequence_number");
 
    // объявление матрицы и результата линии в системе матриц
    int *linesResultInSystem = (int *)malloc(sequence_number * sizeof(int));
    int **matrix = (int **)malloc(sequence_number * sizeof(int *));
 
    // проверка достатка памяти
    if (matrix == NULL)
    {
        printf("Memory error!\n");
        free(matrix);
        return 1;
    }
 
    // наполнение матрицы и результата линии в системе матриц рандомными числами от 0 до 9
    for (int i = 0; i < sequence_number; i++)
    {
        linesResultInSystem[i] = rand() % 10;
        matrix[i] = (int *)malloc(sequence_number * sizeof(int));
        if (matrix[i] == NULL)
        {
            printf("Memory error!\n");
            for (int k = 0; k < i; k++)
            {
                free(matrix[k]);
            }
            free(matrix);
            return 1;
        }
        for (int j = 0; j < sequence_number; j++)
        {
            matrix[i][j] = rand() % 10;
        }
    }
 
    printf("\n-------------\nYour generated matrix: \n");
 
    // вывод системы матриц
    for (int i = 0; i < sequence_number; i++)
    {
        printf("\n");
        for (int j = 0; j < sequence_number; j++)
        {
            if (j > 0)
            {
                printf(" + %dx", matrix[i][j]);
            }
            else
            {
                printf("%dx", matrix[i][j]);
            }
        }
        printf(" = %d", linesResultInSystem[i]);
    }
 
    int resultOfCramer = CramerMethod(matrix, sequence_number, linesResultInSystem);
 
    if (resultOfCramer == 0)
    {
        return 1;
    }
 
    for (int i = 0; i < sequence_number; i++) {
        free(matrix[i]);
    }
    free(matrix);
    free(linesResultInSystem);
 
    return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+ICAvLyDQtNC70Y8g0LLQstC+0LTQsC/QstGL0LLQvtC00LAKI2luY2x1ZGUgPHN0cmluZy5oPiAvLyDQtNC70Y8g0YHRgtGA0L7QugojaW5jbHVkZSA8c3RkbGliLmg+CiNpbmNsdWRlIDx0aW1lLmg+CgppbnQgaXNDb3JyZWN0TWF0cml4KGNvbnN0IGNoYXIgdHlwZVtdKQp7CiAgICBjaGFyIGlucHV0WzEwMF07CiAgICB3aGlsZSAoMSkKICAgIHsKICAgICAgICBwcmludGYoIldyaXRlIHNlcXVlbmNlIG51bWJlciBvZiBtYXRyaXg6ICIpOwoKICAgICAgICBmZ2V0cyhpbnB1dCwgc2l6ZW9mKGlucHV0KSwgc3RkaW4pOwoKICAgICAgICBpbnB1dFtzdHJjc3BuKGlucHV0LCAiXG4iKV0gPSAwOwoKICAgICAgICBpbnQgdGVtcCwgbjsKICAgICAgICBpZiAoc3NjYW5mKGlucHV0LCAiJWQlbiIsICZ0ZW1wLCAmbikgPT0gMSAmJiBuID09IHN0cmxlbihpbnB1dCkgJiYgdGVtcCA+IDApCiAgICAgICAgewogICAgICAgICAgICByZXR1cm4gdGVtcDsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgcHJpbnRmKCItLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tXG5JbmNvcnJlY3QgaW5wdXQhXG4iKTsKICAgICAgICB9OwogICAgfQp9CgppbnQgZGV0ZXJtaW5hbnRGdW5jKGludCAqKm1hdHJpeCwgaW50IG4pIHsKICAgIC8vINC/0L7RgNGP0LTQvtC6INGA0LDQstC10L0gMiA9PiDQtNC10YLQtdGA0LzQuNC90LDQvdGCINGA0LDQstC10L0g0LXQtNC40L3RgdGC0LLQtdC90L3QvtC80YMg0Y3Qu9C10LzQtdC90YLRgwogICAgaWYgKG4gPT0gMSkgewogICAgICAgIHJldHVybiBtYXRyaXhbMF1bMF07CiAgICB9CiAgICAKICAgIC8vINC/0L7RgNGP0LTQvtC6INGA0LDQstC10L0gMiA9PiDQuNGB0L/QvtC70YzQt9GD0LXQvCDRhNC+0YDQvNGD0LvRgyDQtNC70Y8gMngyINC00LXRgtC10YDQvNC40L3QsNC90YLQsAogICAgaWYgKG4gPT0gMikgewogICAgICAgIHJldHVybiBtYXRyaXhbMF1bMF0gKiBtYXRyaXhbMV1bMV0gLSBtYXRyaXhbMF1bMV0gKiBtYXRyaXhbMV1bMF07CiAgICB9CiAgICAKICAgIC8vINC40L3QuNGG0LjQsNC70LjQt9C40YDRg9C10Lwg0L/QtdGA0LXQvNC10L3QvdGD0Y4g0LTQu9GPINGF0YDQsNC90LXQvdC40Y8g0LjRgtC+0LPQvtCy0L7Qs9C+INC00LXRgtC10YDQvNC40L3QsNC90YLQsAogICAgaW50IGRldCA9IDA7CiAgICAKICAgIC8vINC40L3QuNGG0LjQsNC70LjQt9C40YDRg9C10Lwg0LfQvdCw0Log0LTQu9GPINGH0LXRgNC10LTQvtCy0LDQvdC40Y8g0L/Qu9GO0YHQsCDQuCDQvNC40L3Rg9GB0LAg0LIg0YHRg9C80LzQtSAo0L3QsNGH0LjQvdCw0LXQvCDRgSArKQogICAgaW50IHNpZ24gPSAxOwogICAgCiAgICAvLyDQtNC70Y8g0LrQsNC20LTQvtCz0L4gaSDRgdC+0LfQtNCw0ZHQvCDQv9C+0LTQvNCw0YLRgNC40YbRgywg0YPRh9C40YLRi9Cy0LDRjyDQvNC40L3QvtGALCDQuNGB0LrQu9GO0YfQsNGPINGB0YLRgNC+0LrRgyAwINC4INGB0YLQvtC70LHQtdGGIGkuCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykgewogICAgICAgIAogICAgICAgIC8vINCy0YvQtNC10LvRj9C10Lwg0L/QsNC80Y/RgtGMINC00LvRjyDQv9C+0LTQvNCw0YLRgNC40YbRiyDRgNCw0LfQvNC10YDQvtC8IG4geCBuLCDQuNGB0LrQu9GO0YfQsNGPINGB0YLRgNC+0LrRgyAwINC4INGB0YLQvtC70LHQtdGGIGkKICAgICAgICBpbnQgKipzdWJtYXRyaXggPSAoaW50ICoqKW1hbGxvYygobi0xKSAqIHNpemVvZihpbnQgKikpOwogICAgICAgIGZvciAoaW50IGsgPSAwOyBrIDwgbi0xOyBrKyspIHsKICAgICAgICAgICAgc3VibWF0cml4W2tdID0gKGludCAqKW1hbGxvYygobi0xKSAqIHNpemVvZihpbnQpKTsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgLy8g0LfQsNC/0L7Qu9C90Y/QtdC8INC/0L7QtNC80LDRgtGA0LjRhtGDOiDQutC+0L/QuNGA0YPQtdC8INGN0LvQtdC80LXQvdGC0Ysg0LjQtyDRgdGC0YDQvtC6IDEg0LTQviBuLTEsINC/0YDQvtC/0YPRgdC60LDRjyDRgdGC0L7Qu9Cx0LXRhiBpCiAgICAgICAgZm9yIChpbnQgcm93ID0gMTsgcm93IDwgbjsgcm93KyspIHsKICAgICAgICAgICAgaW50IGNvbF9pbmRleCA9IDA7ICAvLyDQuNC90LTQtdC60YEg0YHRgtC+0LvQsdGG0LAg0LIg0L/QvtC00LzQsNGC0YDQuNGG0LUKICAgICAgICAgICAgZm9yIChpbnQgY29sID0gMDsgY29sIDwgbjsgY29sKyspIHsKICAgICAgICAgICAgICAgIGlmIChjb2wgIT0gaSkgeyAgLy8g0L/RgNC+0L/Rg9GB0LrQsNC10Lwg0YHRgtC+0LvQsdC10YYgaQogICAgICAgICAgICAgICAgICAgIHN1Ym1hdHJpeFtyb3ctMV1bY29sX2luZGV4KytdID0gbWF0cml4W3Jvd11bY29sXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAKICAgICAgICAvLyDQtNC+0LHQsNCy0LvRj9C10Lwg0Log0LTQtdGC0LXRgNC80LjQvdCw0L3RgtGDOiAoKzEg0LjQu9C4IC0xKSAqINGN0LvQtdC80LXQvdGCINC/0LXRgNCy0L7QuSDRgdGC0YDQvtC60Lgg0Lgg0YHRgtC+0LvQsdGG0LAgaSAqINC00LXRgtC10YDQvNC40L3QsNC90YIg0L/QvtC00LzQsNGC0YDQuNGG0YsKICAgICAgICBkZXQgKz0gc2lnbiAqIG1hdHJpeFswXVtpXSAqIGRldGVybWluYW50RnVuYyhzdWJtYXRyaXgsIG4tMSk7CgogICAgICAgIC8vINGH0LXRgNC10LTRg9C10LwgLTEg0LggKzEKICAgICAgICBzaWduID0gLXNpZ247CgogICAgICAgIGZvciAoaW50IGsgPSAwOyBrIDwgbi0xOyBrKyspIHsKICAgICAgICAgICAgZnJlZShzdWJtYXRyaXhba10pOwogICAgICAgIH0KICAgICAgICBmcmVlKHN1Ym1hdHJpeCk7CiAgICB9CiAgICAKICAgIHJldHVybiBkZXQ7Cn0KCmludCBDcmFtZXJNZXRob2QoaW50ICoqbWF0cml4LCBpbnQgc2VxdWVuY2VfbnVtYmVyLCBpbnQgKmxpbmVzUmVzdWx0SW5TeXN0ZW0pCnsKICAgIGludCAqKmRlbHRhID0gKGludCAqKiltYWxsb2Moc2VxdWVuY2VfbnVtYmVyICogc2l6ZW9mKGludCAqKSk7CgogICAgaWYgKGRlbHRhID09IE5VTEwpCiAgICB7CiAgICAgICAgcHJpbnRmKCJNZW1vcnkgZXJyb3IhXG4iKTsKICAgICAgICBmcmVlKGRlbHRhKTsKICAgICAgICByZXR1cm4gMTsKICAgIH0KCiAgICBmb3IgKGludCBpID0gMDsgaSA8IHNlcXVlbmNlX251bWJlcjsgaSsrKQogICAgewogICAgICAgIGRlbHRhW2ldID0gKGludCAqKW1hbGxvYyhzZXF1ZW5jZV9udW1iZXIgKiBzaXplb2YoaW50KSk7CgogICAgICAgIGlmIChkZWx0YVtpXSA9PSBOVUxMKQogICAgICAgIHsKICAgICAgICAgICAgcHJpbnRmKCJNZW1vcnkgZXJyb3IhXG4iKTsKICAgICAgICAgICAgZm9yIChpbnQgayA9IDA7IGsgPCBpOyBrKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGZyZWUoZGVsdGFba10pOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGZyZWUoZGVsdGEpOwogICAgICAgICAgICByZXR1cm4gMTsKICAgICAgICB9CgogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgc2VxdWVuY2VfbnVtYmVyOyBqKyspCiAgICAgICAgewogICAgICAgICAgICBkZWx0YVtpXVtqXSA9IG1hdHJpeFtpXVtqXTsKICAgICAgICB9CiAgICB9CgogICAgLy8g0LPQu9Cw0LLQvdGL0Lkg0LTQtdGC0LXRgNC80LjQvdCw0L3RggogICAgaW50IGRldGVybWluYW50TnVtYmVyID0gZGV0ZXJtaW5hbnRGdW5jKGRlbHRhLCBzZXF1ZW5jZV9udW1iZXIpOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc2VxdWVuY2VfbnVtYmVyOyBpKyspCiAgICB7CiAgICAgICAgZnJlZShkZWx0YVtpXSk7CiAgICB9CgogICAgZnJlZShkZWx0YSk7CgogICAgcHJpbnRmKCJcbi0tLS0tLS0tLS0tLS0tLS0tLVxuXG5EZXRlcm1pbmFudCBvZiBtYWluIGRlbHRhOiAlZFxuIiwgZGV0ZXJtaW5hbnROdW1iZXIpOwoKICAgIC8vINC+0YHRgtCw0LvRjNC90YvQtSDQtNC10YLQtdGA0LzQuNC90LDQvdGC0Ysg0Lgg0LLRi9GB0YfQuNGC0YvQstCw0L3QuNC1INC40LrRgdC+0LIKICAgIGlmIChkZXRlcm1pbmFudE51bWJlciA9PSAwKQogICAgewogICAgICAgIHByaW50ZigiXG4hISEhISEhISEhISEhIVxuSW52YWxpZCBtZXRob2Qgb2YgQ3JhbWVyLCBjb250aW51ZSBvbiBuZXh0IG1ldGhvZC4uLlxuISEhISEhISEhISEhISFcbiIpOwogICAgICAgIHJldHVybiAxOwogICAgfQogICAgZm9yIChpbnQgZGVsdGFfbnVtZXJpYyA9IDE7IGRlbHRhX251bWVyaWMgPD0gc2VxdWVuY2VfbnVtYmVyOyBkZWx0YV9udW1lcmljKyspCiAgICB7CiAgICAgICAgaW50ICoqZGVsdGFfYW5vdGhlciA9IChpbnQgKiopbWFsbG9jKHNlcXVlbmNlX251bWJlciAqIHNpemVvZihpbnQgKikpOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc2VxdWVuY2VfbnVtYmVyOyBpKyspCiAgICAgICAgewogICAgICAgICAgICBkZWx0YV9hbm90aGVyW2ldID0gKGludCAqKW1hbGxvYyhzZXF1ZW5jZV9udW1iZXIgKiBzaXplb2YoaW50KSk7CgogICAgICAgICAgICBpZiAoZGVsdGFfYW5vdGhlcltpXSA9PSBOVUxMKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBwcmludGYoIk1lbW9yeSBlcnJvciFcbiIpOwogICAgICAgICAgICAgICAgZm9yIChpbnQgayA9IDA7IGsgPCBpOyBrKyspCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgZnJlZShkZWx0YV9hbm90aGVyW2tdKTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGZyZWUoZGVsdGFfYW5vdGhlcik7CiAgICAgICAgICAgICAgICByZXR1cm4gMTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBzZXF1ZW5jZV9udW1iZXI7IGorKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgZGVsdGFfYW5vdGhlcltpXVtqXSA9IG1hdHJpeFtpXVtqXTsKICAgICAgICAgICAgfQogICAgICAgICAgICBkZWx0YV9hbm90aGVyW2ldW2RlbHRhX251bWVyaWMgLSAxXSA9IGxpbmVzUmVzdWx0SW5TeXN0ZW1baV07CiAgICAgICAgfQoKICAgICAgICBpbnQgYW5vdGhlckRldGVybWluYW50TnVtYmVyID0gZGV0ZXJtaW5hbnRGdW5jKGRlbHRhX2Fub3RoZXIsIHNlcXVlbmNlX251bWJlcik7CgogICAgICAgIGZsb2F0IG1haW5YOwoKICAgICAgICBtYWluWCA9IChmbG9hdClhbm90aGVyRGV0ZXJtaW5hbnROdW1iZXIgLyBkZXRlcm1pbmFudE51bWJlcjsKCiAgICAgICAgcHJpbnRmKCJ4JWQ6ICUuMmY7ICIsIGRlbHRhX251bWVyaWMsIG1haW5YKTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IHNlcXVlbmNlX251bWJlcjsgaSsrKQogICAgICAgIHsKICAgICAgICAgICAgZnJlZShkZWx0YV9hbm90aGVyW2ldKTsKICAgICAgICB9CiAgICAgICAgZnJlZShkZWx0YV9hbm90aGVyKTsKICAgIH0KfQoKaW50IG1haW4oKQp7CiAgICAvLyDRgNCw0L3QtNC+0LwKICAgIHNyYW5kKHRpbWUoTlVMTCkpOwoKICAgIC8vINC/0L7RgNGP0LTQvtC6INC80LDRgtGA0LjRhtGLCiAgICBpbnQgc2VxdWVuY2VfbnVtYmVyOwoKICAgIC8vINC/0YDQvtCy0LXRgNC60LAg0YbQtdC70L7Rh9C40YHQu9C10L3QvdC+0YHRgtC4INC80LDRgtGA0LjRhtGLCiAgICBzZXF1ZW5jZV9udW1iZXIgPSBpc0NvcnJlY3RNYXRyaXgoInNlcXVlbmNlX251bWJlciIpOwoKICAgIC8vINC+0LHRitGP0LLQu9C10L3QuNC1INC80LDRgtGA0LjRhtGLINC4INGA0LXQt9GD0LvRjNGC0LDRgtCwINC70LjQvdC40Lgg0LIg0YHQuNGB0YLQtdC80LUg0LzQsNGC0YDQuNGGCiAgICBpbnQgKmxpbmVzUmVzdWx0SW5TeXN0ZW0gPSAoaW50ICopbWFsbG9jKHNlcXVlbmNlX251bWJlciAqIHNpemVvZihpbnQpKTsKICAgIGludCAqKm1hdHJpeCA9IChpbnQgKiopbWFsbG9jKHNlcXVlbmNlX251bWJlciAqIHNpemVvZihpbnQgKikpOwoKICAgIC8vINC/0YDQvtCy0LXRgNC60LAg0LTQvtGB0YLQsNGC0LrQsCDQv9Cw0LzRj9GC0LgKICAgIGlmIChtYXRyaXggPT0gTlVMTCkKICAgIHsKICAgICAgICBwcmludGYoIk1lbW9yeSBlcnJvciFcbiIpOwogICAgICAgIGZyZWUobWF0cml4KTsKICAgICAgICByZXR1cm4gMTsKICAgIH0KCiAgICAvLyDQvdCw0L/QvtC70L3QtdC90LjQtSDQvNCw0YLRgNC40YbRiyDQuCDRgNC10LfRg9C70YzRgtCw0YLQsCDQu9C40L3QuNC4INCyINGB0LjRgdGC0LXQvNC1INC80LDRgtGA0LjRhiDRgNCw0L3QtNC+0LzQvdGL0LzQuCDRh9C40YHQu9Cw0LzQuCDQvtGCIDAg0LTQviA5CiAgICBmb3IgKGludCBpID0gMDsgaSA8IHNlcXVlbmNlX251bWJlcjsgaSsrKQogICAgewogICAgICAgIGxpbmVzUmVzdWx0SW5TeXN0ZW1baV0gPSByYW5kKCkgJSAxMDsKICAgICAgICBtYXRyaXhbaV0gPSAoaW50ICopbWFsbG9jKHNlcXVlbmNlX251bWJlciAqIHNpemVvZihpbnQpKTsKICAgICAgICBpZiAobWF0cml4W2ldID09IE5VTEwpCiAgICAgICAgewogICAgICAgICAgICBwcmludGYoIk1lbW9yeSBlcnJvciFcbiIpOwogICAgICAgICAgICBmb3IgKGludCBrID0gMDsgayA8IGk7IGsrKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgZnJlZShtYXRyaXhba10pOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGZyZWUobWF0cml4KTsKICAgICAgICAgICAgcmV0dXJuIDE7CiAgICAgICAgfQogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgc2VxdWVuY2VfbnVtYmVyOyBqKyspCiAgICAgICAgewogICAgICAgICAgICBtYXRyaXhbaV1bal0gPSByYW5kKCkgJSAxMDsKICAgICAgICB9CiAgICB9CgogICAgcHJpbnRmKCJcbi0tLS0tLS0tLS0tLS1cbllvdXIgZ2VuZXJhdGVkIG1hdHJpeDogXG4iKTsKCiAgICAvLyDQstGL0LLQvtC0INGB0LjRgdGC0LXQvNGLINC80LDRgtGA0LjRhgogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBzZXF1ZW5jZV9udW1iZXI7IGkrKykKICAgIHsKICAgICAgICBwcmludGYoIlxuIik7CiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBzZXF1ZW5jZV9udW1iZXI7IGorKykKICAgICAgICB7CiAgICAgICAgICAgIGlmIChqID4gMCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcHJpbnRmKCIgKyAlZHgiLCBtYXRyaXhbaV1bal0pOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgcHJpbnRmKCIlZHgiLCBtYXRyaXhbaV1bal0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHByaW50ZigiID0gJWQiLCBsaW5lc1Jlc3VsdEluU3lzdGVtW2ldKTsKICAgIH0KCiAgICBpbnQgcmVzdWx0T2ZDcmFtZXIgPSBDcmFtZXJNZXRob2QobWF0cml4LCBzZXF1ZW5jZV9udW1iZXIsIGxpbmVzUmVzdWx0SW5TeXN0ZW0pOwoKICAgIGlmIChyZXN1bHRPZkNyYW1lciA9PSAwKQogICAgewogICAgICAgIHJldHVybiAxOwogICAgfQoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgc2VxdWVuY2VfbnVtYmVyOyBpKyspIHsKICAgICAgICBmcmVlKG1hdHJpeFtpXSk7CiAgICB9CiAgICBmcmVlKG1hdHJpeCk7CiAgICBmcmVlKGxpbmVzUmVzdWx0SW5TeXN0ZW0pOwoKICAgIHJldHVybiAwOwp9

MTA=

10