11.cpp

/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author RiaD
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <unordered_map>
#include <vector>
#include <assert.h>

using namespace std;

class Task11 {
public:
	static int64_t binpow(int64_t x, int64_t p, int64_t m) {
		int64_t r = 1;
		while (p) {
			if (p & 1) r = (r * x) % m;
			x = (x * x) % m;
			p >>= 1;
		}
		return r;
	}


	struct ReminderStorage {
		std::unordered_map<int, int> counts;
		int multiplier;
		int addition;
		int P;
		int ten_reversed;

		ReminderStorage(int P) : multiplier(1), addition(0), P(P) {
			counts.reserve(1 << 20);
			ten_reversed = binpow(10, P - 2, P);
		}

		void insert(int x) {
			x -= addition;
			if (x < 0)
				x += P;
			x = int64_t(x) * multiplier % P;
			//std::cerr << "insert: " << addition << " " << multiplier << " " << x << std::endl;
			counts[x]++;
		}

		void multiply() {
			multiplier = int64_t(multiplier) * ten_reversed % P;
			addition = int64_t(addition) * 10 % P;
		}

		void add(int x) {
			addition += x;
			if (addition >= P)
				addition -= P;
		}

		int ways(int x) const {
			x -= addition;
			if (x < 0)
				x += P;
			x = int64_t(x) * multiplier % P;
			auto it = counts.find(x);
			return (it == counts.end() ? 0 : it->second);
		}
	};

	void solve(std::istream& in, std::ostream& out) {
		std::string digits;
		in >> digits;
		int n, p;
		in >> n >> p;
		std::vector<int> queries(n);
		std::vector<int64_t> ways(n);
		std::vector<int> l(n, -1), r(n, -1);
		for (int i = 0; i < n; i++) {
			in >> queries[i];
		}
		ReminderStorage rs(p);
		for (int j = 0; j < digits.size(); j++) {
			char digit = digits[j];
			rs.multiply();
			rs.insert(0);
			rs.add(digit - '0');
			for (int i = 0; i < n; i++) {
				int add = rs.ways(queries[i]);
				if (add > 0) {
					ways[i] += add;
					r[i] = j;
				}
			}
		}
		for (int i = 0; i < n; i++) {
			if (r[i] != -1) {
				int64_t x = 0, m = 1;
				for (int j = r[i]; j >= 0; j--) {
					x = (x + m * (digits[j] - '0')) % p;
					m = (m * 10) % p;
					if (x == queries[i]) {
						l[i] = j;
					}
				}
				assert(l[i] != -1);
			}

			out << ways[i] << " " << (l[i] + 1) << " " << (r[i] + 1) << "\n";
		}
	}
};


int main() {
	std::ios_base::sync_with_stdio(false);
	Task11 solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	in.tie(0);
	out << std::fixed;
	out.precision(20);
	solver.solve(in, out);
	return 0;
}