const unsigned long long base = 1ULL << 32ULL;

typedef struct longN{
    unsigned long long dig[626];
    unsigned long long length;
} longN;


longN SetLongN(unsigned long long value){
    longN temp;
    temp.dig[0] = value;
    temp.length = 1;
    return temp;
}

unsigned long long Max(unsigned long long x,unsigned long long y){
    if (x>y) return x;
    return y;
}

longN LongNPlusLongN(longN *x, longN *y){
    unsigned long long z = 0;
    x->length = Max(x->length,y->length) + 1;
    for (long long i = 0; i < x->length; ++i){
        if (i < x->length) z+=x->dig[i];
        if (i < y->length) z+=y->dig[i];
        x->dig[i] = z%base;
        z/=base;
    }
    if (x -> dig[x->length - 1] == 0) x->length = x->length - 1;
    return *x;
}

longN LongNXLongN(longN *x, unsigned long long y){
    longN temp;
    unsigned long long z;
    temp.length = x->length + 1;
    memset(temp.dig, 0, sizeof(unsigned long long) * temp.length);
    unsigned long long newLength = 0;
    for (int i = 0; i < x->length; i++){
        z = 0;
        z += temp.dig[i];
        z += (unsigned long long)(x->dig[i]*y);
        temp.dig[i] = z % base;
        z /= base;
        if (i > newLength) newLength = i;
        if (z != 0){
            temp.dig[i + 1] = temp.dig[i + 1] + z;
            if (i + 1 > newLength) newLength = i + 1;
        }
    }
    temp.length = newLength + 1;
    return temp;
}

//longN LongNXLongN(longN *x, unsigned long long y){
//    longN lY = SetLongN(0);
//    longN lX = LongNPlusLongN(&lY,x);
//    while (y){
//        if (y%2){
//            lY = LongNPlusLongN(&lY,&lX);
//        }
//        lX = LongNPlusLongN(&lX,&lX);
//        y/=2;
//    }
//    return lY;
//}

longN LongNDivLongN(longN *x, unsigned long long y, unsigned long long *rem){
    longN temp;
    temp.length = x->length;
    memset(temp.dig, 0, (x->length * sizeof(unsigned long long)));
    int newLength = -1;
    unsigned long long z = 0;
    for (long long i = x->length - 1; i >= 0; i--){
        z = z * base + x->dig[i];
        temp.dig[i] = z / y;
        z = z % y;
        if (temp.dig[i] != 0 && i > newLength) newLength = i;
    }
    *rem = z;
    if (newLength == -1){
        temp.length = 1;
        temp.dig[0] = 0;
    }else{
        temp.length = newLength + 1;
    }
    return temp;
}