//#pragma GCC optimize("O2")
//#pragma GCC target("avx2")
#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
namespace fastio_impl {
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_endl {};
struct IO_flush {};
std::ostream& operator<<(std::ostream& os, const IO_endl&) { return os << std::endl; }
std::ostream& operator<<(std::ostream& os, const IO_flush&) { return os << std::flush; }
template <class T> concept is_IO_endl = std::is_same_v<T, IO_endl>;
template <class T> concept is_IO_flush = std::is_same_v<T, IO_flush>;
template <class T> concept is_char = std::is_same_v<T, char>;
template <class T> concept is_bool = std::is_same_v<T, bool>;
template <class> struct is_bounded_char_array_t : std::false_type {};
template <std::size_t N> struct is_bounded_char_array_t<char[N]> : std::true_type {};
template <class T> concept is_bounded_char_array = std::is_bounded_array_v<T> && std::is_base_of_v<std::true_type, is_bounded_char_array_t<T>>;
template <class T> concept is_string = 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> concept is_default = is_char<T> || is_bool<T> || is_string<T> || std::is_integral_v<T>;
template <class T> concept is_int128 = std::is_same_v<T, __int128_t> || std::is_same_v<T, __uint128_t>;
template <class T> concept has_val = requires(T& v) { v.val(); };
template <class T> concept has_to_string = requires(T& v) { v.to_string(); };
template <class T> concept has_str = requires(T& v) { v.str(); };
template <class T> concept has_constructor_string = std::is_constructible_v<T, std::string>;
template <class T> concept has_constructor_ll = std::is_constructible_v<T, long long>;
template <class T> concept is_constructible_istreambuf_iterator = std::is_constructible_v<std::istreambuf_iterator<char>, T>;
template <class T> concept is_custom = requires(T& v) { T::internal_value_type(); };
template <class T> concept is_iterable = requires(T& v) { std::begin(std::declval<T>()); std::end(std::declval<T>()); };
template <class T> concept is_applyable = requires(T& v) { std::tuple_size<T>::type(); std::get<0>(std::declval<T>()); };
template <class T> static constexpr bool needs_newline = (is_iterable<T> || is_applyable<T>) && (!is_default<T>);
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; };
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;
	bool is_sync_with_stdio;
	FILE *infile, *outfile;
	std::istream *instream;
	std::ostream *outstream;
	IO() : input_buffer{}, output_buffer{}, input_ptr_left{}, input_ptr_right{}, output_ptr_right{}, precision_value{20}, is_sync_with_stdio{false}, infile{stdin}, outfile{stdout}, instream{nullptr}, outstream{nullptr} {}
	IO(const IO&) = delete;
	IO(IO&&) = delete;
	IO& operator=(const IO&) = delete;
	IO& operator=(IO&&) = delete;
	~IO() { flush(); }
	inline void load() {
		memmove(std::begin(input_buffer), std::begin(input_buffer) + input_ptr_left, input_ptr_right - input_ptr_left);
		int bytes_read = static_cast<int>(instream ? instream->read(std::begin(input_buffer) + input_ptr_right - input_ptr_left, SZ - input_ptr_right + input_ptr_left).gcount() : fread_unlocked(std::begin(input_buffer) + input_ptr_right - input_ptr_left, 1, SZ - input_ptr_right + input_ptr_left, infile));
		input_ptr_right = input_ptr_right - input_ptr_left + bytes_read;
		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() {
		if (outstream) for (int i = 0; i < output_ptr_right; ++i) *outstream << output_buffer[i];
		else fwrite_unlocked(std::begin(output_buffer), 1, output_ptr_right, outfile);
		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> or is_default<T> or is_iterable<T> or is_applyable<T> or std::is_floating_point_v<T> or has_constructor_string<T> or has_constructor_ll<T>);
		static_assert(!is_bool<T>);
		if constexpr (is_custom<T>) { typename T::internal_value_type y; read_int(y); x = y; }
		else if constexpr (is_default<T>) {
			if constexpr (is_string<T>) { read_string(x); }
			else if constexpr (is_char<T>) { read_char(x); }
			else if constexpr (std::is_integral_v<T>) { read_int(x); }
		} else if constexpr (is_iterable<T>) { for (auto& y : x) operator>>(y); }
		else if constexpr (is_applyable<T>) { 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>) { std::string y; read_string(y); x = y; }
		else if constexpr (has_constructor_ll<T>) { 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_IO_endl<T> or is_IO_flush<T> or is_custom<T> or is_default<T> or is_iterable<T> or is_applyable<T> or std::is_floating_point_v<T> or is_int128<T> or has_val<T> or has_to_string<T> or has_str<T> or is_constructible_istreambuf_iterator<T>);
		if constexpr (is_IO_endl<T>) { fastio_endl(); }
		else if constexpr (is_IO_flush<T>) { fastio_flush(); }
		else if constexpr (is_custom<T>) { write_int(x.get()); }
		else if constexpr (is_default<T>) {
			if constexpr (is_bool<T>) { write_bool(x); }
			else if constexpr (is_string<T>) { write_string(x); }
			else if constexpr (is_char<T>) { write_char(x); }
			else if constexpr (std::is_integral_v<T>) { write_int(x); }
		} else if constexpr (is_iterable<T>) {
			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>) {
			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 (is_int128<T>) { write_string(to_string(x)); }
		else if constexpr (has_val<T>) { write_int(x.val()); }
		else if constexpr (has_to_string<T>) { write_string(x.to_string()); }
		else if constexpr (has_str<T>) { write_string(x.str()); }
		else if constexpr (is_constructible_istreambuf_iterator<T>) { std::istreambuf_iterator<char> it(x), last; std::for_each(it, last, [&](char c) { write_char(c); }); }
		return *this;
	}
	IO* tie(std::nullptr_t) { return this; }
	void sync_with_stdio(bool b) { is_sync_with_stdio = b; }
	void setf(...) {}
	void precision(int n) { precision_value = n; }
	void set_infile(FILE* f) { infile = f; }
	void set_outfile(FILE* f) { outfile = f; }
	void unset_infile() { infile = stdin; }
	void unset_outfile() { outfile = stdout; }
	void set_instream(std::istream* s) { instream = s; }
	void set_outstream(std::ostream* s) { outstream = s; }
	void unset_instream() { instream = nullptr; }
	void unset_outstream() { outstream = nullptr; }
	IO& fastio_endl() { operator<<('\n'); if (is_sync_with_stdio) flush(); return *this; }
	IO& fastio_flush() { flush(); return *this; }
};
} // namespace fastio_impl
#ifdef USE_FASTIO
	namespace std {
		fastio_impl::IO fastio;
		fastio_impl::IO_endl fastio_endl;
		fastio_impl::IO_flush fastio_flush;
	}
	#define cin fastio
	#define cout fastio
	#define endl fastio_endl
	#define flush fastio_flush
#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
	#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::vector<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::vector<std::dvector<T>>& vv) { s << "\\\n"; for (std::size_t i = 0; i < vv.size(); ++i){ s << vv[i] << (i + 1 == vv.size() ? "" : "\n"); } return s; }
		template <typename T, std::size_t N, typename std::enable_if_t<!std::is_same_v<T, char> && !std::is_same_v<T, const 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::is_same_v<T, const 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] << (i + 1 == N ? "" : "\n"); } return s; }
		std::ostream& operator<<(std::ostream& s, const std::vector<std::string>& v) { s << "\\\n"; for (std::size_t i = 0; i < v.size(); ++i){ s << v[i] << (i + 1 == v.size() ? "" : "\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)
	#define debugr(...) do { std::cerr << "\033[31m"; debug(__VA_ARGS__); std::cerr << "\033[0m"; } while (false)
	#define debugy(...) do { std::cerr << "\033[33m"; debug(__VA_ARGS__); std::cerr << "\033[0m"; } 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)
	#define debugr(...) do {} while (false)
	#define debugy(...) do {} while (false)
	constexpr inline long long prodlocal([[maybe_unused]] long long prod, [[maybe_unused]] long long local) { return prod; }
#endif
//#define int long long
using ll = long long;
using ll128 = __int128_t;
//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 std::array<int, 4> dx = {0, -1, 0, 1}; //['R', 'U', 'L', 'D']
constexpr std::array<int, 4> dy = {1, 0, -1, 0};
constexpr std::array<int, 8> dx8 = {0, -1, -1, -1, 0, 1, 1, 1};
constexpr std::array<int, 8> dy8 = {1, 1, 0, -1, -1, -1, 0, 1};
#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)
template <typename T> using priority_queue_rev = std::priority_queue<T, std::vector<T>, std::greater<T>>;
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> inline void pv(const T& v) { auto itbegin = std::begin(v), itend = std::end(v); for (auto it = itbegin; it != itend; std::advance(it, 1)) cout << (it == itbegin ? "" : " ") << *it; cout << NEWLINE; }
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 int sz(const T& v) { return std::size(v); }
template <typename T> inline T floor(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }
template <typename T> inline T ceil(T a, T b) { return floor(a + b - 1, b); }
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(std::rbegin(sizes), std::rend(sizes)); 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 <typename T = ll> std::pair<T, T> nibutan(T left, T right, const auto&& f) { while (std::abs(right - left) > 1) { T mid = left + (right - left) / 2; (f(mid) ? left : right) = mid; } return {left, right}; }
template <typename T = double> std::pair<T, T> nibutan_double(T threshold, T left, T right, const auto&& f) { int c = std::log2(std::abs(right - left) / threshold) + 3; while (std::abs(right - left) > threshold && c--) { T mid = left + (right - left) / 2; (f(mid) ? left : right) = mid; } return {left, right}; }
namespace std {
	template <typename T, typename std::enable_if_t<std::is_same_v<T, __int128_t> || std::is_same_v<T, __uint128_t>, std::nullptr_t> = nullptr> std::string to_string(T n) { if (n == 0) return "0"; bool minus = n < 0; if (minus) n = -n; std::string r; while (n > 0) r += '0' + n % 10, n /= 10; if (minus) r += '-'; reverse(r.begin(), r.end()); return r; }
	template <typename T, typename std::enable_if_t<std::is_same_v<T, __int128_t> || std::is_same_v<T, __uint128_t>, std::nullptr_t> = nullptr> std::ostream& operator<<(std::ostream& s, const T& n) { return s << to_string(n); }
}
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 iterator_category = Category;
	};
	class zip_iterator : public basic_iterator<std::forward_iterator_tag, std::tuple<decltype(*std::declval<T>().begin())...>> {
	public:
		int 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...}; }
#if __has_include(<ext/pb_ds/assoc_container.hpp>)
#include <bits/extc++.h>
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);
	}
	template <typename T1, typename T2> 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 C, typename T = std::decay_t<decltype(*begin(std::declval<C>()))>> std::size_t operator()(const C& container) const {
		std::size_t h = container.size(); for (auto&& k : container) h ^= operator()(k) + 0x9e3779b9 + (h << 6) + (h >> 2); return h;
	}
};
template <typename Key, typename Mapped, typename Hash = custom_hash> using fmapbase = __gnu_pbds::gp_hash_table<Key, Mapped, Hash, equal_to<Key>, __gnu_pbds::direct_mask_range_hashing<>, __gnu_pbds::linear_probe_fn<>, __gnu_pbds::hash_standard_resize_policy<__gnu_pbds::hash_exponential_size_policy<>, __gnu_pbds::hash_load_check_resize_trigger<>, true>>;
template <typename Key, typename Mapped, typename Hash = custom_hash> class fmap : public fmapbase <Key, Mapped, Hash> {
public:
	using fmapbase<Key, Mapped, Hash>::gp_hash_table;
	template <typename Mapped_ = Mapped, typename std::enable_if_t<std::is_same_v<Mapped_, __gnu_pbds::null_type>, std::nullptr_t> = nullptr> fmap(std::initializer_list<Key> il) : fmapbase<Key, Mapped, Hash>(il.begin(), il.end()) {}
	template <typename Mapped_ = Mapped, typename std::enable_if_t<!std::is_same_v<Mapped_, __gnu_pbds::null_type>, std::nullptr_t> = nullptr> fmap(std::initializer_list<std::pair<Key, Mapped>> il) : fmapbase<Key, Mapped, Hash>(il.begin(), il.end()) {}
	void reserve(std::size_t n) {
		fmapbase<Key, Mapped, Hash>::resize(n);
	}
	template <typename T> int count(const T& x) const {
		return fmapbase<Key, Mapped, Hash>::find(x) != fmapbase<Key, Mapped, Hash>::end();
	}
};
template <typename Key, typename Hash = custom_hash> using fset = fmap<Key, __gnu_pbds::null_type, Hash>;
#ifdef LOCAL_TEST
template <typename Key, typename Mapped, typename Hash> std::ostream& operator<<(std::ostream& s, const fmapbase<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; }
template <typename Key, typename Hash> std::ostream& operator<<(std::ostream& s, const fmapbase<Key, __gnu_pbds::null_type, Hash>& se) { s << "{ "; for (auto it = se.begin(); it != se.end(); ++it){ s << *it << "\t"; } s << "}"; return s; }
#endif
#else
template <typename Key, typename Mapped> using fmap = std::unordered_map<Key, Mapped>;
template <typename Key> using fset = std::unordered_set<Key>;
#endif

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

//[lib].cpp
//https://hitonanode.github.io/cplib-cpp/other_algorithms/binary_lifting.hpp
// Binary lifting (Doubling) on functional graphs
template <class S, class Op> class binary_lifting {
	int n = 0;
	std::vector<std::vector<int>> _nexts;
	std::vector<std::vector<S>> _prods;
	Op op;

	void build_next() {
		std::vector<int> _next(n);
		std::vector<S> _prod(n);

		for (int i = 0; i < n; ++i) {
			if (int j = _nexts.back().at(i); isin(j)) {
				_next.at(i) = _nexts.back().at(j);
				_prod.at(i) = op(_prods.back().at(i), _prods.back().at(j));
			} else {
				_next.at(i) = j;
				_prod.at(i) = _prods.back().at(i);
			}
		}
		_nexts.emplace_back(std::move(_next));
		_prods.emplace_back(std::move(_prod));
	}

	inline bool isin(int i) const noexcept { return 0 <= i and i < n; }

	// (up to) 2^d steps from `s`
	// Complexity: O(d) (Already precalculated) / O(nd) (First time)
	// s からスタートして2^d回移動したとき、どこにいるかを返す
	int pow_next(int s, int d) {
		assert(isin(s));
		while (int(_nexts.size()) <= d) build_next();
		return _nexts.at(d).at(s);
	}

	// Product of (up to) 2^d elements from `s`
	// s からスタートして2^d回移動したとき、重みw[i]をopで集約した総積を返す
	const S &pow_prod(int s, int d) {
		assert(isin(s));
		while (int(_nexts.size()) <= d) build_next();
		return _prods.at(d).at(s);
	}

public:
	binary_lifting() = default;
	//i -> g[i] へ重み w[i] の辺が張られているfunctional graph
	//g[i] の値は 0 未満や n 以上でも構わない
	template <typename Int>
	binary_lifting(const std::vector<Int> &g, const std::vector<S> &w, const Op& op_)
		: n(g.size()), _nexts(1, {g.begin(), g.end()}), _prods(1, w), op(op_) {
		assert(g.size() == w.size());
	}

	// (up to) k steps from `s`
	// s からスタートしてk回移動したとき、どこにいるかを返す
	// 途中で[0, n)の範囲外に出た場合は、出た先の値を返す
	template <class Int> int kth_next(int s, Int k) {
		for (int d = 0; k > 0 and isin(s); ++d, k >>= 1) {
			if (k & 1) s = pow_next(s, d);
		}
		return s;
	}

	// Product of (up to) `len` elements from `s`
	// sからスタートしてlen-1回移動して訪れた頂点(最初のs含む)がlen個になったとき、訪れた頂点群の重みw[i]をopで集約した総積を返す
	template <class Int> S kth_prod(int s, Int len) {
		assert(isin(s));
		assert(len > 0);
		int d = 0;
		while (!(len & 1)) ++d, len /= 2;

		S ret = pow_prod(s, d);
		s = pow_next(s, d);
		for (++d, len /= 2; len and isin(s); ++d, len /= 2) {
			if (len & 1) {
				ret = op(ret, pow_prod(s, d));
				s = pow_next(s, d);
			}
		}
		return ret;
	}

	// `start` から出発して「`left_goal` 以下または `right_goal` 以上」に到達するまでのステップ数
	// 到達できない場合は -1 を返す．
	// 単調性が必要
	int distance_monotone(int start, int left_goal, int right_goal) {
		assert(isin(start));
		if (start <= left_goal or right_goal <= start) return 0;

		int d = 0;
		while (left_goal < pow_next(start, d) and pow_next(start, d) < right_goal) {
			if ((1 << d) >= n) return -1;
			++d;
		}

		int ret = 0, cur = start;
		for (--d; d >= 0; --d) {
			if (int nxt = pow_next(cur, d); left_goal < nxt and nxt < right_goal) {
				ret += 1 << d, cur = nxt;
			}
		}
		return ret + 1;
	}

	// f(prod(s, len)) が true と評価される 2^maxd 以下の最大の len を返す．
	// f(prod(s, len)) の単調性が必要．
	template <class F> long long max_length(const int s, const F& f, const int maxd = 60) {
		assert(isin(s));
		int d = 0;
		while (d <= maxd and f(pow_prod(s, d))) {
			if (!isin(pow_next(s, d))) return 1LL << maxd;
			++d;
		}
		if (d > maxd) return 1LL << maxd;
		--d;
		int cur = pow_next(s, d);
		long long len = 1LL << d;
		S p = pow_prod(s, d);

		for (int e = d - 1; e >= 0; --e) {
			if (S nextp = op(p, pow_prod(cur, e)); f(nextp)) {
				std::swap(p, nextp);
				cur = pow_next(cur, e);
				len += 1LL << e;
			}
		}
		return len;
	}
};

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

//https://yukicoder.me/problems/no/1013
void solve() {
	ll N, K;
	cin >> N >> K;
	vector<ll> a(N);
	rep(i, N) cin >> a[i];

	using weighttype = ll;
	vector<ll> movev(N); //iの次の行き先をmovev[i]に定める
	vector<weighttype> weightv(N); //iに到着したときの重みweightv[i]
	rep(i, N) {
		movev[i] = (a[i] + i) % N;
		weightv[i] = a[i];
	}
	// 重みの集約関数
	auto fF = [&](const weighttype& x, const weighttype& y) {
		return x + y;
	};
	binary_lifting<weighttype, decltype(fF)> bl(movev, weightv, fF);


	rep(i, N) {
		//kth_prod(i,k)は頂点iからk-1回移動
		//kth_next(i,k)は頂点iからk回移動
		//で移動回数が違うので注意！！
		ll ans = bl.kth_prod(i, K+1);
		ll t = bl.kth_next(i, K);
		ans -= a[t];
		ans += i + 1;
		debug(ans, t);
		p(ans);
	}
}

//https://yukicoder.me/problems/no/2242
void yuki2242() {
	ll N;
	cin >> N;
	vector<ll> H(N), T(N);
	rep(i, N) cin >> H[i];
	rep(i, N) cin >> T[i];

	vector<array<ll, 3>> v(N);
	rep(i, N) v[i] = {H[i], T[i], i};
	sort(all(v));
	vector<ll> idxs(N);
	rep(i, N) idxs[v[i][2]] = i;

	using weighttype = ll;
	vector<ll> movev(N+1); //iの次の行き先をmovev[i]に定める
	vector<weighttype> weightv(N+1); //iに到着したときの重みweightv[i]
	ll maxT = -INF;
	rep(i, N) {
		chmax(maxT, v[i][1]);
		using rangetype = ll;
		auto [left, right] = nibutan<rangetype>(-1, N, [&](rangetype val) -> bool {
			return v[val][0] <= maxT;
		});
		movev[i+1] = left+1;
	}
	// 重みの集約関数
	auto fF = [&](const weighttype& x, const weighttype& y) {
		return x + y;
	};
	binary_lifting<weighttype, decltype(fF)> bl(movev, weightv, fF);


	ll Q;
	cin >> Q;
	while (Q--) {
		ll a, b;
		cin >> a >> b;
		a--, b--;
		if (T[a] >= H[b]) p(1);
		else {
			ll aa = idxs[a], bb = idxs[b];
			using rangetype = ll;
			auto [left, right] = nibutan<rangetype>(-1, N, [&](rangetype val) -> bool {
				return v[val][0] <= T[a];
			});
			ll ans = bl.distance_monotone(left+1, -1, bb+1);
			if (ans != -1) ans++;
			p(ans);
		}
	}
}

//https://atcoder.jp/contests/abc179/tasks/abc179_e
void abc179_e() {
	ll N, X, M;
	cin >> N >> X >> M;

	using weighttype = ll;
	vector<ll> movev(M); //iの次の行き先をmovev[i]に定める
	vector<weighttype> weightv(M); //iに到着したときの重みweightv[i]
	rep(i, M) {
		ll nexti = (i * i) % M;
		movev[i] = nexti;
		weightv[i] = i;
	}
	//重みの集約関数
	auto fF = [&](const weighttype& x, const weighttype& y) {
		return x + y;
	};
	binary_lifting<weighttype, decltype(fF)> bl(movev, weightv, fF);

	ll ans = bl.kth_prod(X, N);
	p(ans);
}

//https://atcoder.jp/contests/abc167/tasks/abc167_d
void abc167_d() {
	ll N, K;
	cin >> N >> K;
	vector<ll> a(N);
	rep(i, N) cin >> a[i], a[i]--;


	using weighttype = ll;
	vector<ll> movev = a;
	vector<weighttype> weightv(N);
	auto fF = [&](const weighttype& x, const weighttype& y) {
		return x + y;
	};
	binary_lifting<weighttype, decltype(fF)> bl(movev, weightv, fF);

	ll ans = bl.kth_next(0, K);
	p(ans + 1);
}

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