#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
char from_input(char input){
    if(input >= '0' && input <= '9'){
        return input - '0';
    }else{
        return input - 'a' + 10;
    }
}
int main() {
    FILE* fp = fopen("test.txt","r");
    char ch;
    int cnt = 0;
    int square = 0;
    int x = 0, y = 0;
    int width = 0, height = 0;
    char input[6250000];

    while ((ch = fgetc(fp)) != EOF) {
        if (ch != ' ' && ch != '\n') {
            input[cnt] = from_input(ch);
            cnt++;
        }
    }
    int size = sqrt((float)cnt)*2;
    unsigned short* b = malloc(sizeof(unsigned short)*cnt);
    unsigned short* c = malloc(sizeof(unsigned short)*cnt);
    unsigned short* prev_b = malloc(sizeof(unsigned short)*cnt);
    unsigned short* prev_c = malloc(sizeof(unsigned short)*cnt);
    for(int i = 0 ; i < size; ++i){
        prev_c[i] = 1 - ((input[i/4] >> (3 - (i%4))) & 1u);
        printf("%d ",prev_c[i]);
        prev_b[i] = prev_c[i];
    }
    printf("\n");
    for(int i = 1; i < size; ++i){
        b[0] = 1 - ((input[(size/4)*i] >> 3) & 1u);
        c[0] = b[0];
        for(int j = 1; j < size; ++j){
            if((input[(size/4)*i + j/4] >> (3-(j%4)))&1u == 1){
                b[j] = 0;
                c[j] = 0;
            }else{
                /*
                if(i == size-1 || j == size-1){
                    b[j] = 0;
                    c[j] = 0;
                    continue;
                }
                */
                b[j] = __min( prev_b[j],b[j-1])+1;
                c[j] = __max(1 + prev_c[j], c[j-1]);
            }
            printf("%d ",b[j]);
            if(square < (int)(b[j])*(int)(c[j])){
                x = i - c[j] + 1;
                y = j - b[j] + 1;
                width = c[j];
                height = b[j];
            }
        }
        for(int j = 0;j < size; ++j){
            prev_c[j] = c[j];
            prev_b[j] = b[j];
        }
        printf("\n");
    }
    free(prev_b);
    free(prev_c);
    free(c);
    free(b);
    //printf("%d %d %d %d\n",x,y,width,height);