Untitled

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

using namespace std;

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

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

inline int Hash(std::string& word, std::vector<uint64_t>& foundations, uint64_t mod) {
	uint64_t hash = 0;
	int counter = 0;
	for (int i = word.size() - 1; i >= 0; --i) {
		hash += foundations.at(counter++) * (uint64_t(word.at(i)) % mod) ;

	}
	return hash  % mod;
}

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


int main() {
	std::ios::sync_with_stdio(false);
	uint64_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<uint64_t> foundations_cache(GenFoundations(foundation, mod, word.size()));
	std::vector<uint64_t> str_hashes(CacheStringHashes(word, foundation, mod));
	// PrintDataMerged(str_haches);
//	std::cout << "'abcd - ab = cd' : " <<  uint64_t(225227) - foundations_cache.at(2) * uint64_t(97098) % mod << " exp. 99100" << std::endl;
//	std::cout << "'abcdefgh - abcdef = gh' : " <<  uint64_t(436420) - foundations_cache.at(2) * uint64_t(74077) % mod << " exp. 103104" << std::endl;
//	std::cout << "'abcdefgh - abcd = efgh' : "  <<  uint64_t(436420) - foundations_cache.at(4) * uint64_t(225227) % mod << " exp. 193195" << std::endl;
//	std::cout << "'ab - a = b' : " <<  uint64_t(97098) - foundations_cache.at(1) * uint64_t(97) % mod << " exp. 98" << std::endl;
//	std::cout << "'abcd - a = bcd' : " <<  uint64_t(225227) - foundations_cache.at(3) * uint64_t(97) % mod << " exp. 98218" << std::endl;
//	std::cout << std::endl;
//	std::cout << "'abc - a = bc' :" <<  uint64_t(97226) - foundations_cache.at(0) * uint64_t(98) % mod << " exp. 98099" << std::endl;
	while (counter) {
		uint64_t begin, end;
		std::cin >> begin >> end;
		std::cin.get();
		--counter;
		uint64_t end_hash = str_hashes.at(end - 1);

		if (begin > 1) {
			int diff = end - begin;
			if (!diff) {
				std::cout << int(word.at(begin - 1))  << std::endl;
			} else {
				uint64_t begin_hash =  str_hashes.at(begin - 2);
				std::cout <<  end_hash - foundations_cache.at(end-begin + 1) * begin_hash % mod << std::endl;			}
		} else {
			std::cout << end_hash  << std::endl;
		}
	}
	return 0;
}