Caps

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

int bits(int64_t N) {
    int have = 0;
    while (N > 0) {
        ++have;
        N -= (N & -N);
    }
    return have;
}

int map(char c) {
    if (c >= 'A' && c <= 'Z')
        return c - 'A';
    return c - 'a' + 26;
}

char rev(char c) {
    return c ^ 'A' ^ 'a';
}

int main () {
    ifstream cin("caps.in");
    ofstream cout("caps.out");

    int K, Q; assert(cin >> K >> Q);
    assert(1 <= K && K <= 100 * 1000);
    assert(1 <= Q && Q <= 50 * 1000);

    string S; cin >> S;
    assert(int(S.size()) == K);
    for (auto &c : S)
        assert((c >= 'a' && c <= 'z') || (c >= 'A' || c <= 'Z'));

    int total_count[52];
    fill(total_count, total_count + 52, 0);
    for (auto &c : S)
        total_count[map(c)]++;

    vector<int> positions[52];
    for (int i = 0; i < int(S.size()); ++i)
        positions[map(S[i])].push_back(i);

    for (int i = 0; i < Q; ++i) {
        int64_t N; assert(cin >> N);
        assert(1 <= N && N <= 1000LL * 1000 * 1000 * 1000 * 1000 * 1000);
        --N;

        int64_t part = N / K;
        int index = N % K;
        char answer;
        if (bits(part) % 2)
            answer = rev(S[index]);
        else
            answer = S[index];

        int64_t many = 0;
        int64_t normal = part / 2, reversed = part / 2;
        if (part % 2) {
            if (bits(part - 1) % 2)
                ++reversed;
            else
                ++normal;
        }
        many += normal * total_count[map(answer)];
        many += reversed * total_count[map(rev(answer))];
        char search_for = S[index];
        many += upper_bound(positions[map(search_for)].begin(), positions[map(search_for)].end(), index) - positions[map(search_for)].begin();
        cout << answer << " " << many << "\n";
    }
}