//#pragma GCC optimize("O2")
#define _USE_MATH_DEFINES
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
#include <bits/stdc++.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 ENV_USE_FASTIO 1
#define ENV_USE_ENDL 0
#if !defined(LOCAL_DEV) && ENV_USE_FASTIO
	#define USE_FASTIO
#endif
#if ENV_USE_ENDL
	#define NEWLINE std::endl
#else
	#define NEWLINE '\n'
#endif
//#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};
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_to_string {
		template <class U> static auto check(U v) -> decltype(v.to_string(), 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_string {
		template <class U> static auto check(U v) -> decltype(U(std::declval<std::string>()), 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) 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) 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_string<T>::value 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_string<T>::value) { std::string y; read_string(y); x = y; }
		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 or has_to_string<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()); }
		else if constexpr (has_to_string<T>::value) { write_string(x.to_string()); }
		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>
			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>
			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);
			}
		};
		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>& v) {
			s << "{ "; for (std::size_t i = 0; i < N; ++i){ s << v[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 it = se.begin(); it != se.end(); ++it){ s << *it << "\t"; } s << "}"; return s; }
		template <typename T, typename Compare> std::ostream& operator<<(std::ostream& s, const std::multiset<T, Compare>& se) {
			s << "{ "; for (auto it = se.begin(); it != se.end(); ++it){ s << *it << "\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 it = m.begin(); it != m.end(); ++it){ s << "\t" << it->first << " : " << it->second << "\n"; } s << "}"; return s; }
		template <typename T> std::ostream& operator<<(std::ostream& s, const std::deque<T>& v) {
			s << "{ "; for (std::size_t i = 0; i < v.size(); ++i){ s << v[i] << "\t"; } s << "}"; return s; }
		template <typename T> std::ostream& operator<<(std::ostream& s, const std::dvector<T>& v) {
			s << "{ "; for (std::size_t i = 0; i < v.size(); ++i){ s << v[i] << "\t"; } s << "}"; return s; }
		template <typename T> std::ostream& operator<<(std::ostream& s, const std::dvector<std::dvector<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]) {
			s << "{ "; for (std::size_t i = 0; i < N; ++i){ s << v[i] << "\t"; } s << "}"; 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; }
	} // namespace std
	#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
	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 << NEWLINE; }
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 << NEWLINE; }
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>(); }
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...}; }
#include <bits/extc++.h>
#if __has_include(<ext/pb_ds/assoc_container.hpp>)
#ifdef LOCAL_TEST
	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 it = se.begin(); it != se.end(); ++it){ s << *it << "\t"; } s << "}"; return s; }
	template <typename Key, typename Mapped, typename Hash> std::ostream& operator<<(std::ostream& s, const __gnu_pbds::gp_hash_table<Key, Mapped, Hash>& m) {
		s << "{\n"; for (auto it = m.begin(); it != m.end(); ++it){ s << "\t" << it->first << " : " << it->second << "\n"; } s << "}"; return s; }
#endif
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 T1, typename T2, typename std::enable_if_t<std::is_integral_v<T1> && std::is_integral_v<T2>, std::nullptr_t> = nullptr> std::size_t operator() (const std::pair<T1, T2>& x) const {
		std::size_t lhs = operator()(x.first), rhs = operator()(x.second); return lhs ^ (rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2));
	}
	template <typename T, typename std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr> std::size_t operator()(const std::vector<T>& x) const {
		std::size_t h = x.size(); for (auto&& k : x) h ^= operator()(k) + 0x9e3779b9 + (h << 6) + (h >> 2); return h;
	}
	template <typename T, std::size_t N, typename std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr> std::size_t operator()(const std::array<T, N>& x) const {
		std::size_t h = x.size(); for (auto&& k : x) h ^= operator()(k) + 0x9e3779b9 + (h << 6) + (h >> 2); return h;
	}
};
template <typename Key, typename Mapped, typename Hash = custom_hash> 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

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


//[lib](internal)edge.cpp
using EdgeCostType = ll;
using usize = ll;
template <class T> class edge_type {
public:
	inline static int edgeidx = 0;
	usize from, to;
	T cost;
	int idx;
	edge_type() {}
	edge_type(usize from, usize to, T cost) : from(from), to(to), cost(cost), idx(edgeidx++) {}
	edge_type(usize from, usize to, T cost, usize idx) : from(from), to(to), cost(cost), idx(idx) {}
	bool operator<(const edge_type& r) const { return r.cost < cost; }
};
using Edge = edge_type<EdgeCostType>;
ostream& operator<<(ostream &s, const Edge &e) {
	s << "{ " << e.from << " -> " << e.to << ", " << e.cost << " }";
	return s;
}
inline void addedge(vector<vector<Edge>> &g, usize from, usize to, EdgeCostType cost) {
	g[from].emplace_back(from, to, cost, Edge::edgeidx);
	g[to].emplace_back(to, from, cost, Edge::edgeidx);
	Edge::edgeidx++;
}
//最短路木の親頂点を元にstart->goalの経路を作成
vector<ll> buildPath(const vector<ll> &prev, ll goal) {
	vector<ll> path;
	for (ll u = goal; u >= 0; u = prev[u]) path.push_back(u);
	reverse(path.begin(), path.end());
	return path;
}

vector<vector<ll>> conv_edge2ll(const vector<vector<Edge>> &g) {
	vector<vector<ll>> h(g.size());
	for (auto&& v : g) for (auto&& e : v) h[e.from].emplace_back(e.to);
	return h;
}
vector<vector<Edge>> conv_ll2edge(const vector<vector<ll>> &g) {
	vector<vector<Edge>> h(g.size());
	for (int i = 0; i < (int)g.size(); i++) for (auto&& j : g[i]) {
		if (i <= j) continue;
		h[i].emplace_back(i, j, 1, Edge::edgeidx);
		h[j].emplace_back(j, i, 1, Edge::edgeidx);
		Edge::edgeidx++;
	}
	return h;
}

/*
計算量：O(min(V^2, ElogV))
引数
　g:探索するグラフ
　start:探索するスタートノード番号
戻り値
　dist:スタートノードから各頂点までの距離
　prev:最短路木の親頂点

負辺があっても動作するが最悪指数時間かかる
https://theory-and-me.hatenablog.com/entry/2019/09/08/182442
*/
void dijkstra_elogv(const vector<vector<Edge>> &g, ll start, vector<EdgeCostType> &dist, vector<ll> &prev) {
	int gsize = g.size();
	dist.assign(gsize, INF); dist[start] = 0;
	prev.assign(gsize, -1);
	auto compare_edge = [](const Edge& x, const Edge& y) {
		return x.cost != y.cost ? (x.cost > y.cost) : (x.from != y.from ? x.from < y.from : x.to < y.to);
	};
	priority_queue<Edge, vector<Edge>, decltype(compare_edge)> que(compare_edge);
	que.emplace(-1, start, 0);
	while (!que.empty()) {
		Edge e = que.top();
		que.pop();
		if (dist[e.to] < e.cost) continue;
		prev[e.to] = e.from;
		for (auto&& f : g[e.to]) {
			auto newcost = e.cost + f.cost;
			if (dist[f.to] > newcost) {
				dist[f.to] = newcost;
				que.emplace(f.from, f.to, newcost);
			}
		}
	}
}
template <class Func>
void dijkstra_elogv(const size_t gsize, const Func &gfunc, ll start, vector<EdgeCostType> &dist, vector<ll> &prev) {
	dist.assign(gsize, INF); dist[start] = 0;
	prev.assign(gsize, -1);
	auto compare_edge = [](const Edge& x, const Edge& y) {
		return x.cost != y.cost ? (x.cost > y.cost) : (x.from != y.from ? x.from < y.from : x.to < y.to);
	};
	priority_queue<Edge, vector<Edge>, decltype(compare_edge)> que(compare_edge);
	que.emplace(-1, start, 0);
	while (!que.empty()) {
		Edge e = que.top();
		que.pop();
		if (dist[e.to] < e.cost) continue;
		prev[e.to] = e.from;
		gfunc(e.to, [&](const usize nextv, const EdgeCostType nextcost) {
			auto newcost = e.cost + nextcost;
			if (dist[nextv] > newcost) {
				dist[nextv] = newcost;
				que.emplace(e.to, nextv, newcost);
			}
		});
	}
}
void dijkstra_v2(const vector<vector<Edge>> &g, ll start, vector<EdgeCostType> &dist, vector<ll> &prev) {
	int gsize = g.size();
	dist.assign(gsize, INF); dist[start] = 0;
	prev.assign(gsize, -1);
	vector<bool> seen(gsize, false);
	for (int k = 0; k < gsize - 1; ++k) {
		EdgeCostType minval = INF;
		int idx = -1;
		for (int i = 0; i < gsize; ++i) {
			if (!seen[i] && chmin(minval, dist[i])) idx = i;
		}
		if (idx == -1) break;
		seen[idx] = true;
		for (auto&& e : g[idx]) {
			if (chmin(dist[e.to], dist[idx] + e.cost)) prev[e.to] = idx;
		}
	}
}
template <class Func>
void dijkstra_v2(const size_t gsize, const Func &gfunc, ll start, vector<EdgeCostType> &dist, vector<ll> &prev) {
	dist.assign(gsize, INF); dist[start] = 0;
	prev.assign(gsize, -1);
	vector<bool> seen(gsize, false);
	for (int k = 0; k < gsize - 1; ++k) {
		EdgeCostType minval = INF;
		int idx = -1;
		for (int i = 0; i < gsize; ++i) {
			if (!seen[i] && chmin(minval, dist[i])) idx = i;
		}
		if (idx == -1) break;
		seen[idx] = true;
		gfunc(idx, [&](const usize nextv, const EdgeCostType nextcost) {
			if (chmin(dist[nextv], dist[idx] + nextcost)) prev[nextv] = idx;
		});
	}
}
/*
constexpr size_t dijkstra_v2_threshold = 0;
void dijkstra(const vector<vector<Edge>>& g, ll start, vector<EdgeCostType>& dist, vector<ll>& prev) {
	if (g.size() <= dijkstra_v2_threshold) dijkstra_v2(g, start, dist, prev);
	else dijkstra_elogv(g, start, dist, prev);
}
template <class Func>
void dijkstra(const size_t gsize, const Func &gfunc, ll start, vector<EdgeCostType> &dist, vector<ll> &prev) {
	if (gsize <= dijkstra_v2_threshold) dijkstra_v2(gsize, gfunc, start, dist, prev);
	else dijkstra_elogv(gsize, gfunc, start, dist, prev);
}
*/
//[lib]dijkstra.cpp
//[depends on](internal)edge.cpp
template <class T> class fibonacci_heap {
	class node_type;
	using node_ptr = node_type *;
	class node_type {
	public:
		node_ptr parent;
		node_ptr child;
		node_ptr left;
		node_ptr right;
		usize rank;
		bool mark;
		T key;
		usize prev;
		node_type() : parent(nullptr), child(nullptr), left(nullptr), right(nullptr), rank(0), mark(false), key(std::numeric_limits<T>::max()), prev(-1) {};
	};

	vector<node_type> nodes;
	node_ptr root;
	vector<node_ptr> table;

public:
	fibonacci_heap(const usize n) : nodes(n), root(nullptr), table(std::ceil(std::log(n + 1) * 2.08), nullptr) {}

	bool empty() const { return root == nullptr; }

	edge_type<T> pop() {
		edge_type<T> ret = {root->prev, static_cast<usize>(root - nodes.data()), root->key};

		usize max = 0;
		const auto push = [&](node_ptr v) -> void {
			while (true) {
				node_ptr u = table[v->rank];
				if (u == nullptr) {
					table[v->rank] = v;
					break;
				}
				table[v->rank] = nullptr;
				if (u->key < v->key) {
					std::swap(u, v);
				}
				const node_ptr c = v->child;
				if (c == nullptr) {
					u->left = u;
					u->right = u;
					v->child = u;
				} else {
					u->left = c->left;
					u->right = c;
					c->left->right = u;
					c->left = u;
				}
				u->parent = v;
				v->rank += 1;
			}
			max = std::max(max, v->rank + 1);
		};

		{
			node_ptr v = root->right;
			while (v != root) {
				const node_ptr next = v->right;
				push(v);
				v = next;
			}
		}
		if (root->child != nullptr) {
			node_ptr v = root->child;
			do {
				const node_ptr next = v->right;
				v->mark = false;
				push(v);
				v = next;
			} while (v != root->child);
		}
		root = nullptr;

		for (usize i = 0; i != max; i += 1) {
			const node_ptr v = table[i];
			if (v == nullptr) {
				continue;
			}
			table[i] = nullptr;
			v->parent = nullptr;
			if (root == nullptr) {
				root = v;
				v->left = v;
				v->right = v;
			} else {
				v->left = root->left;
				v->right = root;
				root->left->right = v;
				root->left = v;
				if (root->key > v->key) {
					root = v;
				}
			}
		}

		return ret;
	}

	void update_key(const usize v_, const T key, const usize prev) {
		node_ptr v = &nodes[v_];

		if (v->key <= key) {
			return;
		}
		v->key = key;
		v->prev = prev;

		if (v->left == nullptr) {
			if (root == nullptr) {
				v->left = v;
				v->right = v;
				root = v;
			} else {
				v->left = root->left;
				v->right = root;
				root->left->right = v;
				root->left = v;
				if (key < root->key) {
					root = v;
				}
			}
			return;
		}

		if (v->parent == nullptr) {
			if (key < root->key) {
				root = v;
			}
			return;
		} else {
			if (v->parent->key <= key) {
				return;
			}
		}

		while (true) {
			const node_ptr p = v->parent;
			v->left->right = v->right;
			v->right->left = v->left;
			v->parent = nullptr;
			p->rank -= 1;
			if (p->child == v) {
				if (p->rank == 0) {
					p->child = nullptr;
				} else {
					p->child = v->right;
				}
			}

			v->left = root->left;
			v->right = root;
			root->left->right = v;
			root->left = v;
			v->mark = false;

			v = p;
			if (v->parent == nullptr) {
				break;
			}
			if (!v->mark) {
				v->mark = true;
				break;
			}
		}
		if (root->key > key) {
			root = &nodes[v_];
		}
	}
};
/*
計算量：O(E+VlogV)
引数
　g:探索するグラフ
　start:探索するスタートノード番号
戻り値
　dist:スタートノードから各頂点までの距離
　prev:最短路木の親頂点
*/
void dijkstra(const vector<vector<Edge>> &g, ll start, vector<EdgeCostType> &dist, vector<ll> &prev) {
	dist.assign(g.size(), INF); dist[start] = 0;
	prev.assign(g.size(), -1);
	fibonacci_heap<EdgeCostType> heap(g.size());
	heap.update_key(start, 0, -1);
	while (!heap.empty()) {
		const auto top = heap.pop();
		dist[top.to] = top.cost;
		prev[top.to] = top.from;
		for (const auto &edge : g[top.to]) {
			heap.update_key(edge.to, top.cost + edge.cost, edge.from);
		}
	}
}
template <class Func>
void dijkstra(const ll gsize, const Func &gfunc, ll start, vector<EdgeCostType> &dist, vector<ll> &prev) {
	dist.assign(gsize, INF); dist[start] = 0;
	prev.assign(gsize, -1);
	fibonacci_heap<EdgeCostType> heap(gsize);
	heap.update_key(start, 0, -1);
	while (!heap.empty()) {
		const auto top = heap.pop();
		dist[top.to] = top.cost;
		prev[top.to] = top.from;
		gfunc(top.to, [&](const usize nextv, const EdgeCostType nextcost) {
			heap.update_key(nextv, top.cost + nextcost, top.to);
		});
	}
}

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

void solve() {
	ll N, K;
	cin >> N >> K;
	ll SX, SY, GX, GY;
	cin >> SX >> SY >> GX >> GY;
	vector<ll> X(N), Y(N);
	rep(i, N) cin >> X[i] >> Y[i];
	X.push_back(SX);
	X.push_back(GX);
	Y.push_back(SY);
	Y.push_back(GY);
	N += 2;

	//初期は left->OK / right->NG になっています
	using rangetype = ll;
	rangetype left = 1e9;
	rangetype right = 0;
	auto isOK = [&](rangetype val) -> bool {
		vector<vector<Edge>> g(N);
		rep(i,N)rep(j,i+1,N){
			if (i == j) continue;
			ll d = abs(X[i] - X[j]) + abs(Y[i] - Y[j]);
			/*
			0..val 0
			val+1..2val 1
			*/
			ll c = (d-1) / val;
			chmax(c, 0LL);
			addedge(g, i, j, c);
		}
		vector<ll> dist, prev;
		dijkstra(g, N-2, dist, prev);
		return dist[N - 1] <= K;
	};
	while (abs(right - left) > 1) {
		rangetype mid = left + (right - left) / 2;
		if (isOK(mid)) left = mid;
		else right = mid;
	}
	p(left);
}

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;
}