Untitled

#include <iostream>
#include <string>
#include <vector>

using namespace std;

std::vector<uint64_t> GenAllHashes(std::string& word, uint64_t foundation, uint64_t mod) {
	std::vector<uint64_t> hash_vec;
	hash_vec.reserve(((word.size() + 1) * word.size()) / 2 );
	uint64_t hash = 0;
	uint64_t rand = 1;
	std::string str;
	size_t counter = 1;
	while (counter <= word.size()) {
		std::string str(word.substr(0, counter++));
		for (int i = str.size() - 1; i >= 0; --i) {
		hash += rand * (uint64_t(str.at(i)) % mod);
			rand = (rand * foundation) % mod;
			hash_vec.push_back(hash % mod);
		}
		hash = 0;
		rand = 1;
	}
	return hash_vec;
}

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);
	std::vector<uint64_t> hash_vec(GenAllHashes(word, foundation, mod));
	int counter;
	std::cin >> counter;
	std::cin.get();
	while (counter) {
		int begin, end;
		std::cin >> begin >> end;
		std::cin.get();
		int pos_counter = (((end - 1) * end) / 2); // вычисляю соответсвующее положения хэша конечной позиции
		pos_counter += std::abs(begin - end);  // поправка положение на соответсвуюю длину
		if (!hash_vec.empty() && pos_counter < hash_vec.size()) {
			std::cout <<  hash_vec.at(pos_counter) << std::endl;
		}
		--counter;
	}
	return 0;
}