#pragma GCC optimize("O2")
#define _USE_MATH_DEFINES
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
/*
#include <atcoder/all>
using namespace atcoder;
*/
/*
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
using bll = boost::multiprecision::cpp_int;
using bdouble = boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>;
using namespace boost::multiprecision;
*/
//#define int long long
using ll = long long;
//constexpr ll MOD = (ll)1e9 + 7; //primitive root = 5
constexpr ll MOD = 998244353; //primitive root = 3
//INT_MAX = (1<<31)-1 = 2147483647, INT64_MAX = (1LL<<63)-1 = 9223372036854775807
constexpr ll INF = std::numeric_limits<ll>::max() == INT_MAX ? (ll)1e9 + 7 : (ll)1e18 + 1;
constexpr double EPS = 1e-9;
constexpr ll dx[4] = {1, 0, -1, 0};
constexpr ll dy[4] = {0, 1, 0, -1};
constexpr ll dx8[8] = {1, 1, 0, -1, -1, -1, 0, 1};
constexpr ll dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
#if !defined(LOCAL_DEV) && 0
	#define USE_FASTIO
#endif
namespace std {
struct IOPre {
	static constexpr int TEN = 10, SZ = TEN * TEN * TEN * TEN;
	std::array<char, 4 * SZ> num;
	constexpr IOPre() : num{} {
		for (int i = 0; i < SZ; i++) { int n = i; for (int j = 3; j >= 0; j--) { num[i * 4 + j] = static_cast<char>(n % TEN + '0'); n /= TEN; } }
	}
};
struct IO {
#if !HAVE_DECL_FREAD_UNLOCKED
	#define fread_unlocked fread
#endif
#if !HAVE_DECL_FWRITE_UNLOCKED
	#define fwrite_unlocked fwrite
#endif
	static constexpr int SZ = 1 << 17, LEN = 32, TEN = 10, HUNDRED = TEN * TEN, THOUSAND = HUNDRED * TEN, TENTHOUSAND = THOUSAND * TEN, MAGIC_MULTIPLY = 205, MAGIC_SHIFT = 11, MASK = 15, TWELVE = 12, SIXTEEN = 16;
	static constexpr IOPre io_pre = {};
	std::array<char, SZ> input_buffer, output_buffer;
	int input_ptr_left, input_ptr_right, output_ptr_right, precision_value;
	IO() : input_buffer{}, output_buffer{}, input_ptr_left{}, input_ptr_right{}, output_ptr_right{}, precision_value{20} {}
	IO(const IO&) = delete;
	IO(IO&&) = delete;
	IO& operator=(const IO&) = delete;
	IO& operator=(IO&&) = delete;
	~IO() { flush(); }
	template <class> struct is_bounded_char_array : std::false_type {};
	template <std::size_t N> struct is_bounded_char_array<char[N]> : std::true_type {};
	template <class T> struct is_char { static constexpr bool value = std::is_same_v<T, char>; };
	template <class T> struct is_bool { static constexpr bool value = std::is_same_v<T, bool>; };
	template <class T> struct is_string { static constexpr bool value = std::is_same_v<T, std::string> || std::is_same_v<T, const char*> || std::is_same_v<T, char*> || is_bounded_char_array<T>{}; };
	template <class T, class D = void> struct is_custom { static constexpr bool value = false; };
	template <class T> struct is_custom<T, std::void_t<typename T::internal_value_type>> { static constexpr bool value = true; };
	template <class T> struct is_default { static constexpr bool value = is_char<T>::value || is_bool<T>::value || is_string<T>::value || std::is_integral_v<T>; };
	template <class T, class D = void> struct is_iterable { static constexpr bool value = false; };
	template <class T> struct is_iterable< T, typename std::void_t<decltype(std::begin(std::declval<T>()))>> { static constexpr bool value = true; };
	template <class T, class D = void, class E = void> struct is_applyable { static constexpr bool value = false; };
	template <class T> struct is_applyable<T, std::void_t<typename std::tuple_size<T>::type>, std::void_t<decltype(std::get<0>(std::declval<T>()))>> { static constexpr bool value = true; };
	template <class T> struct has_val {
		template <class U> static auto check(U v) -> decltype(v.val(), std::true_type());
		static auto check(...) -> decltype(std::false_type());
		typedef decltype(check(std::declval<T>())) type;
		static constexpr bool value = type::value;
	};
	template <class T> struct has_constructor_ll {
		template <class U> static auto check(U v) -> decltype(U(std::declval<long long>()), std::true_type());
		static auto check(...) -> decltype(std::false_type());
		typedef decltype(check(std::declval<T>())) type;
		static constexpr bool value = type::value;
	};
	template <class T> static constexpr bool needs_newline = (is_iterable<T>::value || is_applyable<T>::value) && (!is_default<T>::value);
	template <typename T, typename U> struct any_needs_newline { static constexpr bool value = false; };
	template <typename T> struct any_needs_newline<T, std::index_sequence<>> { static constexpr bool value = false; };
	template <typename T, std::size_t I, std::size_t... Is> struct any_needs_newline<T, std::index_sequence<I, Is...>> {
		static constexpr bool value = needs_newline<decltype(std::get<I>(std::declval<T>()))> || any_needs_newline<T, std::index_sequence<Is...>>::value;
	};
	inline void load() {
		memmove(std::begin(input_buffer), std::begin(input_buffer) + input_ptr_left, input_ptr_right - input_ptr_left);
		input_ptr_right = input_ptr_right - input_ptr_left + static_cast<int>(fread_unlocked(std::begin(input_buffer) + input_ptr_right - input_ptr_left, 1, SZ - input_ptr_right + input_ptr_left, stdin));
		input_ptr_left = 0;
	}
	inline void read_char(char& c) {
		if (input_ptr_left + LEN > input_ptr_right) load();
		c = input_buffer[input_ptr_left++];
	}
	inline void read_string(std::string& x) {
		char c; while (read_char(c), c < '!') continue;
		x = c; while (read_char(c), c >= '!') x += c;
	}
	template <class T> inline std::enable_if_t<std::is_floating_point_v<T>, void> read_float(T& x) {
		std::string s; read_string(s); x = std::stod(s);
	}
	template <class T> inline std::enable_if_t<std::is_integral_v<T>, void> read_int(T& x) {
		if (input_ptr_left + LEN > input_ptr_right) load();
		char c = 0;
		do c = input_buffer[input_ptr_left++]; while (c < '-');
		[[maybe_unused]] bool minus = false;
		if constexpr (std::is_signed<T>::value == true) if (c == '-') minus = true, c = input_buffer[input_ptr_left++];
		x = 0;
		while (c >= '0') x = x * TEN + (c & MASK), c = input_buffer[input_ptr_left++];
		if constexpr (std::is_signed<T>::value == true) if (minus) x = -x;
	}
	inline void skip_space() {
		if (input_ptr_left + LEN > input_ptr_right) load();
		while (input_buffer[input_ptr_left] <= ' ') input_ptr_left++;
	}
	inline void flush() {
		fwrite_unlocked(std::begin(output_buffer), 1, output_ptr_right, stdout);
		output_ptr_right = 0;
	}
	inline void write_char(char c) {
		if (output_ptr_right > SZ - LEN) flush();
		output_buffer[output_ptr_right++] = c;
	}
	inline void write_bool(bool b) {
		if (output_ptr_right > SZ - LEN) flush();
		output_buffer[output_ptr_right++] = b ? '1' : '0';
	}
	inline void write_string(const std::string& s) {
		for (auto x : s) write_char(x);
	}
	inline void write_string(const char* s) {
		while (*s) write_char(*s++);
	}
	inline void write_string(char* s) {
		while (*s) write_char(*s++);
	}
	template <typename T> inline std::enable_if_t<std::is_floating_point_v<T>, void> write_float(T x) {
		std::ostringstream s; s.setf(ios::fixed), s.precision(precision_value); s << x; write_string(s.str());
	}
	template <typename T> inline std::enable_if_t<std::is_integral_v<T>, void> write_int(T x) {
		if (output_ptr_right > SZ - LEN) flush();
		if (!x) { output_buffer[output_ptr_right++] = '0'; return; }
		if constexpr (std::is_signed<T>::value == true) if (x < 0) output_buffer[output_ptr_right++] = '-', x = -x;
		int i = TWELVE;
		std::array<char, SIXTEEN> buf{};
		while (x >= TENTHOUSAND) { memcpy(std::begin(buf) + i, std::begin(io_pre.num) + (x % TENTHOUSAND) * 4, 4); x /= TENTHOUSAND; i -= 4; }
		if (x < HUNDRED) {
			if (x < TEN) {
				output_buffer[output_ptr_right++] = static_cast<char>('0' + x);
			} else {
				std::uint32_t q = (static_cast<std::uint32_t>(x) * MAGIC_MULTIPLY) >> MAGIC_SHIFT, r = static_cast<std::uint32_t>(x) - q * TEN;
				output_buffer[output_ptr_right] = static_cast<char>('0' + q);
				output_buffer[output_ptr_right + 1] = static_cast<char>('0' + r);
				output_ptr_right += 2;
			}
		} else {
			if (x < THOUSAND) memcpy(std::begin(output_buffer) + output_ptr_right, std::begin(io_pre.num) + (x << 2) + 1, 3), output_ptr_right += 3;
			else memcpy(std::begin(output_buffer) + output_ptr_right, std::begin(io_pre.num) + (x << 2), 4), output_ptr_right += 4;
		}
		memcpy(std::begin(output_buffer) + output_ptr_right, std::begin(buf) + i + 4, TWELVE - i);
		output_ptr_right += TWELVE - i;
	}
	template <typename T> IO& operator>>(T& x) {
		static_assert(is_custom<T>::value or is_default<T>::value or is_iterable<T>::value or is_applyable<T>::value or std::is_floating_point_v<T> or has_constructor_ll<T>::value);
		static_assert(!is_bool<T>::value);
		if constexpr (is_custom<T>::value) {
			typename T::internal_value_type y; read_int(y); x = y;
		} else if constexpr (is_default<T>::value) {
			if constexpr (is_string<T>::value) {
				read_string(x);
			} else if constexpr (is_char<T>::value) {
				read_char(x);
			} else if constexpr (std::is_integral_v<T>) {
				read_int(x);
			}
		} else if constexpr (is_iterable<T>::value) {
			for (auto& y : x) operator>>(y);
		} else if constexpr (is_applyable<T>::value) {
			std::apply([this](auto&... y) { ((this->operator>>(y)), ...); }, x);
		} else if constexpr (std::is_floating_point_v<T>) {
			read_float(x);
		} else if constexpr (has_constructor_ll<T>::value) {
			long long y; read_int(y); x = y;
		}
		return *this;
	}
	template <typename T_> IO& operator<<(T_&& x) {
		using T = typename std::remove_cv< typename std::remove_reference<T_>::type>::type;
		static_assert(is_custom<T>::value or is_default<T>::value or is_iterable<T>::value or is_applyable<T>::value or std::is_floating_point_v<T> or has_val<T>::value);
		if constexpr (is_custom<T>::value) {
			write_int(x.get());
		} else if constexpr (is_default<T>::value) {
			if constexpr (is_bool<T>::value) {
				write_bool(x);
			} else if constexpr (is_string<T>::value) {
				write_string(x);
			} else if constexpr (is_char<T>::value) {
				write_char(x);
			} else if constexpr (std::is_integral_v<T>) {
				write_int(x);
			}
		} else if constexpr (is_iterable<T>::value) {
			constexpr char sep = needs_newline<decltype(*std::begin(x))> ? '\n' : ' '; int i = 0;
			for (const auto& y : x) { if (i++) write_char(sep); operator<<(y); }
		} else if constexpr (is_applyable<T>::value) {
			constexpr char sep = (any_needs_newline<T, std::make_index_sequence<std::tuple_size_v<T>>>::value) ? '\n' : ' '; int i = 0;
			std::apply([this, &sep, &i](auto const&... y) { (((i++ ? write_char(sep) : void()), this->operator<<(y)), ...); }, x);
		} else if constexpr (std::is_floating_point_v<T>) {
			write_float(x);
		} else if constexpr (has_val<T>::value) {
			write_int(x.val());
		}
		return *this;
	}
	IO* tie(std::nullptr_t) { return this; }
	void sync_with_stdio(bool) {}
	void setf(...) {}
	void precision(int n) { precision_value = n; }
};
IO& operator<<(IO& io, [[maybe_unused]]std::ostream& (*var)(std::ostream&)) { io << '\n'; return io; }
IO fastio;
}; // namespace std
#ifdef USE_FASTIO
	#define cin fastio
	#define cout fastio
#endif
#if defined(LOCAL_TEST) || defined(LOCAL_DEV)
	#define BOOST_STACKTRACE_USE_ADDR2LINE
	#define BOOST_STACKTRACE_ADDR2LINE_LOCATION /usr/local/opt/binutils/bin/addr2line
	#define _GNU_SOURCE 1
	#include <boost/stacktrace.hpp>
#endif
#ifdef LOCAL_TEST
	namespace std {
		template <typename T> class dvector : public std::vector<T> {
		public:
			using std::vector<T>::vector;
			template <typename T_ = T, typename std::enable_if_t<std::is_same_v<T_, bool>, std::nullptr_t> = nullptr>
			constexpr std::vector<bool>::reference operator[](std::size_t n) {
				if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
			}
			template <typename T_ = T, typename std::enable_if_t<std::is_same_v<T_, bool>, std::nullptr_t> = nullptr>
			constexpr const T_ operator[](std::size_t n) const {
				if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
			}
			template <typename T_ = T, typename std::enable_if_t<!std::is_same_v<T_, bool>, std::nullptr_t> = nullptr>
			constexpr T_& operator[](std::size_t n) {
				if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
			}
			template <typename T_ = T, typename std::enable_if_t<!std::is_same_v<T_, bool>, std::nullptr_t> = nullptr>
			constexpr const T_& operator[](std::size_t n) const {
				if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
			}
		};
		template <typename T, std::size_t N> class darray : public std::array<T, N> {
		public:
			using std::array<T, N>::array;
			constexpr darray(std::initializer_list<T> il) {
				*this = {}; int i = 0; for (auto&& x : il) this->operator[](i++) = x;
			}
			constexpr T& operator[](std::size_t n) {
				if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
			}
			constexpr const T& operator[](std::size_t n) const {
				if (this->size() <= n) { std::cerr << boost::stacktrace::stacktrace() << '\n' << "vector::_M_range_check: __n (which is " << n << ") >= this->size() (which is " << this->size() << ")" << '\n'; } return this->at(n);
			}
		};
		template <typename T, std::size_t N> struct tuple_size<std::darray<T, N>> : integral_constant<std::size_t, N> {};
		template <typename T, std::size_t N, std::size_t I> struct tuple_element<I, std::darray<T, N>> { using type = T; };
		template <typename T, typename Compare = std::less<T>> class dmultiset : public std::multiset<T, Compare> {
		public:
			using std::multiset<T, Compare>::multiset;
			const typename std::multiset<T, Compare>::iterator erase(const typename std::multiset<T, Compare>::iterator it) {
				return std::multiset<T, Compare>::erase(it);
			}
			std::size_t erase([[maybe_unused]] const T& x) {
				std::cerr << boost::stacktrace::stacktrace() << '\n'; assert(false);
			}
			std::size_t erase_all_elements(const T& x) {
				return std::multiset<T, Compare>::erase(x);
			}
		};
	}
	#define vector dvector
	#define array darray
	#define multiset dmultiset
	class SIGFPE_exception : std::exception {};
	class SIGSEGV_exception : std::exception {};
	void catch_SIGFPE([[maybe_unused]] int e) { std::cerr << boost::stacktrace::stacktrace() << '\n'; throw SIGFPE_exception(); }
	void catch_SIGSEGV([[maybe_unused]] int e) { std::cerr << boost::stacktrace::stacktrace() << '\n'; throw SIGSEGV_exception(); }
	signed convertedmain();
	signed main() { signal(SIGFPE, catch_SIGFPE); signal(SIGSEGV, catch_SIGSEGV); return convertedmain(); }
	#define main() convertedmain()
#else
	#define erase_all_elements erase
#endif
#ifdef LOCAL_DEV
	template <typename T1, typename T2> std::ostream& operator<<(std::ostream& s, const std::pair<T1, T2>& p) {
		return s << "(" << p.first << ", " << p.second << ")"; }
	template <typename T, std::size_t N> std::ostream& operator<<(std::ostream& s, const std::array<T, N>& a) {
		s << "{ "; for (std::size_t i = 0; i < N; ++i){ s << a[i] << "\t"; } s << "}"; return s; }
	template <typename T, typename Compare> std::ostream& operator<<(std::ostream& s, const std::set<T, Compare>& se) {
		s << "{ "; for (auto itr = se.begin(); itr != se.end(); ++itr){ s << (*itr) << "\t"; } s << "}"; return s; }
	template <typename T, typename Compare> std::ostream& operator<<(std::ostream& s, const std::multiset<T, Compare>& se) {
		s << "{ "; for (auto itr = se.begin(); itr != se.end(); ++itr){ s << (*itr) << "\t"; } s << "}"; return s; }
	template <typename T1, typename T2, typename Compare> std::ostream& operator<<(std::ostream& s, const std::map<T1, T2, Compare>& m) {
		s << "{\n"; for (auto itr = m.begin(); itr != m.end(); ++itr){ s << "\t" << (*itr).first << " : " << (*itr).second << "\n"; } s << "}"; return s; }
	template <typename T> std::ostream& operator<<(std::ostream& s, const std::deque<T>& v) {
		for (std::size_t i = 0; i < v.size(); ++i){ s << v[i]; if (i < v.size() - 1) s << "\t"; } return s; }
	template <typename T> std::ostream& operator<<(std::ostream& s, const std::vector<T>& v) {
		for (std::size_t i = 0; i < v.size(); ++i){ s << v[i]; if (i < v.size() - 1) s << "\t"; } return s; }
	template <typename T> std::ostream& operator<<(std::ostream& s, const std::vector<std::vector<T>>& vv) {
		s << "\\\n"; for (std::size_t i = 0; i < vv.size(); ++i){ s << vv[i] << "\n"; } return s; }
	template <typename T, std::size_t N, typename std::enable_if_t<!std::is_same_v<T, char>, std::nullptr_t> = nullptr> std::ostream& operator<<(std::ostream& s, const T (&v)[N]) {
		for (std::size_t i = 0; i < N; ++i){ s << v[i]; if (i < N - 1) s << "\t"; } return s; }
	template <typename T, std::size_t N, std::size_t M, typename std::enable_if_t<!std::is_same_v<T, char>, std::nullptr_t> = nullptr> std::ostream& operator<<(std::ostream& s, const T (&vv)[N][M]) {
		s << "\\\n"; for (std::size_t i = 0; i < N; ++i){ s << vv[i] << "\n"; } return s; }
	#if __has_include(<ext/pb_ds/assoc_container.hpp>)
		template <typename Key, typename Compare> std::ostream& operator<<(std::ostream& s, const __gnu_pbds::tree<Key, __gnu_pbds::null_type, Compare, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>& se) {
			s << "{ "; for (auto itr = se.begin(); itr != se.end(); ++itr){ s << (*itr) << "\t"; } s << "}"; return s; }
		template <typename Key, typename T, typename Hash> std::ostream& operator<<(std::ostream& s, const __gnu_pbds::gp_hash_table<Key, T, Hash>& m) {
			s << "{\n"; for (auto itr = m.begin(); itr != m.end(); ++itr){ s << "\t" << (*itr).first << " : " << (*itr).second << "\n"; } s << "}"; return s; }
	#endif
	void debug_impl() { std::cerr << '\n'; }
	template <typename Head, typename... Tail> void debug_impl(Head& head, Tail&... tail) { std::cerr << " " << head << (sizeof...(Tail) ? "," : ""); debug_impl(tail...); }
	template <typename Head, typename... Tail> void debug_impl(const Head& head, const Tail&... tail) { std::cerr << " " << head << (sizeof...(Tail) ? "," : ""); debug_impl(tail...); }
	#define debug(...) do { std::cerr << ":" << __LINE__ << " (" << #__VA_ARGS__ << ") ="; debug_impl(__VA_ARGS__); } while (false)
	constexpr inline long long prodlocal([[maybe_unused]] long long prod, [[maybe_unused]] long long local) { return local; }
#else
	#define debug(...) do {} while (false)
	constexpr inline long long prodlocal([[maybe_unused]] long long prod, [[maybe_unused]] long long local) { return prod; }
#endif
#define repoverload3(_1, _2, _3, name, ...) name
#define rep3(i, a, b) for(ll i=(a), i##_length=(b); i<i##_length; ++i)
#define rep2(i, n) rep3(i, 0, n)
#define rep1(n) rep3(i, 0, n)
#define rep(...) repoverload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define repeq3(i, a, b) rep3(i, (a)+1, (b)+1)
#define repeq2(i, n) rep3(i, 1, (n)+1)
#define repeq1(n) rep3(i, 1, (n)+1)
#define repeq(...) repoverload3(__VA_ARGS__, repeq3, repeq2, repeq1)(__VA_ARGS__)
#define rrep3(i, a, b) for(ll i=(b)-1; i>=(a); --i)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep1(n) rrep3(i, 0, n)
#define rrep(...) repoverload3(__VA_ARGS__, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rrepeq3(i, a, b) rrep3(i, (a)+1, (b)+1)
#define rrepeq2(i, n) rrep3(i, 1, (n)+1)
#define rrepeq1(n) rrep3(i, 1, (n)+1)
#define rrepeq(...) repoverload3(__VA_ARGS__, rrepeq3, rrepeq2, rrepeq1)(__VA_ARGS__)
#define all(v) std::begin(v), std::end(v)
#define rall(v) std::rbegin(v), std::rend(v)
void p() { std::cout << '\n'; }
template <typename Head, typename... Tail> void p(Head& head, Tail&... tail) { std::cout << head << (sizeof...(Tail) ? " " : ""); p(tail...); }
template <typename Head, typename... Tail> void p(const Head& head, const Tail&... tail) { std::cout << head << (sizeof...(Tail) ? " " : ""); p(tail...); }
template <typename T, typename U = typename T::value_type> inline void pv(const T& v, const U& add = {}) { auto itbegin = std::begin(v), itend = std::end(v); for (auto it = itbegin; it != itend; std::advance(it, 1)) cout << (it == itbegin ? "" : " ") << *it + add; cout << '\n'; }
template <typename T> inline bool chmax(T& a, T b) { return a < b && (a = b, true); }
template <typename T> inline bool chmin(T& a, T b) { return a > b && (a = b, true); }
template <typename T> inline void uniq(T& v) { std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end()); }
template <typename T> inline ll sz(const T& v) { return std::size(v); }
template <typename T, std::size_t N> std::vector<T> make_vector_impl(std::vector<ll>& sizes, typename std::enable_if<(N==1), const T&>::type x) { return std::vector<T>(sizes.front(),x); }
template <typename T, std::size_t N> auto make_vector_impl(std::vector<ll>& sizes, typename std::enable_if<(N>1), const T&>::type x) { ll size=sizes.back(); sizes.pop_back(); return std::vector<decltype(make_vector_impl<T,N-1>(sizes,x))>(size,make_vector_impl<T,N-1>(sizes,x)); }
template <typename T, std::size_t N> auto make_vector(const ll (&sizes)[N], const T& x=T()) { std::vector<ll> s(N); for(std::size_t i=0; i<N; ++i)s[i]=sizes[N-1-i]; return make_vector_impl<T,N>(s,x); }
template <typename T, std::size_t N> std::array<T,N> make_array() { return std::array<T,N>{}; }
template <typename T, std::size_t Head, std::size_t... Tail, typename std::enable_if_t<(sizeof...(Tail)>=1), std::nullptr_t> = nullptr> auto make_array() { return std::array<decltype(make_array<T,Tail...>()),Head>(); }
#if __has_include(<ext/pb_ds/assoc_container.hpp>)
	class custom_hash {
	public:
		constexpr static uint64_t splitmix64(uint64_t x) {
			x += 0x9e3779b97f4a7c15, x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9, x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);
		}
		std::size_t operator()(uint64_t x) const {
			static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM);
		}
		std::size_t operator()(const std::string& x) const {
			return std::hash<std::string>()(x);
		}
	};
	template <typename Key, typename Mapped, typename Hash = custom_hash, typename std::enable_if_t<std::is_integral_v<Key> || std::is_same_v<Key, std::string>, std::nullptr_t> = nullptr> class fmap : public __gnu_pbds::gp_hash_table<Key, Mapped, Hash> {
	public:
		using __gnu_pbds::gp_hash_table<Key, Mapped, Hash>::gp_hash_table;
		template <typename T> fmap(std::initializer_list<std::initializer_list<T>> il) : __gnu_pbds::gp_hash_table<Key, Mapped, Hash>() {
			for (auto&& x : il) __gnu_pbds::gp_hash_table<Key, Mapped, Hash>::insert(std::pair<Key, Mapped>(*x.begin(), *(x.begin() + 1)));
		}
		template <typename T> ll count(const T& x) const {
			return __gnu_pbds::gp_hash_table<Key, Mapped, Hash>::find(x) != __gnu_pbds::gp_hash_table<Key, Mapped, Hash>::end();
		}
	};
#else
	template <typename Key, typename Mapped> using fmap = std::map<Key, Mapped>;
#endif
template <bool Index, typename... T> class zip_helper {
	template <class Category, class Type, class Diff = ptrdiff_t, class Ptr = Type*, class Ref = Type&> struct basic_iterator {
		using difference_type = Diff;
		using value_type = Type;
		using pointer = Ptr;
		using reference = Ref;
		using terator_category = Category;
	};
	class zip_iterator : basic_iterator<std::forward_iterator_tag, std::tuple<decltype(*std::declval<T>().begin())...>> {
	public:
		ll idx_;
		std::tuple<decltype(std::declval<T>().begin())...> iters_;
		template <std::size_t... I> auto deref(std::index_sequence<I...>) const { return typename zip_iterator::value_type{*std::get<I>(iters_)...}; }
		template <std::size_t... I> void increment(std::index_sequence<I...>) { [[maybe_unused]] auto l = {(++std::get<I>(iters_), 0)...}; }
		explicit zip_iterator(decltype(iters_) iters) : idx_(0), iters_{std::move(iters)} {}
		zip_iterator& operator++() { ++idx_; increment(std::index_sequence_for<T...>{}); return *this; }
		zip_iterator operator++(int) { auto saved{*this}; ++idx_; increment(std::index_sequence_for<T...>{}); return saved; }
		bool operator!=(const zip_iterator& other) const { return iters_ != other.iters_; }
		template <bool Index_ = Index, typename std::enable_if_t<Index_, std::nullptr_t> = nullptr> auto operator*() const { return std::tuple_cat(std::make_tuple(this->idx_), this->deref(std::index_sequence_for<T...>{})); }
		template <bool Index_ = Index, typename std::enable_if_t<!Index_, std::nullptr_t> = nullptr> auto operator*() const { return this->deref(std::index_sequence_for<T...>{}); }
	};
public:
	zip_helper(T&... seqs) : begin_{std::make_tuple(seqs.begin()...)}, end_{std::make_tuple(seqs.end()...)} {}
	zip_iterator begin() const { return begin_; }
	zip_iterator end() const { return end_; }
	zip_iterator begin_, end_;
};
template <typename... T> auto zip(T&&... seqs) { return zip_helper<false, T...>{seqs...}; }
template <typename... T> auto zipindex(T&&... seqs) { return zip_helper<true, T...>{seqs...}; }

/*-----8<-----template-----8<-----*/

//[lib]スライド検索fft.cpp
// Cooley–Tukey FFT algorithm
vector<complex<double>> fft(vector<complex<double>> a, bool inverse = false) {
	int n = a.size();
	int h = 0; // h = log_2(n)
	for (int i = 0; 1 << i < n; i++) h++;
	// バタフライ演算用の配置入れ替え
	for (int i = 0; i < n; i++) {
		int j = 0;
		for (int k = 0; k < h; k++) j |= (i >> k & 1) << (h - 1 - k);
		if (i < j) swap(a[i], a[j]);
	}
	// バタフライ演算
	for (int b = 1; b < n; b *= 2) {
		// 第 log_2(b) + 1 段
		// ブロックサイズ = b * 2
		for (int j = 0; j < b; j++) {
			// ブロック内 j 個目
			// 重み w = (1 の原始 2b 乗根の j 乗)
			complex<double> w =
				polar(1.0, (M_PI * 2) / (2 * b) * j * (inverse ? 1 : -1));
			for (int k = 0; k < n; k += b * 2) {
				// k を先頭とするブロック
				complex<double> s = a[j + k];		 // 前
				complex<double> t = a[j + k + b] * w; // 後
				a[j + k] = s + t;					 // 前の更新
				a[j + k + b] = s - t;				 // 後の更新
			}
		}
	}
	// 逆変換時にサイズで割る調整
	if (inverse)
		for (int i = 0; i < n; i++) a[i] /= n;
	return a;
}

vector<complex<double>> fft(vector<double> a, bool inverse = false) {
	vector<complex<double>> a_complex(a.size());
	for(int i=0; i<(ll)a.size(); i++) a_complex[i] = complex<double>(a[i], 0);
	return fft(a_complex, inverse);
}

// FFT による畳み込み O(N log N)
template<typename T> 
vector<complex<double>> convolve(vector<T> a, vector<T> b) {
	int s = a.size() + b.size() - 1; // 畳み込み結果のサイズ
	int t = 1; // FFT に使う配列のサイズ（2 の累乗）
	while (t < s) t *= 2;
	a.resize(t); // FFT するためにリサイズ
	b.resize(t); // FFT するためにリサイズ
	vector<complex<double>> A = fft(a);
	vector<complex<double>> B = fft(b);
	for (int i = 0; i < t; i++) {
		A[i] *= B[i]; // 畳み込み結果の FFT 結果を得る
	}
	A = fft(A, true); // IFFT で畳み込み結果を得る
	A.resize(s);
	return A;
}


vector<ll> findkeyword(const string &text, const string &key, bool partialmatch=false, char firstchar='a'){
	ll textsize=text.size(), keysize=key.size();
	vector<complex<double>> x(text.size(), {0,0}), y(key.size(), {0,0});
	vector<complex<double>> wildx(text.size(), {0,0}), wildy(key.size(), {0,0});
	for(ll i=0; i<textsize; i++){
		if(text[i]=='?')continue;
		double a=2.*M_PI*(text[i]-firstchar)/26.;
		x[i]={cos(a),sin(a)};
		wildx[i]={1,0};
	}
	for(ll i=0; i<keysize; i++){
		if(key[i]=='?')continue;
		double a=2.*M_PI*(key[i]-firstchar)/26.;
		y[keysize-1-i]={cos(a),-sin(a)};
		wildy[keysize-1-i]={1,0};
	}
	vector<complex<double>> c=convolve(x,y);
	vector<complex<double>> wildc=convolve(wildx,wildy);

	vector<ll> ans;
	ll beginval,endval;
	if(partialmatch)beginval=0, endval=c.size();
	else beginval=keysize-1, endval=textsize;
	for(ll i=beginval; i<endval; i++){
		if(abs(c[i].real()-wildc[i].real())<EPS && abs(c[i].imag())<EPS)ans.push_back(-keysize+1+i);
	}
	return ans;
}

/*-----8<-----library-----8<-----*/

void solve() {
	ll N, M;
	cin >> N >> M;
	string text, key;
	cin >> text >> key;
	vector<ll> v = findkeyword(text, key);
	if(v.size()==0){
		p(-1);
		return;
	}
	rep(i,M){
		text[i + v.back()] = key[i];
	}
	rep(i,N){
		if (text[i] == '?') text[i] = 'a';
	}
	p(text);
}

signed main() {
#ifdef LOCAL_DEV
	//std::ifstream in("in.txt");
	//std::cin.rdbuf(in.rdbuf());
#else
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
#endif
	ll Q; cin >> Q; while(Q--)solve();
	//solve();
	return 0;
}