#include <algorithm>
#include <bit>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <functional>
#include <locale>
#include <numeric>
#include <queue>
#include <string>
#include <utility>
#include <vector>

/**
 * Author: Cracker
 * Last update: 24.02.08
 */
namespace Default_Source {
#define UseStd(obj) using std::obj;
#define OPERATOR(T, U, OPT)                                       \
	friend constexpr T operator OPT(const T &lhs, const U &rhs) { \
		return T(lhs) OPT## = rhs;                                \
	}

namespace Type {
using i32 = int;
using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
// #ifdef _GLIBCXX_USE_INT128
using i128 = __int128;
using u128 = unsigned __int128;
// #endif
using f32 = float;
using f64 = double;
using f128 = long double;
template <typename T>
constexpr T Inf{std::numeric_limits<T>::max()};
template <typename T>
constexpr T HalfInf{std::numeric_limits<T>::max() / 2};
}  // namespace Type
using namespace Type;

namespace Utility {
using std::max;
using std::min;
using std::swap;
#ifndef likely
#define likely(x) __builtin_expect(!!(x), 1)
#endif
#ifndef unlikely
#define unlikely(x) __builtin_expect(!!(x), 0)
#endif
template <typename T>
constexpr void ckmin(T &lhs, const T &rhs) noexcept {
	lhs = lhs < rhs ? lhs : rhs;
}
template <typename T>
constexpr void ckmin(T &base, const std::initializer_list<T> &L) noexcept {
	for (const T &it : L) ckmin(base, it);
}
template <typename T>
constexpr void ckmax(T &lhs, const T &rhs) noexcept {
	lhs = lhs < rhs ? rhs : lhs;
}
template <typename T>
constexpr void ckmax(T &base, const std::initializer_list<T> &L) noexcept {
	for (const T &it : L) ckmax(base, it);
}
}  // namespace Utility
using namespace Utility;

namespace Traits {
template <typename _InputIterator>
using LegacyInputIterator = typename std::enable_if_t<std::is_convertible<
	typename std::iterator_traits<_InputIterator>::iterator_category,
	std::input_iterator_tag>::value>;
}

namespace Math {
UseStd(cos) UseStd(sin) UseStd(tan) UseStd(acos) UseStd(asin) UseStd(atan);
UseStd(abs) UseStd(ceil) UseStd(floor) UseStd(round);
template <typename T>
T ceil(T up, T down) {
	static_assert(std::is_arithmetic_v<T>);
	return (up + down - 1) / down;
}
template <typename T>
T floor(T up, T down) {
	static_assert(std::is_arithmetic_v<T>);
	return up / down;
}
template <typename T>
constexpr T Pi = acos<T>(-1);
}  // namespace Math

namespace IO {
namespace Buffer {
template <size_t BUFSIZE, typename ChatT = char>
class InBuffer {
#ifdef __unix__
#define fread fread_unlocked
#else
#endif
	FILE *fp;
	ChatT buf[BUFSIZE], *p, *ped;

   public:
	InBuffer(FILE *_fp = stdin) noexcept
		: fp{_fp}, buf{}, p{buf}, ped{buf + fread(buf, 1, BUFSIZE, fp)} {
		*ped = EOF;
	}
	ChatT getc() noexcept { return p == ped ? EOF : *p++; }
	ChatT pos() const noexcept { return *p; }
	void nxt() noexcept { p != ped && ++p; }
	bool ugetc(ChatT ch) noexcept { return p != buf && (*--p = ch, true); }
#undef fread
};
template <typename CharT>
class InBuffer<0, CharT> {
#ifdef __unix__
#define fgetc fgetc_unlocked
#else
#define fgetc _fgetc_nolock
#endif
	FILE *fp;

   public:
	InBuffer(FILE *_fp = stdin) noexcept : fp{_fp} {}
	CharT getc() const noexcept { return fgetc(fp); }
	CharT pos() const noexcept {
		CharT ch = fgetc(fp);
		return ungetc(ch, fp), ch;
	}
	void nxt() const noexcept { fgetc(fp); }
	bool ugetc(CharT ch) const noexcept { return ungetc(ch, fp); }
};
}  // namespace Buffer

static const std::locale Local{};
template <size_t BUFSIZE, typename CharT = char>
class InStream {
	Buffer::InBuffer<BUFSIZE, CharT> buf;

   public:
	InStream(FILE *_fp = stdin) noexcept : buf{_fp} {}
	template <typename _Rule>
	bool test(_Rule rule) const noexcept {
		return rule(buf.pos(), Local);
	}
	template <typename _Rule>
	void skip(_Rule rule) noexcept {
		while (rule(buf.pos(), Local)) buf.nxt();
	}
	CharT pos() noexcept { return buf.pos(); }
	void nxt() noexcept { buf.nxt(); }
	CharT getc() noexcept { return buf.getc(); }
	bool ugetc() noexcept { return buf.ugetc(); }
	bool eof() const noexcept { return buf.pos() == EOF; }
	operator bool() const noexcept { return buf.pos() != EOF; }

	template <typename T>
	std::enable_if_t<std::is_integral_v<T> && std::is_signed_v<T>, InStream &>
	operator>>(T &x) noexcept {
		x = 0, skip(std::isspace<CharT>);
		if (buf.pos() == '-')
			for (buf.nxt(); test(std::isdigit<CharT>);)
				x = x * 10 - (buf.getc() & 15);
		else
			for (; test(std::isdigit<CharT>);) x = x * 10 + (buf.getc() & 15);
		return *this;
	}
	template <typename T>
	std::enable_if_t<std::is_integral_v<T> && std::is_unsigned_v<T>, InStream &>
	operator>>(T &x) noexcept {
		x = 0, skip(std::isspace<CharT>);
		for (; test(std::isdigit<CharT>);) x = x * 10 + (buf.getc() & 15);
		return *this;
	}
	template <typename T>
	std::enable_if_t<std::is_floating_point_v<T>, InStream &> operator>>(
		T &x) noexcept {
		static T f;
		x = 0, skip(std::isspace<CharT>);
		if (buf.pos() == '-') {
			for (buf.nxt(); test(std::isdigit<CharT>);)
				x = x * 10 - (buf.getc() & 15);
			if (buf.pos() == '.')
				for (f = 0.1, buf.nxt(); test(std::isdigit<CharT>); f *= 0.1)
					x -= f * (buf.getc() & 15);
		} else {
			for (; test(std::isdigit<CharT>);) x = x * 10 + (buf.getc() & 15);
			if (buf.pos() == '.')
				for (f = 0.1, buf.nxt(); test(std::isdigit<CharT>); f *= 0.1)
					x += f * (buf.getc() & 15);
		}
		return *this;
	}
	InStream &operator>>(bool &boolen) noexcept {
		return skip(std::isspace<CharT>), boolen = buf.getc() == '1', *this;
	}
	InStream &operator>>(char &ch) noexcept {
		return skip(std::isspace<CharT>), ch = buf.getc(), *this;
	}
	InStream &operator>>(char *str) noexcept {
		for (skip(std::isspace<CharT>); test(std::isgraph<CharT>);)
			*str++ = buf.getc();
		return *str = '\0', *this;
	}
	InStream &operator>>(std::string &str) noexcept {
		str = "";
		for (skip(std::isspace<CharT>); test(std::isgraph<CharT>);)
			str += buf.getc();
		return *this;
	}

	InStream &operator>>(
		std::tuple<char *&, std::function<bool(char, std::locale)>>
			strtp) noexcept {
		auto &[str, rule] = strtp;
		for (skip(std::isspace<CharT>); test(rule);) *str++ = buf.getc();
		return *str = '\0', *this;
	}
	InStream &operator>>(
		std::tuple<std::string &, std::function<bool(char, std::locale)>>
			strtp) noexcept {
		auto &[str, rule] = strtp;
		str = "";
		for (skip(std::isspace<CharT>); test(rule);) str += buf.getc();
		return *this;
	}

	template <typename T1, typename T2>
	InStream &operator>>(std::pair<T1, T2> &ptt) noexcept {
		return *this >> ptt.first >> ptt.second;
	}
	template <typename... Args>
	InStream &operator>>(std::tuple<Args...> &tp) noexcept {
		return tp = reads<Args...>(), *this;
	}
	template <typename... Args>
	InStream &read(Args &...args) noexcept {
		return void(std::initializer_list<InStream>{*this >> args...}), *this;
	}
	template <typename T>
	T read() noexcept {
		static_assert(!std::is_pointer_v<T>);
		static T tmp;
		return read(tmp), tmp;
	}
	template <typename T>
	std::tuple<T> reads() noexcept {
		return std::make_tuple(read<T>());
	}
	template <typename T, typename... Args>
	typename std::enable_if<sizeof...(Args) != 0, std::tuple<T, Args...>>::type
	reads() noexcept {
		static T tmp;
		return read(tmp), std::tuple_cat(std::tuple<T>{tmp}, reads<Args...>());
	}
};
}  // namespace IO

namespace Arithmetic {
using std::complex;
template <typename T>
static constexpr T mul(T x, T y, T p) noexcept {
	if constexpr (sizeof(T) < sizeof(u64))
		return 1ll * x * y % p;
	else if constexpr (sizeof(T) < sizeof(u128))
		return i128(x) * y % p;
	else
		return x * y % p;
}
template <typename T, typename U>
static constexpr T qpow(T x, U pw) noexcept {
	T ret{1};
	for (; pw; pw >>= 1, x *= x)
		if (pw & 1) ret *= x;
	return ret;
}
template <typename T, T P>
class ModNum {
	static_assert(P >= 0);

   public:
	using un_type = std::make_unsigned_t<T>;
	using exp_type = ModNum<T, P - 1>;

   private:
	static_assert(std::is_integral_v<T>);
	un_type v;
	static un_type Mod;
	constexpr static un_type unorm(un_type x) noexcept {
		return x >= mod() ? x - mod() : x;
	}
	template <typename U>
	constexpr static un_type norm(U x) noexcept {
		return unorm(x < 0 ? x + mod() : x);
	}

   public:
	constexpr ModNum() noexcept : v{} {}
	template <typename U, typename = std::enable_if_t<std::is_integral_v<U>>>
	constexpr ModNum(const U &x) noexcept : v{norm(x % T(mod()))} {}
	constexpr ModNum(const ModNum &ot) noexcept = default;
	constexpr ModNum(ModNum &&ot) noexcept = default;
	constexpr ModNum &operator=(const ModNum &ot) noexcept {
		return v = ot.v, *this;
	}
	constexpr ModNum &operator=(ModNum &&ot) noexcept {
		return v = ot.v, *this;
	}
	constexpr explicit operator T() const noexcept { return v; }
	constexpr T val() const noexcept { return v; }
	constexpr static un_type mod() noexcept {
		if constexpr (P > 0)
			return P;
		else
			return Mod;
	}
	constexpr static void set(T _Mod) noexcept { Mod = _Mod; }
	constexpr ModNum &operator++() noexcept { return v = norm(++v), *this; }
	constexpr const ModNum operator++(i32) noexcept {
		un_type tmp = v;
		v = norm(++v);
		return ModNum(tmp);
	}
	constexpr ModNum operator-() const noexcept { return ModNum(-T(v)); }
	constexpr ModNum inv() const noexcept { return qpow(*this, mod() - 2); }
	constexpr ModNum &operator+=(ModNum ot) noexcept {
		return v = unorm(v + ot.v), *this;
	}
	constexpr ModNum &operator-=(ModNum ot) noexcept {
		return v = unorm(v + mod() - ot.v), *this;
	}
	constexpr ModNum &operator*=(ModNum ot) noexcept {
		return v = mul(v, ot.v, mod()), *this;
	}
	constexpr ModNum &operator/=(ModNum ot) noexcept {
		return *this *= ot.inv();
	}
	OPERATOR(ModNum, ModNum, +);
	OPERATOR(ModNum, ModNum, -);
	OPERATOR(ModNum, ModNum, *);
	OPERATOR(ModNum, ModNum, /);
	constexpr bool friend operator==(ModNum lhs, ModNum rhs) noexcept {
		return lhs.val() == rhs.val();
	}
	constexpr bool friend operator!=(ModNum lhs, ModNum rhs) noexcept {
		return lhs.val() != rhs.val();
	}
	template <typename U>
	constexpr ModNum pow(U pw) const noexcept {
		return qpow(*this, pw);
	}
	template <size_t BUFSIZE, typename CharT>
	constexpr friend IO::InStream<BUFSIZE, CharT> &operator>>(
		IO::InStream<BUFSIZE, CharT> &is, ModNum &x) noexcept {
		is.skip(std::isspace<CharT>);
		if (is.pos() == '-')
			for (is.nxt(); is.test(std::isdigit<CharT>);)
				x = x * 10 - (is.getc() & 15);
		else
			for (; is.test(std::isdigit<CharT>);) x = x * 10 + (is.getc() & 15);
		return is;
	}
};
template <typename T, T P>
ModNum<T, P>::un_type ModNum<T, P>::Mod;

template <i32 P>
using Z32 = ModNum<i32, P>;
template <i64 P>
using Z64 = ModNum<i64, P>;

/**
 * I don't know how it works.
 */
template <typename T>
constexpr T findPrimitiveRoot() {
	T i = 2;
	i32 k = std::countr_zero<typename std::make_unsigned_t<decltype(T::mod())>>(
		T::mod() - 1);
	for (;; ++i)
		if (qpow(i, (T::mod() - 1) / 2) != 1) break;
	return qpow(i, (T::mod() - 1) >> k);
}
template <typename T>
constexpr T primitiveRoot = findPrimitiveRoot<T>();
template <typename T>
constexpr T InvprimitiveRoot = qpow(primitiveRoot<T>, T::mod() - 2);

template <typename T>
std::vector<T> fac{1};
template <typename T>
std::vector<T> ifac{1};
template <typename T>
std::vector<T> iv{0};
template <typename T>
constexpr void pre_fac(u32 m) noexcept {
	if (fac<T>.size() < m) {
		u32 k = fac<T>.size();
		fac<T>.resize(m);
		for (; k < m; ++k) fac<T>[k] = fac<T>[k - 1] * k;
	}
}
template <typename T>
void pre_ifac(u32 m) noexcept {
	if (ifac<T>.size() < m) {
		u32 k = ifac<T>.size();
		pre_fac<T>(m), ifac<T>.resize(m);
		ifac<T>.back() = qpow(fac<T>.back(), T::mod() - 2);
		for (--m; m > k; --m) ifac<T>[m - 1] = ifac<T>[m] * m;
	}
}
template <typename T>
constexpr void pre_iv(u32 m) noexcept {
	if (iv<T>.size() < m) {
		u32 k = iv<T>.size();
		pre_ifac<T>(m), iv<T>.resize(m);
		for (; k < m; ++k) iv<T>[k] = ifac<T>[k] * fac<T>[k - 1];
	}
}
template <typename T>
constexpr T binom(u32 n, u32 m) noexcept {
	return fac<T>[n] * ifac<T>[m] * ifac<T>[n - m];
}
}  // namespace Arithmetic

namespace Poly {
enum Trans_mode { DIF = 0, DIT = 1 };
constexpr u32 toLim(u32 len) { return 1u << (32 - std::countl_zero(len)); }
using std::vector;

template <typename T>
class NTT {
	static vector<T> roots;
	static constexpr void InitRoot(u32 k) noexcept {
		u32 l = roots.size();
		roots.resize(k);
		for (u32 l2 = l << 1; l < k; l = l2, l2 <<= 1) {
			T p = Arithmetic::qpow(Arithmetic::primitiveRoot<T>,
								   (T::mod() - 1) / l2);
			for (u32 i = l; i < l2; ++ ++i)
				roots[i + 1] = (roots[i] = roots[i / 2]) * p;
		}
	}

   public:
	template <Trans_mode mode, typename Iterator>
	static constexpr void trans(Iterator p, u32 n) noexcept {
		InitRoot(n);
		if constexpr (mode == DIF)
			for (u32 l = n >> 1; l; l >>= 1)
				for (u32 t = 0; t < n; t += (l << 1))
					for (u32 k = 0; k < l; ++k) {
						T x = p[t + k], y = p[t + l + k];
						p[t + k] = x + y, p[t + l + k] = roots[k + l] * (x - y);
					}
		else {
			for (u32 l = 1; l < n; l <<= 1)
				for (u32 t = 0; t < n; t += (l << 1))
					for (u32 k = 0; k < l; ++k) {
						T x = p[t + k], y = roots[k + l] * p[t + l + k];
						p[t + k] = x + y, p[t + l + k] = x - y;
					}
			const T ivn = T(1) / n;
			for (u32 k = 0; k < n; ++k) p[k] *= ivn;
			std::reverse(p + 1, p + n);
		}
	}
};
template <typename T>
vector<T> NTT<T>::roots{1, 1};

template <typename Iterator>
constexpr void dot(Iterator f, Iterator g, u32 deg) {
	for (u32 k = 0; k < deg; ++k) f[k] *= g[k];
}
enum PolyMode { Coefficients = 0, PipValue = 1 };
template <typename T, typename _Trans = NTT<T>>
class poly : public vector<T> {
	static _Trans trans;
	PolyMode mode = PolyMode::Coefficients;

#define f (*this)
	static poly &times(poly &p, poly &q, u32 n) noexcept {
		return p.Dft(n), q.Dft(n), dot(p.begin(), q.begin(), n), p.Idft(n);
	}

   public:
	using vector<T>::vector;
	constexpr poly(u32 n, std::function<T(u32)> func) noexcept {
		redeg(n);
		for (u32 k = 0; k < n; ++k) f[k] = func(k);
	}
	constexpr void fill(std::function<T(u32)> func = [](u32 k) -> T {
		return {};
	}) noexcept {
		for (u32 k = 0; k < deg(); ++k) f[k] = func(k);
	}
	constexpr void fill(
		u32 n,
		std::function<T(u32)> func = [](u32 k) -> T { return {}; }) noexcept {
		redeg(n);
		for (u32 k = 0; k < deg(); ++k) f[k] = func(k);
	}
	constexpr u32 deg() const noexcept { return vector<T>::size(); }
	constexpr poly &redeg(u32 n) noexcept {
		return vector<T>::resize(n), *this;
	}
	constexpr poly slice(u32 length, u32 first = 0) const noexcept {
		return {vector<T>::begin() + first,
				vector<T>::begin() + Utility::min(deg(), first + length)};
	}
	constexpr poly &Dft(u32 n) noexcept {
		if (mode != PipValue)
			mode = PipValue, redeg(n),
			trans.template trans<DIF>(vector<T>::begin(), n);
		return *this;
	}
	constexpr poly &Idft(u32 n) noexcept {
		return mode = Coefficients,
			   trans.template trans<DIT>(vector<T>::begin(), n), *this;
	}
	constexpr poly operator-() const noexcept {
		poly ret = *this;
		for (T &it : ret) it = -it;
		return ret;
	}
	constexpr poly &operator+=(const poly &ot) noexcept {
		redeg(Utility::max(deg(), ot.deg()));
		for (u32 k = 0; k < ot.deg(); ++k) f[k] += ot[k];
		return *this;
	}
	constexpr poly &operator-=(const poly &ot) noexcept {
		redeg(Utility::max(deg(), ot.deg()));
		for (u32 k = 0; k < ot.deg(); ++k) f[k] -= ot[k];
		return *this;
	}
	constexpr poly &operator*=(const T &value) noexcept {
		for (T &it : *this) it *= value;
		return *this;
	}
	constexpr poly &operator*=(poly ot) noexcept {
		u32 degree = deg() + ot.deg() - 1;
		return times(*this, ot, toLim(degree)).redeg(degree);
	}
	OPERATOR(poly, poly, +);
	OPERATOR(poly, poly, -);
	OPERATOR(poly, poly, *);
	OPERATOR(poly, T, *);
	constexpr poly Dvt(u32 degree) const noexcept {
		poly ret(degree);
		for (u32 k = 1; k < Utility::min(deg(), degree + 1); ++k)
			ret[k - 1] = k * f[k];
		return ret;
	}
	constexpr poly Igt(u32 degree) const noexcept {
		poly ret(degree);
		Arithmetic::pre_iv<T>(degree);
		for (u32 k = Utility::min(deg(), degree - 1); k > 0; --k)
			ret[k] = Arithmetic::iv<T>[k] * f[k - 1];
		return ret;
	}
	template <typename U>
	constexpr poly &operator>>=(U t) noexcept {
		if (t >= deg()) return *this = {};
		for (u32 k = t; k < deg(); ++k) f[k - t] = f[k];
		return redeg(deg() - t);
	}
	template <typename U>
	constexpr poly &operator<<=(U t) noexcept {
		redeg(deg() + t);
		for (u32 k = t; k < deg(); ++k) f[k] = f[k - t];
		for (u32 k = 0; k < t; ++k) f[k] = 0;
		return redeg(deg() - t);
	}
	template <typename U>
	constexpr friend poly operator>>(poly lhs, U t) noexcept {
		return lhs >>= t;
	}
	template <typename U>
	constexpr friend poly operator<<(poly lhs, U t) noexcept {
		return lhs <<= t;
	}
	constexpr poly Rev() const noexcept {
		return poly{vector<T>::rbegin(), vector<T>::rend()};
	}
	constexpr poly &shrink() {
		if (!vector<T>::empty())
			for (u32 k = deg() - 1; k; --k)
				if (f[k] != 0) return redeg(k + 1);
		return *this;
	}

   private:
	constexpr poly &ClearL(u32 degree) noexcept {
		return std::fill_n(vector<T>::begin(), degree >> 1, 0), *this;
	}
	constexpr poly &ClearH(u32 degree) noexcept {
		return std::fill_n(vector<T>::begin() + (degree >> 1), degree >> 1, 0),
			   *this;
	}
	constexpr poly &InvHelp(poly p, poly q, u32 degree) noexcept {
		times(p, q, degree).ClearL(degree);
		times(p, q, degree), redeg(degree);
		for (u32 k = degree >> 1; k < degree; ++k) f[k] = -p[k];
		return *this;
	}

   public:
	constexpr poly Inv(u32 degeree) const noexcept {
		poly ret{1 / f.front()};
		for (u32 l = 2; l < degeree * 2; l *= 2)
			ret.InvHelp(slice(l), ret.slice(degeree), l);
		return ret.redeg(degeree);
	}
	constexpr poly Div(poly g, u32 degree) const noexcept {
		if (deg() == 0) return {};
		u32 t = toLim(degree);
		poly f0 = slice(t >> 1), g0 = g.Inv(t >> 1);
		poly q = times(f0, g0, t).slice(t >> 1);
		times(q, g, t).ClearL(t);
		for (u32 k = t >> 1; k < Utility::min(t, deg()); ++k) q[k] -= f[k];
		times(q, g0, t), f0.redeg(degree);
		for (u32 k = t >> 1; k < Utility::min(t, degree); ++k) f0[k] = -q[k];
		return f0;
	}
	constexpr poly Sqrt(u32 degree) const noexcept {
		poly ret{1};
		for (u32 l1 = 2, l2 = 4; l1 < degree * 2; l1 = l2, l2 <<= 1)
			(ret = (ret + slice(l1).Div(ret, l1)) * (T(2).inv())).redeg(l1);
		return ret.redeg(degree);
	}
	constexpr poly Ln(u32 degree) const noexcept {
		return Dvt(degree).Div(slice(degree), degree).Igt(degree);
	}
	constexpr poly Exp(u32 degree) const noexcept {
		poly ret{1};
		for (u32 l1 = 2, l2 = 4; l1 < degree * 2; l1 = l2, l2 <<= 1)
			ret *= poly{1} - ret.Ln(l1) + slice(l1);
		return ret.redeg(degree);
	}
	constexpr poly Pow(u32 degree, T pw) const noexcept {
		return (Ln(degree) * pw).Exp(degree);
	}
	friend constexpr poly operator/(poly p, const poly &q) noexcept {
		if (p.deg() < q.deg()) p.redeg(q.deg());
		return p.Rev().Div(q.Rev(), p.deg() - q.deg() + 1).Rev();
	}
	friend constexpr poly operator%(const poly &p, const poly &q) noexcept {
		poly g = p / q, h = p - g * q;
		return h.shrink();
	}
	constexpr std::pair<poly, poly> Divt(const poly &g) const noexcept {
		poly p = f / g, q = f - g * p;
		return {p, q.shrink()};
	}
	constexpr poly ChirpZ(T c, u32 m) const noexcept {
		poly p(deg(), [&](u32 k) { return f[k] / c.pow(k * (k - 1ll) >> 1); }),
			q(deg() + m - 1, [&](u32 k) { return c.pow(k * (k - 1ll) >> 1); });
		std::reverse(p.begin(), p.end()), p *= q;
		for (u32 k = 0; k < m; ++k)
			p[k] = p[k + deg() - 1] / c.pow((k * (k - 1ll)) >> 1);
		return p.redeg(m);
	}
#undef f
};
template <typename T, typename _Trans>
_Trans poly<T, _Trans>::trans;

enum FWT_type { Or = 0, And = 1, Xor = 2 };
template <FWT_type type>
struct FWT {};
template <>
struct FWT<Or> {
	template <Trans_mode mode, typename Iterator>
	constexpr void trans(Iterator f, u32 n) const noexcept {
		for (u32 k = 1; k < n; k <<= 1)
			for (u32 i = 0; i < n; ++i)
				if (i & k) {
					if constexpr (mode == DIF)
						f[i] += f[i ^ k];
					else
						f[i] -= f[i ^ k];
				}
	}
};
template <>
struct FWT<And> {
	template <Trans_mode mode, typename Iterator>
	constexpr void trans(Iterator f, u32 n) const noexcept {
		for (u32 k = 1; k < n; k <<= 1)
			for (u32 i = 0; i < n; ++i)
				if (i & k) {
					if constexpr (mode == DIF)
						f[i ^ k] += f[i];
					else
						f[i ^ k] -= f[i];
				}
	}
};
template <>
struct FWT<Xor> {
	template <typename T>
	static constexpr T Inv2 = T(1) / 2;
	template <Trans_mode mode, typename Iterator>
	static constexpr void trans(Iterator f, u32 n) noexcept {
		auto inv2 = Inv2<std::remove_reference_t<decltype(f[0])>>;
		for (u32 p = 1, l = 2; p < n; p = l, l <<= 1)
			for (u32 t = 0; t < n; t += l)
				for (u32 k = 0; k < p; ++k) {
					auto x = f[t | k], y = f[t | p | k];
					if constexpr (mode == DIF)
						f[t | k] += y, f[t | p | k] = x - y;
					else
						(f[t | k] += y) *= inv2, f[t | p | k] = (x - y) * inv2;
				}
	}
};
template <typename Trans, typename Iterator>
constexpr void times(Iterator f, Iterator g, u32 deg, Trans trans = Trans{}) {
	trans.template trans<DIF>(f, deg);
	trans.template trans<DIF>(g, deg);
	dot(f, g, deg);
	trans.template trans<DIT>(f, deg);
	return f;
}

}  // namespace Poly

#undef UseStd
#undef OPERATOR
}  // namespace Default_Source
using namespace Default_Source;

constexpr i64 N = 1e15;
IO::InStream<0> qin;
using Arithmetic::Z64;
Z64<0> f[14], g[14];
struct pair {
	i64 x;
	Z64<0> val;
	pair() = default;
	pair(i64 _x, Z64<0> _val) : x{_x}, val{_val} {}
	bool operator<(const pair &ot) const noexcept { return x < ot.x; }
};
std::vector<i64> pre;
std::vector<pair> pref, preg;
Z64<0> calc(i64 n, const std::vector<pair> &pre_func) {
	return (--std::upper_bound(pre_func.begin(), pre_func.end(), pair(n, {})))
		->val;
}
Z64<0> get(i64 n, i32 t, const std::vector<pair> &pre_func) {
	return n % t ? Z64<0>(0) : calc(n / t, pre_func);
}

signed main() {
	auto [f0, g0, T, mod] = qin.reads<i32, i32, i32, i64>();
	Z64<0>::set(mod), f[0] = f0, g[0] = g0;
	for (i32 n = 1; n <= 13; ++n)
		f[n] = max<i64>(Z64<0>(n).val(),
						(g[n / 2] + g[n / 3] + g[n / 5] + g[n / 7]).val()),
		g[n] = max<i64>(Z64<0>(n).val(),
						(f[n / 2] + f[n / 3] + f[n / 4] + f[n / 5]).val());
	pre.reserve(84078), pre.emplace_back(0);
	for (i32 n : {1, 2, 3, 5, 7, 9, 11, 13})
		for (i64 _2 = 1, __2 = N / n; _2 <= __2; _2 <<= 1)
			for (i64 _3 = 1, __3 = N / (n * _2); _3 <= __3; _3 *= 3)
				for (i64 _5 = 1, __5 = N / (n * _2 * _3); _5 <= __5; _5 *= 5)
					for (i64 _7 = 1, __7 = N / (n * _2 * _3 * _5); _7 <= __7;
						 _7 *= 7)
						pre.emplace_back(n * _2 * _3 * _5 * _7);
	std::sort(pre.begin(), pre.end()),
		pre.erase(std::unique(pre.begin(), pre.end()), pre.end());
	for (i32 n = 13; n >= 1; --n) f[n] -= f[n - 1], g[n] -= g[n - 1];
	pref.reserve(pre.size() + 1), preg.reserve(pre.size() + 1);
	for (auto n : pre)
		if (n <= 13)
			pref.emplace_back(n, f[n]), preg.emplace_back(n, g[n]);
		else {
			Z64<0> posf = get(n, 2, preg) + get(n, 3, preg) + get(n, 5, preg) +
						  get(n, 7, preg),
				   posg = get(n, 2, pref) + get(n, 3, pref) + get(n, 4, pref) +
						  get(n, 5, pref);
			pref.emplace_back(n, posf), preg.emplace_back(n, posg);
		}
	for (u32 t = 1; t < pre.size(); ++t)
		pref[t].val += pref[t - 1].val, preg[t].val += preg[t - 1].val;
	for (i64 n; T; --T)
		qin.read(n),
			printf("%lld %lld\n", calc(n, pref).val(), calc(n, preg).val());

	return 0;
}