const int MAXN = 1005; // 最大位数
struct BigInt {
    int d[MAXN]; // 存储数字，d[0]是个位，d[1]是十位，...
    int len; // 数字长度
    BigInt() {
        memset(d, 0, sizeof(d));
        len = 0;
    }
};
// 比较两个高精度数的大小
int compare(BigInt a, BigInt b) {
    if(a.len != b.len) return a.len > b.len ? 1 : -1;
    for(int i = a.len - 1; i >= 0; i--) {
        if(a.d[i] != b.d[i]) return a.d[i] > b.d[i] ? 1 : -1;
    }
    return 0;
}
// 高精度减法
BigInt sub(BigInt a, BigInt b) {
    BigInt c;
    for(int i = 0; i < a.len; i++) {
        c.d[i] += a.d[i] - b.d[i];
        if(c.d[i] < 0) {
            c.d[i] += 10;
            c.d[i+1]--;
        }
    }
    c.len = a.len;
    while(c.len > 1 && c.d[c.len-1] == 0) c.len--;
    return c;
}
// 高精度除法（a/b，返回商和余数）
pair<BigInt, BigInt> div(BigInt a, BigInt b) {
    BigInt q, r; // q是商，r是余数
    if(compare(a, b) < 0) { // 如果a<b，商为0，余数为a
        q.len = 1;
        q.d[0] = 0;
        r = a;
        return make_pair(q, r);
    }
    // 初始化余数r为a的前b.len位
    r.len = b.len;
    for(int i = a.len - 1; i >= a.len - b.len; i--) {
        r.d[i - (a.len - b.len)] = a.d[i];
    }
    // 逐位计算商
    for(int i = a.len - b.len; i >= 0; i--) {
        // 把下一位加入余数
        if(r.len > 1 || r.d[0] != 0) {
            for(int j = r.len; j > 0; j--) {
                r.d[j] = r.d[j-1];
        }
        _______________________
        } else {
            r.d[0] = a.d[i]; 
            r.len = 1;
    }
    // 计算当前位的商
    while(compare(r, b) >= 0) {
        r = sub(r, b);
        q.d[i]++;
        }
    }
    // 确定商的长度
    q.len = a.len - b.len + 1;
    while(q.len > 1 && q.d[q.len-1] == 0) q.len--;
    // 处理余数前导零
    while(r.len > 1 && r.d[r.len-1] == 0) r.len--;
        return make_pair(q, r);
}