int superDigitInt(uint64_t n) {
    if (n < 10)
        return n;
    uint64_t v = 0;
    while (n) {
        v += n % 10;
        n /= 10;
    }
    return superDigitInt(v);
}

int superDigit(string n, int k) {
    auto uncharify = [&k](uint64_t acc, const char c) {
        return acc + int(c - '0');
    };
    // This won't work for n > 10^19
    uint64_t prod = accumulate(n.begin(), n.end(), 0ULL, uncharify) * k;
    return superDigitInt(prod);
}

string sumDigits(string n) {
    string result = "0";
    for (int i = n.size() - 1; i >= 0; i--) {
        const char ni  = n[i] - '0';
        const char r = result.back() - '0';
        char sum = ni + r;
        result.back() = '0' + sum % 10;
        char carryOver = sum / 10;
        int pos = result.size() - 2;
        while (pos >= 0 && carryOver > 0) {
            char p = result[pos] - '0';
            sum = carryOver + p;
            result[pos] = '0' + sum % 10;
            carryOver = sum / 10;
        }
        if (carryOver > 0) {
            result.insert(result.begin(), carryOver + '0');
        }
    }
    return result;
}

int superDigit(string n)
{
    if (n.size() == 1) {
        return n.at(0) - '0';
    }
    return superDigit(sumDigits(n));
}

string multiply(string n, int k) 
{
    string result;
    vector<uint8_t> dig;
    for (int i = k; i > 0; i /= 10)
        dig.push_back(i % 10);
    reverse(dig.begin(), dig.end());
    vector<tuple<uint8_t, uint8_t>> t(dig.size() + 1);
    for (int i = 0; i < dig.size(); ++i) {
        n.insert(n.begin(), '0');
    }
    while (n.size() > 0) {
        result.insert(result.begin(), get<0>(t[0]) / 10); 
        const char cur = n.back() - '0';
        for (int i = 0; i < dig.size(); i++) {
            auto &[a, b] = t[i];
            const uint8_t c = get<0>(t[i + 1]);
            const uint8_t prod = cur * dig[i] + b;
            a = c + prod % 10;
            b = prod / 10;
        }
        result.front() = result.front() + get<0>(t[0]) % 10 + '0';
        n.pop_back();
    }
    result.erase(result.begin(), find_if(result.begin(), result.end(),
        [](const char& c) { return c != '0'; }));
    return result;
}

int superDigit(string n, int k)
{
    return superDigit(multiply(n, k));
}