#include "validate.h"

std::pair<bool, std::string> isSubsequence(std::string_view x, std::string_view of) {
	std::size_t i = 0;
	std::string remain;
	for (std::size_t j = 0; j < of.size(); j++) {
		if (i < x.size() && x[i] == of[j]) i++;
		else remain.push_back(of[j]);
	}
	std::sort(remain.begin(), remain.end());
	return {i == x.size(), remain};
}

int main(int argc, char **argv) {
	OutputValidator::init(argc, argv);
	using namespace OutputValidator;

	if (stringEqual(juryAns.string(), "impossible")) {
		teamAns.expectString("impossible");
		teamAns.newline();
		teamAns.eof();
		juryOut << "OK impossible" << AC;
	} else {
		teamAns.expectString("possible");
		teamAns.newline();
		std::string a = testIn.string();
		std::string b = testIn.string();
		Integer c = testIn.integer();
		Integer d = testIn.integer();

		std::string a2 = teamAns.string(INTEGER_REGEX);
		teamAns.space();
		std::string b2 = teamAns.string(INTEGER_REGEX);
		teamAns.newline();

		auto [ba, ra] = isSubsequence(a2, a);
		auto [bb, rb] = isSubsequence(b2, b);

		if (!ba) juryOut << "a' not generated by cancelling digits!" << WA;
		if (!bb) juryOut << "b' not generated by cancelling digits!" << WA;
		if (ra != rb) juryOut << ra << " != " << rb << ": cancelled digits are not the same" << WA;

		Integer a3 = std::stoll(a2);
		Integer b3 = std::stoll(b2);
		if (a3 == 0 || b3 == 0 ||
			mulMod(c, b3, 1'000'000'007) != mulMod(a3, d, 1'000'000'007) || //product of mods is larger than 10^18*10^18
			mulMod(c, b3, 1'000'000'009) != mulMod(a3, d, 1'000'000'009) ||
			mulMod(c, b3, 1'000'000'021) != mulMod(a3, d, 1'000'000'021) ||
			mulMod(c, b3, 1'000'000'033) != mulMod(a3, d, 1'000'000'033)) {
			juryOut << a << "/" << b << " != " << c << "/" << d << WA;
		}

		teamAns.eof();
		juryOut << "OK possible" << AC;
	}
}