std::vector<long long> radix_sort_linked_list_arr(std::vector<long long>& arr, long long size) {
    auto first = new long long[size];
    auto last = new long long[size];
    auto next = new long long[size];
    std::fill(first, first + size, -1);
    std::fill(last, last + size, -1);
    std::fill(next, next + size, -1);

    // Sort by x % size
    for (long long i = 0; i < size; ++i) {
        long long r = arr[i] % size;
        if (first[r] == -1) {
            first[r] = i;
        } else {
            next[last[r]] = i;
        }
        last[r] = i;
    }

    // Sort by x / size
    auto First = new long long[size];
    auto Last = new long long[size];
    auto Next = new long long[size];
    std::fill(First, First + size, -1);
    std::fill(Last, Last + size, -1);
    std::fill(Next, Next + size, -1);

    for (long long r = 0; r < size; ++r) {
        long long i = first[r];
        while (i != -1) {
            long long x = arr[i];
            long long q = x / size;
            if (First[q] == -1) {
                First[q] = i;
            } else {
                Next[Last[q]] = i;
            }
            Last[q] = i;
            i = next[i];
        }
    }

    // Output
    std::vector<long long> output(size);
    int curr_idx = 0;
    for (long long q = 0; q < size; ++q) {
        long long i = First[q];
        while (i != -1) {
            output[curr_idx++] = arr[i];
            i = Next[i];
        }
    }

    delete[] first;
    delete[] last;
    delete[] next;
    delete[] First;
    delete[] Last;
    delete[] Next;

    return output;
}