Untitled

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

void PrintDataMerged(std::vector<int64_t>& data) {
	for (int n : data) {
		std::cout << n << " ";
	}
	std::cout << std::endl;
}

std::vector<int64_t> GenFoundations(int64_t foundation, int64_t mod, size_t size) {
	std::vector<int64_t> foundations;
	foundations.reserve(size);
	int64_t rand = 1  % mod ;
		while (size--) {
			foundations.push_back(rand  % mod );
		rand = (rand % mod * foundation % mod) ;
	}
	return foundations;
}

inline int Hash(std::string word, int64_t foundations, int64_t mod) {
	int64_t hash = 0 % mod;
	for (char c : word) {
		hash = (hash % mod * foundations % mod + int64_t(c) % mod) ;
	}
	return hash % mod;
}

std::vector<int64_t> CacheStringHashes(std::string& word, int64_t foundations, int64_t mod) {
	std::vector<int64_t> result;
	result.reserve(word.size());
	int64_t hash = 0;
	for(char c : word) {
		hash = (hash % mod * foundations % mod + int64_t(c) % mod) ;
		result.push_back(hash % mod);
	}
	return result;
}

int main() {
	std::ios::sync_with_stdio(false);
	int64_t foundation, mod;
	std::cin >> foundation;
	std::cin.get();
	std::cin >> mod;
	std::cin.get();
	std::string word;
	std::getline(std::cin, word);
	int counter;
	std::cin >> counter;
	std::cin.get();
	std::vector<int64_t> foundations_cache(GenFoundations(foundation, mod, word.size()));
	std::vector<int64_t> str_hashes(CacheStringHashes(word, foundation, mod));
/*	PrintDataMerged(foundations_cache);
	PrintDataMerged(str_hashes);
	std::cout << "abc and a hashes : " << Hash("abc", foundation, mod) << " - " << Hash("a", foundation, mod) << std::endl;
	std::cout << "'abc - a = bc' :" <<  (Hash("abc", foundation, mod) - (foundations_cache.at(1))  * Hash("a", foundation, mod)) % mod<< " exp. 98099" << std::endl;*/
	while (counter) {
		int64_t begin, end;
		std::cin >> begin >> end;
		std::cin.get();
		--counter;
		int64_t end_hash = 0;
		if (end != 0) {
			end_hash = str_hashes.at(end - 1) % mod;
		}
		if (begin > 1) {
			int diff = end - begin;
			if (!diff) {
				std::cout << int(word.at(begin - 1))  << std::endl;
			} else {
				int64_t begin_hash =  str_hashes.at(begin - 2) % mod ;
				std::cout <<  end_hash - foundations_cache.at(end-begin + 1) * begin_hash % mod << std::endl;}
		} else {

			std::cout << end_hash  << std::endl;
		}
	}
	return 0;
}