#include <bits/stdc++.h>

namespace MyLib  // 自作ライブラリ
{
	template<typename T, class Picker, T default_value> class LiteralSegmentTree
	{
	protected:
		std::vector<std::vector<T>> containers;

	public:
		constexpr LiteralSegmentTree(const std::vector<T>& initializer)
		{
			containers.clear();

			if (initializer.size() == 0) return;
			else if (initializer.size() == 1) { containers.emplace_back(1, initializer[0]); return; }

			uint_fast32_t l = 0, r = 30;
			while (l + 1 < r)
			{
				const auto c = (l + r) >> 1;
				if (((uint_fast32_t)1 << c) < initializer.size())
					l = c;
				else
					r = c;
			}

			containers.emplace_back((uint_fast32_t)1 << r);

			uint_fast32_t i;
			for (i = 0; i != initializer.size(); ++i)
				containers[0][i] = initializer[i];
			for (; i != ((uint_fast32_t)1 << r); ++i)
				containers[0][i] = default_value;

			for (--r; r != 0; --r)
			{
				containers.emplace_back((uint_fast32_t)1 << r);
				for (i = 0; i != ((uint_fast32_t)1 << r); ++i)
					containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]);
			}
			containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1]));
		}

		constexpr LiteralSegmentTree(std::vector<T>&& initializer)
		{
			containers.clear();

			if (initializer.size() == 0) return;

			uint_fast32_t l = 0, r = 30;
			while (l + 1 < r)
			{
				const auto c = (l + r) >> 1;
				if (((uint_fast32_t)1 << c) < initializer.size())
					l = c;
				else
					r = c;
			}

			containers.emplace_back(std::move(initializer));
			containers[0].resize((uint_fast32_t)1 << r, default_value);

			uint_fast32_t i;
			for (--r; r != 0; --r)
			{
				containers.emplace_back((uint_fast32_t)1 << r);
				for (i = 0; i != ((uint_fast32_t)1 << r); ++i)
					containers[containers.size() - 1][i] = Picker()(containers[containers.size() - 2][i << 1], containers[containers.size() - 2][(i << 1) | 1]);
			}
			containers.emplace_back(1, Picker()(containers[containers.size() - 1][0], containers[containers.size() - 1][1]));
		}

		constexpr LiteralSegmentTree(const uint_fast32_t n) : LiteralSegmentTree<T, Picker, default_value>(std::vector<T>(n, default_value)) { }
		constexpr LiteralSegmentTree(const uint_fast32_t n, const T initial_value) : LiteralSegmentTree<T, Picker, default_value>(std::vector<T>(n, initial_value)) { }

		constexpr T operator[](uint_fast32_t index) const noexcept { return containers[0][index]; }

		constexpr uint_fast32_t size() const noexcept { return containers[0].size(); }
		constexpr uint_fast32_t layer() const noexcept { return containers.size(); }

		constexpr T update(uint_fast32_t index, const T value) noexcept
		{
			containers[0][index] = value;

			index >>= 1;
			for (uint_fast32_t i = 1; i != containers.size(); ++i, index >>= 1)
				containers[i][index] = Picker()(containers[i - 1][index << 1], containers[i - 1][(index << 1) | 1]);

			return value;
		}

		constexpr T range_pick_up(uint_fast32_t first_index, uint_fast32_t end_index) const noexcept
		{
			if (containers.size() == 0 || end_index > containers[0].size()) return default_value;

			T ret_l = default_value, ret_r = default_value;
			for (uint_fast32_t cur_layer = 0; first_index < end_index; first_index >>= 1, end_index >>= 1, ++cur_layer)
			{
				if (first_index & 1)
					ret_l = Picker()(ret_l, containers[cur_layer][first_index]), ++first_index;
				if (end_index & 1)
					ret_r = Picker()(containers[cur_layer][end_index - 1], ret_r);
			}

			return Picker()(ret_l, ret_r);
		}
	};

	template<typename T, class Mapping, class Composition, class Picker, T default_value>
	class LiteralLazySegmentTree : public LiteralSegmentTree<T, Picker, default_value>
	{
	protected:
		std::vector<std::vector<std::pair<bool, T>>> unevaluated;

		constexpr void convey_evaluation(const uint_fast32_t cur_layer, const uint_fast32_t cur_index) noexcept
		{
			if (unevaluated[cur_layer - 1][cur_index << 1].first)
				unevaluated[cur_layer - 1][cur_index << 1].second = Composition()(unevaluated[cur_layer - 1][cur_index << 1].second, unevaluated[cur_layer][cur_index].second);
			else
				unevaluated[cur_layer - 1][cur_index << 1] = { true, unevaluated[cur_layer][cur_index].second };

			if (unevaluated[cur_layer - 1][(cur_index << 1) | 1].first)
				unevaluated[cur_layer - 1][(cur_index << 1) | 1].second = Composition()(unevaluated[cur_layer - 1][(cur_index << 1) | 1].second, unevaluated[cur_layer][cur_index].second);
			else
				unevaluated[cur_layer - 1][(cur_index << 1) | 1] = { true, unevaluated[cur_layer][cur_index].second };

			unevaluated[cur_layer][cur_index] = { false, default_value };
		}

		constexpr void execute_evaluation_above(const uint_fast32_t first_index, const uint_fast32_t end_index) noexcept
		{
			for (uint_fast32_t cur_layer = unevaluated.size() - 1; (first_index & (((uint_fast32_t)1 << cur_layer) - 1)) != 0; --cur_layer)
				if (unevaluated[cur_layer][first_index >> cur_layer].first)
				{
					this->containers[cur_layer][first_index >> cur_layer] = Mapping()(this->containers[cur_layer][first_index >> cur_layer], unevaluated[cur_layer][first_index >> cur_layer].second, (uint_fast32_t)1 << cur_layer);
					convey_evaluation(cur_layer, first_index >> cur_layer);
				}

			for (uint_fast32_t cur_layer = unevaluated.size() - 1; (end_index & (((uint_fast32_t)1 << cur_layer) - 1)) != 0; --cur_layer)
				if (unevaluated[cur_layer][(end_index - 1) >> cur_layer].first)
				{
					this->containers[cur_layer][(end_index - 1) >> cur_layer] = Mapping()(this->containers[cur_layer][(end_index - 1) >> cur_layer], unevaluated[cur_layer][(end_index - 1) >> cur_layer].second, (uint_fast32_t)1 << cur_layer);
					convey_evaluation(cur_layer, (end_index - 1) >> cur_layer);
				}
		}

	public:
		constexpr LiteralLazySegmentTree(const std::vector<T>& initializer) : LiteralSegmentTree<T, Picker, default_value>(initializer)
		{
			unevaluated.clear();
			unevaluated.reserve(this->containers.size());

			if (this->containers.size() == 0) return;
			uint_fast32_t L = this->containers[0].size();
			unevaluated.emplace_back(L, std::pair<bool, T>{ false, default_value });

			for (L >>= 1; L != 0; L >>= 1)
				unevaluated.emplace_back(L, std::pair<bool, T>{ false, default_value });
		}

		constexpr LiteralLazySegmentTree(std::vector<T>&& initializer) : LiteralSegmentTree<T, Picker, default_value>(std::move(initializer))
		{
			unevaluated.clear();
			unevaluated.reserve(this->containers.size());

			if (this->containers.size() == 0) return;
			uint_fast32_t L = this->containers[0].size();
			unevaluated.emplace_back(L, std::pair<bool, T>{ false, default_value });

			for (L >>= 1; L != 0; L >>= 1)
				unevaluated.emplace_back(L, std::pair<bool, T>{ false, default_value });
		}

		template<typename... Args> constexpr LiteralLazySegmentTree(const Args... args) : LiteralSegmentTree<T, Picker, default_value>(std::forward<Args>(args)...)
		{
			unevaluated.clear();
			unevaluated.reserve(this->containers.size());

			if (this->containers.size() == 0) return;
			uint_fast32_t L = this->containers[0].size();
			unevaluated.emplace_back(L, std::pair<bool, T>{ false, default_value });

			for (L >>= 1; L != 0; L >>= 1)
				unevaluated.emplace_back(L, std::pair<bool, T>{ false, default_value });
		}

		constexpr T operator[](uint_fast32_t index) noexcept { return range_pick_up(index, index + 1); }

		constexpr void update(const uint_fast32_t first_index, const uint_fast32_t end_index, const T value) noexcept
		{
			if (first_index >= end_index) return;

			execute_evaluation_above(first_index, end_index);
			uint_fast32_t cur_layer, first_index_temp = first_index, end_index_temp = end_index;
			for (cur_layer = 0; first_index_temp != end_index_temp; ++cur_layer, first_index_temp >>= 1, end_index_temp >>= 1)
			{
				if ((first_index_temp << cur_layer) != first_index)
				{
					if (unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].first)
					{
						this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
						if (cur_layer != 1) convey_evaluation(cur_layer - 1, (first_index >> (cur_layer - 1)) ^ 1);
						else unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = { false, default_value };
					}
					this->containers[cur_layer][first_index >> cur_layer] = Picker()(this->containers[cur_layer - 1][first_index >> (cur_layer - 1)], this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1]);
				}
				if ((end_index_temp << cur_layer) != end_index)
				{
					if (unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].first)
					{
						this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
						if (cur_layer != 1) convey_evaluation(cur_layer - 1, ((end_index - 1) >> (cur_layer - 1)) ^ 1);
						else unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = { false, default_value };
					}
					this->containers[cur_layer][(end_index - 1) >> cur_layer] = Picker()(this->containers[cur_layer - 1][(end_index - 1) >> (cur_layer - 1)], this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1]);
				}

				if (first_index_temp & 1)
				{
					if (unevaluated[cur_layer][first_index_temp].first)
						unevaluated[cur_layer][first_index_temp].second = Composition()(unevaluated[cur_layer][first_index_temp].second, value);
					else
						unevaluated[cur_layer][first_index_temp] = { true, value };

					this->containers[cur_layer][first_index_temp] = Mapping()(this->containers[cur_layer][first_index_temp], unevaluated[cur_layer][first_index_temp].second, (uint_fast32_t)1 << cur_layer);
					if (cur_layer != 0) convey_evaluation(cur_layer, first_index_temp);
					else unevaluated[cur_layer][first_index_temp] = { false, default_value };

					++first_index_temp;
				}
				if (end_index_temp & 1)
				{
					if (unevaluated[cur_layer][end_index_temp - 1].first)
						unevaluated[cur_layer][end_index_temp - 1].second = Composition()(unevaluated[cur_layer][end_index_temp - 1].second, value);
					else
						unevaluated[cur_layer][end_index_temp - 1] = { true, value };

					this->containers[cur_layer][end_index_temp - 1] = Mapping()(this->containers[cur_layer][end_index_temp - 1], unevaluated[cur_layer][end_index_temp - 1].second, (uint_fast32_t)1 << cur_layer);
					if (cur_layer != 0) convey_evaluation(cur_layer, end_index_temp - 1);
					else unevaluated[cur_layer][end_index_temp - 1] = { false, default_value };

					//--end_index_temp;
				}
			}

			for (; cur_layer != unevaluated.size(); ++cur_layer, first_index_temp >>= 1, end_index_temp >>= 1)
			{
				if ((first_index_temp << cur_layer) != first_index)
				{
					if (unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].first)
					{
						this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
						if (cur_layer != 1) convey_evaluation(cur_layer - 1, (first_index >> (cur_layer - 1)) ^ 1);
						else unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = { false, default_value };
					}
					this->containers[cur_layer][first_index >> cur_layer] = Picker()(this->containers[cur_layer - 1][first_index >> (cur_layer - 1)], this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1]);
				}
				if ((end_index_temp << cur_layer) != end_index)
				{
					if (unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].first)
					{
						this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
						if (cur_layer != 1) convey_evaluation(cur_layer - 1, ((end_index - 1) >> (cur_layer - 1)) ^ 1);
						else unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = { false, default_value };
					}
					this->containers[cur_layer][(end_index - 1) >> cur_layer] = Picker()(this->containers[cur_layer - 1][(end_index - 1) >> (cur_layer - 1)], this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1]);
				}
			}
		}

		constexpr T range_pick_up(const uint_fast32_t first_index, const uint_fast32_t end_index) noexcept
		{
			if (first_index >= end_index) return default_value;

			execute_evaluation_above(first_index, end_index);
			T ret_l = default_value, ret_r = default_value;
			uint_fast32_t cur_layer, first_index_temp = first_index, end_index_temp = end_index;
			for (cur_layer = 0; first_index_temp != end_index_temp; ++cur_layer, first_index_temp >>= 1, end_index_temp >>= 1)
			{
				if ((first_index_temp << cur_layer) != first_index)
				{
					if (unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].first)
					{
						this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
						if (cur_layer != 1) convey_evaluation(cur_layer - 1, (first_index >> (cur_layer - 1)) ^ 1);
						else unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = { false, default_value };
					}
					this->containers[cur_layer][first_index >> cur_layer] = Picker()(this->containers[cur_layer - 1][first_index >> (cur_layer - 1)], this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1]);
				}
				if ((end_index_temp << cur_layer) != end_index)
				{
					if (unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].first)
					{
						this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
						if (cur_layer != 1) convey_evaluation(cur_layer - 1, ((end_index - 1) >> (cur_layer - 1)) ^ 1);
						else unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = { false, default_value };
					}
					this->containers[cur_layer][(end_index - 1) >> cur_layer] = Picker()(this->containers[cur_layer - 1][(end_index - 1) >> (cur_layer - 1)], this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1]);
				}

				if (first_index_temp & 1)
				{
					if (unevaluated[cur_layer][first_index_temp].first)
					{
						this->containers[cur_layer][first_index_temp] = Mapping()(this->containers[cur_layer][first_index_temp], unevaluated[cur_layer][first_index_temp].second, (uint_fast32_t)1 << cur_layer);
						if (cur_layer != 0) convey_evaluation(cur_layer, first_index_temp);
						else unevaluated[cur_layer][first_index_temp] = { false, default_value };
					}
					ret_l = Picker()(ret_l, this->containers[cur_layer][first_index_temp]);
					++first_index_temp;
				}
				if (end_index_temp & 1)
				{
					if (unevaluated[cur_layer][end_index_temp - 1].first)
					{
						this->containers[cur_layer][end_index_temp - 1] = Mapping()(this->containers[cur_layer][end_index_temp - 1], unevaluated[cur_layer][end_index_temp - 1].second, (uint_fast32_t)1 << cur_layer);
						if (cur_layer != 0) convey_evaluation(cur_layer, end_index_temp - 1);
						else unevaluated[cur_layer][end_index_temp - 1] = { false, default_value };
					}
					ret_r = Picker()(this->containers[cur_layer][end_index_temp - 1], ret_r);
					//--end_index_temp;
				}
			}

			for (; cur_layer != unevaluated.size(); ++cur_layer, first_index_temp >>= 1, end_index_temp >>= 1)
			{
				if ((first_index_temp << cur_layer) != first_index)
				{
					if (unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].first)
					{
						this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
						if (cur_layer != 1) convey_evaluation(cur_layer - 1, (first_index >> (cur_layer - 1)) ^ 1);
						else unevaluated[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1] = { false, default_value };
					}
					this->containers[cur_layer][first_index >> cur_layer] = Picker()(this->containers[cur_layer - 1][first_index >> (cur_layer - 1)], this->containers[cur_layer - 1][(first_index >> (cur_layer - 1)) ^ 1]);
				}
				if ((end_index_temp << cur_layer) != end_index)
				{
					if (unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].first)
					{
						this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = Mapping()(this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1], unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1].second, (uint_fast32_t)1 << (cur_layer - 1));
						if (cur_layer != 1) convey_evaluation(cur_layer - 1, ((end_index - 1) >> (cur_layer - 1)) ^ 1);
						else unevaluated[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1] = { false, default_value };
					}
					this->containers[cur_layer][(end_index - 1) >> cur_layer] = Picker()(this->containers[cur_layer - 1][(end_index - 1) >> (cur_layer - 1)], this->containers[cur_layer - 1][((end_index - 1) >> (cur_layer - 1)) ^ 1]);
				}
			}

			return Picker()(ret_l, ret_r);
		}
	};

	template<typename T> using DefaultMaxPicker = decltype([](const T a, const T b) { return std::max<T>(a, b); });

	template<typename T, class Mapping, class Composition, class MaxPicker, T default_value = std::numeric_limits<T>::lowest()>
	class MaxLazySegmentTree : public LiteralLazySegmentTree<T, Mapping, Composition, MaxPicker, default_value>
	{
	public:
		constexpr MaxLazySegmentTree(const std::vector<T>& initializer) : LiteralLazySegmentTree<T, Mapping, Composition, MaxPicker, default_value>(initializer) { }
		constexpr MaxLazySegmentTree(std::vector<T>&& initializer) : LiteralLazySegmentTree<T, Mapping, Composition, MaxPicker, default_value>(std::move(initializer)) { }
		template<typename... Args> constexpr MaxLazySegmentTree(Args... args) : LiteralLazySegmentTree<T, Mapping, Composition, MaxPicker, default_value>(std::forward<Args>(args)...) { }

		constexpr uint_fast32_t leftest_above(const uint_fast32_t first, const uint_fast32_t last, const T limit) noexcept
		{
			if (this->containers.size() == 0) return 0;
			if (first >= last) return this->containers[0].size();

			uint_fast32_t cur_layer, cur_index;

			uint_fast32_t candidate_layer = this->containers.size(), candidate_index;
			uint_fast32_t first_temp = first, last_temp = last;
			LiteralLazySegmentTree<T, Mapping, Composition, MaxPicker, default_value>::execute_evaluation_above(first, last);
			if (first & 1)
			{
				if (this->unevaluated[0][first].first)
				{
					this->containers[0][first] = Mapping()(this->containers[0][first], this->unevaluated[0][first].second, 1);
					this->unevaluated[0][first] = { false, default_value };
				}

				if (this->containers[0][first] >= limit)
					return first;
				++first_temp;
			}
			if (last & 1)
			{
				if (this->unevaluated[0][last - 1].first)
				{
					this->containers[0][last - 1] = Mapping()(this->containers[0][last - 1], this->unevaluated[0][last - 1].second, 1);
					this->unevaluated[0][last - 1] = { false, default_value };
				}

				if (this->containers[0][last - 1] >= limit)
					candidate_layer = 0, candidate_index = last - 1;
				//--last_temp;
			}

			for (cur_layer = 1, first_temp >>= 1, last_temp >>= 1; first_temp != last_temp; ++cur_layer, first_temp >>= 1, last_temp >>= 1)
			{
				if (first_temp & 1)
				{
					if (this->unevaluated[cur_layer][first_temp].first)
					{
						this->containers[cur_layer][first_temp] = Mapping()(this->containers[cur_layer][first_temp], this->unevaluated[cur_layer][first_temp].second, (uint_fast32_t)1 << cur_layer);
						LiteralLazySegmentTree<T, Mapping, Composition, MaxPicker, default_value>::convey_evaluation(cur_layer, first_temp);
					}

					if (this->containers[cur_layer][first_temp] >= limit)
						break;
					++first_temp;
				}
				if (last_temp & 1)
				{
					if (this->unevaluated[cur_layer][last_temp - 1].first)
					{
						this->containers[cur_layer][last_temp - 1] = Mapping()(this->containers[cur_layer][last_temp - 1], this->unevaluated[cur_layer][last_temp - 1].second, (uint_fast32_t)1 << cur_layer);
						LiteralLazySegmentTree<T, Mapping, Composition, MaxPicker, default_value>::convey_evaluation(cur_layer, last_temp - 1);
					}

					if (this->containers[cur_layer][last_temp - 1] >= limit)
						candidate_layer = cur_layer, candidate_index = last_temp - 1;
					//--last_temp;
				}
			}

			if (first_temp != last_temp) cur_index = first_temp;
			else if (candidate_layer == this->containers.size()) return this->containers[0].size();
			else cur_layer = candidate_layer, cur_index = candidate_index;

			while (cur_layer > 1)
			{
				--cur_layer, cur_index <<= 1;
				if (this->unevaluated[cur_layer][cur_index].first)
				{
					this->containers[cur_layer][cur_index] = Mapping()(this->containers[cur_layer][cur_index], this->unevaluated[cur_layer][cur_index].second, (uint_fast32_t)1 << cur_layer);
					LiteralLazySegmentTree<T, Mapping, Composition, MaxPicker, default_value>::convey_evaluation(cur_layer, cur_index);
				}

				if (this->containers[cur_layer][cur_index] < limit)
				{
					cur_index |= 1;
					if (this->unevaluated[cur_layer][cur_index].first)
					{
						this->containers[cur_layer][cur_index] = Mapping()(this->containers[cur_layer][cur_index], this->unevaluated[cur_layer][cur_index].second, (uint_fast32_t)1 << cur_layer);
						LiteralLazySegmentTree<T, Mapping, Composition, MaxPicker, default_value>::convey_evaluation(cur_layer, cur_index);
					}
				}
			}

			if (cur_layer == 1)
			{
				cur_index <<= 1;
				if (this->unevaluated[0][cur_index].first)
				{
					this->containers[0][cur_index] = Mapping()(this->containers[0][cur_index], this->unevaluated[0][cur_index].second, 1);
					this->unevaluated[0][cur_index] = { false, default_value };
				}

				if (this->containers[0][cur_index] < limit)
				{
					cur_index |= 1;
					if (this->unevaluated[0][cur_index].first)
					{
						this->containers[0][cur_index] = Mapping()(this->containers[0][cur_index], this->unevaluated[0][cur_index].second, 1);
						this->unevaluated[0][cur_index] = { false, default_value };
					}
				}
			}

			return cur_index;
		}

		constexpr uint_fast32_t rightest_above(const uint_fast32_t first, const uint_fast32_t last, const T limit) noexcept
		{
			if (this->containers.size() == 0) return 0;
			if (first >= last) return this->containers[0].size();

			uint_fast32_t cur_layer, cur_index;

			uint_fast32_t candidate_layer = this->containers.size(), candidate_index;
			uint_fast32_t first_temp = first, last_temp = last;
			LiteralLazySegmentTree<T, Mapping, Composition, MaxPicker, default_value>::execute_evaluation_above(first, last);
			if (last & 1)
			{
				if (this->unevaluated[0][last - 1].first)
				{
					this->containers[0][last - 1] = Mapping()(this->containers[0][last - 1], this->unevaluated[0][last - 1].second, 1);
					this->unevaluated[0][last - 1] = { false, default_value };
				}

				if (this->containers[0][last - 1] >= limit)
					return last - 1;
				//--last_temp;
			}
			if (first & 1)
			{
				if (this->unevaluated[0][first].first)
				{
					this->containers[0][first] = Mapping()(this->containers[0][first], this->unevaluated[0][first].second, 1);
					this->unevaluated[0][first] = { false, default_value };
				}

				if (this->containers[0][first] >= limit)
					candidate_layer = 0, candidate_index = first;
				++first_temp;
			}

			for (cur_layer = 1, first_temp >>= 1, last_temp >>= 1; first_temp != last_temp; ++cur_layer, first_temp >>= 1, last_temp >>= 1)
			{
				if (last_temp & 1)
				{
					if (this->unevaluated[cur_layer][last_temp - 1].first)
					{
						this->containers[cur_layer][last_temp - 1] = Mapping()(this->containers[cur_layer][last_temp - 1], this->unevaluated[cur_layer][last_temp - 1].second, (uint_fast32_t)1 << cur_layer);
						LiteralLazySegmentTree<T, Mapping, Composition, MaxPicker, default_value>::convey_evaluation(cur_layer, last_temp - 1);
					}

					if (this->containers[cur_layer][last_temp - 1] >= limit)
						break;
					//--last_temp;
				}
				if (first_temp & 1)
				{
					if (this->unevaluated[cur_layer][first_temp].first)
					{
						this->containers[cur_layer][first_temp] = Mapping()(this->containers[cur_layer][first_temp], this->unevaluated[cur_layer][first_temp].second, (uint_fast32_t)1 << cur_layer);
						LiteralLazySegmentTree<T, Mapping, Composition, MaxPicker, default_value>::convey_evaluation(cur_layer, first_temp);
					}

					if (this->containers[cur_layer][first_temp] >= limit)
						candidate_layer = cur_layer, candidate_index = first_temp;
					++first_temp;
				}
			}

			if (first_temp != last_temp) cur_index = last_temp - 1;
			else if (candidate_layer == this->containers.size()) return this->containers[0].size();
			else cur_layer = candidate_layer, cur_index = candidate_index;

			while (cur_layer > 1)
			{
				--cur_layer, cur_index <<= 1;
				if (this->unevaluated[cur_layer][cur_index | 1].first)
				{
					this->containers[cur_layer][cur_index | 1] = Mapping()(this->containers[cur_layer][cur_index | 1], this->unevaluated[cur_layer][cur_index | 1].second, (uint_fast32_t)1 << cur_layer);
					LiteralLazySegmentTree<T, Mapping, Composition, MaxPicker, default_value>::convey_evaluation(cur_layer, cur_index | 1);
				}

				if (this->containers[cur_layer][cur_index | 1] >= limit)
					cur_index |= 1;
				else if (this->unevaluated[cur_layer][cur_index].first)
				{
					this->containers[cur_layer][cur_index] = Mapping()(this->containers[cur_layer][cur_index], this->unevaluated[cur_layer][cur_index].second, (uint_fast32_t)1 << cur_layer);
					LiteralLazySegmentTree<T, Mapping, Composition, MaxPicker, default_value>::convey_evaluation(cur_layer, cur_index);
				}
			}

			if (cur_layer == 1)
			{
				cur_index <<= 1;
				if (this->unevaluated[0][cur_index | 1].first)
				{
					this->containers[0][cur_index | 1] = Mapping()(this->containers[0][cur_index | 1], this->unevaluated[0][cur_index | 1].second, 1);
					this->unevaluated[0][cur_index | 1] = { false, default_value };
				}

				if (this->containers[0][cur_index | 1] >= limit)
					cur_index |= 1;
				else if (this->unevaluated[0][cur_index].first)
				{
					this->containers[0][cur_index] = Mapping()(this->containers[0][cur_index], this->unevaluated[0][cur_index].second, 1);
					this->unevaluated[0][cur_index] = { false, default_value };
				}
			}

			return cur_index;
		}
	};
}

// レーティング 1200 までいくつ足りないかが「状態」になる
// 各状態に S' を 1 回作用させたときの、次の状態とその間の AC 回数を求める
// 区間加算をしたいので、遅延セグメント木を使用
static inline constexpr std::pair<std::vector<uint_fast32_t>, std::vector<uint_fast64_t>> prepare(const uint_fast32_t N, const std::string& _S) noexcept
{
	std::vector<uint_fast32_t> next(N + 1), count(N + 1, 0);
	std::iota(next.begin(), next.end(), 0);  // next = { 0, 1, 2, ... }

	using Mapping = decltype([](const uint_fast32_t target, const uint_fast32_t operation, const uint_fast32_t length) { return target + operation; });
	using Composition = decltype([](const uint_fast32_t target, const uint_fast32_t operation) { return target + operation; });
	MyLib::MaxLazySegmentTree<uint_fast32_t, Mapping, Composition, MyLib::DefaultMaxPicker<uint_fast32_t>, 0> mlst_next(std::move(next)), mlst_count(std::move(count));

	for (uint_fast32_t i = 0; i != N; ++i)
	{
		if (_S[i] == '0')
			mlst_next.update(0, N + 1, 1);
		else
		{
			const uint_fast32_t l = mlst_next.leftest_above(0, N + 1, 1);
			mlst_next.update(l, N + 1, UINT_FAST32_MAX), mlst_count.update(l, N + 1, 1);
		}
	}

	std::vector<uint_fast32_t> next_out(N + 1);
	std::vector<uint_fast64_t> count_out(N + 1);
	for (uint_fast32_t i = 0; i != N + 1; ++i)
		next_out[i] = std::min(mlst_next[i], N), count_out[i] = mlst_count[i];

	return std::make_pair(std::move(next_out), std::move(count_out));
}

// 各状態から次の状態への遷移を functional graph とみなして、ダブリングでいい感じにまとめる
// 残りは普通にシミュレーション
static inline constexpr uint_fast64_t solve(const uint_fast32_t N, const uint_fast64_t A, const std::string& _S) noexcept
{
	auto [next, count] = prepare(N, _S);
	std::array<std::vector<uint_fast32_t>, 40> doubling_next = { std::vector<uint_fast32_t>(std::move(next)), };
	std::array<std::vector<uint_fast64_t>, 40> doubling_count = { std::vector<uint_fast64_t>(std::move(count)), };
	for (uint_fast32_t i = 1; i != 40; ++i)
	{
		doubling_next[i].resize(N + 1), doubling_count[i].resize(N + 1);
		for (uint_fast32_t j = 0; j != N + 1; ++j)
			doubling_next[i][j] = doubling_next[i - 1][doubling_next[i - 1][j]], doubling_count[i][j] = doubling_count[i - 1][j] + doubling_count[i - 1][doubling_next[i - 1][j]];
	}

	uint_fast64_t ans_cycle = 0, AC_count = 0, cur_state = 0;
	for (uint_fast32_t i = 39; i != UINT_FAST32_MAX; --i)
		if (AC_count + doubling_count[i][cur_state] < A)
			AC_count += doubling_count[i][cur_state], cur_state = doubling_next[i][cur_state], ans_cycle |= UINT64_C(1) << i;

	uint_fast32_t i;
	for (i = 0; AC_count != A; ++i)
	{
		if (_S[i] == '0')
			++cur_state;
		else if (cur_state != 0)
			--cur_state, ++AC_count;
	}

	return ans_cycle * N + i;
}

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);

	uint_fast32_t N;
	uint_fast64_t A;
	std::string _S;
	std::cin >> N >> A;
	_S.reserve(N), std::cin >> _S;

	std::cout << solve(N, A, _S) << '\n';
	return 0;
}