競プロで使ってたやつ

main.cpp

//ここからテンプレート
#if 1
#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
#include<utility>
#include<type_traits>
#include<tuple>
#include<memory>
#include<iterator>
#include<string>
#include<functional>
#include<list>
#include<array>
#include<complex>

namespace utility
{
	template<class Range>std::size_t size(Range const& r)
	{
		return r.size();
	}
	template<class Type, std::size_t I>constexpr std::size_t size(Type const(&)[I])
	{
		return I;
	}
	
	template<class Iterator>struct iterator_range
	{
		Iterator first;
		Iterator last;

		Iterator begin()const
		{
			return first;
		}
		Iterator end()const
		{
			return last;
		}
		std::size_t size()const
		{
			return std::distance(first, last);
		}
	};
	template<class Iterator>auto front(iterator_range<Iterator>const& range)
	{
		return *range.first;
	}
	template<class Iterator>auto back(iterator_range<Iterator>const& range)
	{
		return *std::prev(range.last);
	}
	template<class Iterator>iterator_range<Iterator>make_iterator_range(Iterator first, Iterator last)
	{
		return iterator_range<Iterator>{first, last};
	}

	template<class Return, class Argument, class Func>class memoization_t;//recursion only
	template<class Return, class Func, class... Ts>class memoization_t<Return, std::tuple<Ts...>, Func>
	{
		std::shared_ptr<std::vector<std::pair<std::tuple<Ts...>, Return>>> memo;
		Func func;
	public:
		Return operator()(Ts const&... args)const
		{
			auto t = std::make_tuple(args...);
			for (auto const& p : *memo)
			{
				if (p.first == t)
					return p.second;
			}
			auto ret = func(std::cref(*this), args...);
			memo->emplace_back(t, ret);
			return ret;
		}

		memoization_t(Func fun) :
			memo(std::make_shared<std::vector<std::pair<std::tuple<Ts...>, Return>>>()),
			func(fun) {}
		memoization_t(memoization_t&&) = default;
		memoization_t(memoization_t const&) = default;
		memoization_t& operator=(memoization_t&&) = default;
		memoization_t& operator=(memoization_t const&) = default;
		~memoization_t() = default;
	};
	template<class Return, class ArgumentTuple, class Func>memoization_t<Return, ArgumentTuple, Func> make_memoization(Func func)
	{
		return memoization_t<Return, ArgumentTuple, Func>(func);
	}

	template<class Type>struct irange_t
	{
		Type first;
		Type last;
		struct iterator :std::iterator<std::forward_iterator_tag, Type>
		{
			Type num;
			iterator& operator++()
			{
				++num;
				return *this;
			}
			iterator operator++(int)
			{
				return iterator(num++);
			}
			Type operator*()const
			{
				return num;
			}

			iterator(Type val) :num(val) {}
			iterator(iterator&&) = default;
			iterator(iterator const&) = default;
			iterator& operator=(iterator&&) = default;
			iterator& operator=(iterator const&) = default;
			~iterator() = default;

			bool operator==(iterator const& rhs)const
			{
				return rhs.num == this->num;
			}
			bool operator!=(iterator const& rhs)const
			{
				return rhs.num != this->num;
			}
		};
		iterator begin()const
		{
			return iterator(first);
		}
		iterator end()const
		{
			return iterator(last);
		}
	};
	template<class Type>irange_t<Type> irange(Type first, Type last)
	{
		return irange_t<Type>{first, last};
	}

	struct none_t {};
	constexpr none_t none{};
	template<class T>class optional
	{
		union inside_t
		{
			T value;
			none_t ignore;
			constexpr inside_t(T const& v) :value(v) {}
			constexpr inside_t(T&& v) : value(std::move(v)) {}
			constexpr inside_t(none_t) : ignore(none) {}
			constexpr inside_t() : ignore(none) {}
			constexpr inside_t(inside_t const&) = default;
			inside_t(inside_t&&) = default;
			inside_t& operator=(inside_t const&) = default;
			inside_t& operator=(inside_t&&) = default;
			~inside_t() = default;
		};
		inside_t inside;
		bool flag;
	public:
		void swap(optional&& v)
		{
			std::swap(this->inside, v.inside);
			std::swap(this->flag, v.flag);
		}
		void reset()
		{
			if (flag)
			{
				inside.value.~T();
				inside.ignore = none;
				flag = false;
			}
		}
		
		constexpr optional(T const& v) :inside(v), flag(true) {}
		constexpr optional(T&& v) : inside(std::move(v)), flag(true) {}
		constexpr optional(none_t) : inside(), flag(false) {}
		constexpr optional() : inside(), flag(false) {}
		constexpr optional(optional const& v) : inside(v.inside), flag(v.flag) {}
		optional(optional&& v) : optional()
		{
			swap(std::move(v));
		}
		optional& operator=(optional const& v)
		{
			this->inside = v.inside;
			this->flag = v.flag;
			return *this;
		}
		optional& operator=(optional&& v)
		{
			swap(std::move(v));
			v.reset();
			return *this;
		}
		optional& operator=(T const& v)
		{
			reset();
			inside.value = v;
			flag = true;
			return *this;
		}
		optional& operator=(T&& v)
		{
			reset();
			inside.value = std::move(v);
			flag = true;
			return *this;
		}
		optional& operator=(none_t)
		{
			reset();
			return *this;
		}

		constexpr operator bool()const
		{
			return flag;
		}
		constexpr T const& operator*()const
		{
			return flag ? inside.value : throw std::domain_error("optional error: dont have value");
		}
	};
	template<class T>constexpr optional<typename std::remove_reference<typename std::remove_const<T>::type>::type>make_optional(T&& v)
	{
		return optional<std::remove_reference_t<std::remove_const_t<T>>>(std::forward<T>(v));
	}

	namespace detail
	{
		template<class>struct apply_tuple_t;
		template<std::size_t... Is>struct apply_tuple_t<std::index_sequence<Is...>>
		{
			template<class Func, class Tuple>static decltype(auto) run(Func func, Tuple const& t)
			{
				return func(std::get<Is>(t)...);
			}
		};
	}

	template<class Func, class... Args>decltype(auto) apply_tuple(Func func, std::tuple<Args...>const& vec)
	{
		return detail::apply_tuple_t<std::make_index_sequence<sizeof...(Args)>>::run(func, vec);
	}

	template<class T, std::size_t I>constexpr T const& front(T const(&ar)[I])
	{
		return ar[0];
	}
	template<class Range>auto front(Range const& vec)->decltype(vec[0]) const&
	{
		return vec[0];
	}
	template<class Range>auto front(Range const& vec)->typename std::enable_if<
		!std::is_same<typename std::iterator_traits<decltype(vec.begin())>::iterator_category,std::random_access_iterator_tag>::value,
		decltype(vec.front()) const&>::type
	{
		return vec.front();
	}

	template<class T, std::size_t I>constexpr T const& back(T const(&ar)[I])
	{
		return ar[I - 1];
	}
	template<class Range>auto back(Range const& vec)->decltype(vec[0]) const&
	{
		return vec[vec.size() - 1];
	}
	template<class Range>auto back(Range const& vec)->typename std::enable_if<
		!std::is_same<typename std::iterator_traits<decltype(vec.begin())>::iterator_category, std::random_access_iterator_tag>::value,
		decltype(vec.front()) const&>::type
	{
		return vec.back();
	}

	class tribool
	{
		char flag;
	public:
		tribool() = default;
		tribool(tribool&&) = default;
		tribool(tribool const&) = default;
		tribool& operator=(tribool&&) = default;
		tribool& operator=(tribool const&) = default;
		~tribool() = default;

		constexpr tribool(none_t) :tribool() {}
		constexpr tribool(bool f) : flag(0b10 + f) {}
		
		constexpr bool is_defined()const
		{
			return static_cast<bool>(flag & 0b10);
		}
		constexpr bool is_true()const
		{
			return is_defined() && static_cast<bool>(flag & 0b01);
		}
		constexpr bool is_false()const
		{
			return is_defined() && static_cast<bool>(flag ^ 0b11);
		}


	};
	constexpr bool operator==(tribool b, none_t)
		{
			return !b.is_defined();
		}
	constexpr bool operator==(none_t,tribool b)
		{
			return !b.is_defined();
		}
	constexpr bool operator!=(tribool b, none_t)
		{
			return b.is_defined();
		}
	constexpr bool operator!=(none_t, tribool b)
		{
			return b.is_defined();
		}
	constexpr bool operator==(tribool b, bool f)
		{
			return f ? b.is_true() : b.is_false();
		}
	constexpr bool operator==(bool f,tribool b)
		{
			return f ? b.is_true() : b.is_false();
		}
	constexpr bool operator!=(tribool b, bool f)
		{
			return !(b == f);
		}
	constexpr bool operator!=(bool f, tribool b)
		{
			return !(b == f);
		}
	constexpr none_t undefined{};

	template<class T>using point = std::pair<T, T>;
	typedef long long int int64;

	template<class Func>struct scope_exit_t
	{
		Func func;
		scope_exit_t(Func f) :func(f) {}
		scope_exit_t(scope_exit_t &&) = delete;
		scope_exit_t(scope_exit_t const&) = delete;
		scope_exit_t& operator=(scope_exit_t &&) = delete;
		scope_exit_t& operator=(scope_exit_t const&) = delete;
		~scope_exit_t()
		{
			func();
		}
	};
	template<class Func>scope_exit_t<Func> scope_exit(Func func)
	{
		return scope_exit_t<Func>(func);
	}
}
namespace container
{
	template<class Type>class dual_array
	{
		std::vector<Type> vec;
		int x_;
	public:
		dual_array(std::size_t x_size, std::size_t y_size) :vec(x_size*y_size), x_(x_size) {}
		dual_array(dual_array const&) = default;
		dual_array(dual_array&&) = default;
		dual_array& operator=(dual_array const&) = default;
		dual_array& operator=(dual_array&&) = default;

		auto begin()
		{
			return std::begin(vec);
		}
		auto begin()const
		{
			return std::begin(vec);
		}
		auto end()
		{
			return std::end(vec);
		}
		auto end()const
		{
			return std::end(vec);
		}

		Type& operator()(int x, int y)
		{
			return vec[x + y*x_];
		}
		Type const& operator()(int x, int y)const
		{
			return vec[x + y*x_];
		}

		std::size_t size()const
		{
			return vec.size();
		}
		std::size_t x_size()const
		{
			return x_;
		}
		std::size_t y_size()const
		{
			return vec.size() / x_;
		}
	};
	template<class Type, std::size_t Max>class value_tank
	{
		std::array<utility::optional<Type>, Max> value_ = {};
		std::size_t size_ = 0;
	public:
		value_tank() = default;
		value_tank(value_tank const&) = default;
		value_tank(value_tank&&) = default;
		value_tank& operator=(value_tank const&) = default;
		value_tank& operator=(value_tank&&) = default;
		~value_tank() = default;

		std::size_t size()const
		{
			return size_;
		}
		struct iterator :std::iterator<std::input_iterator_tag, Type>
		{
			utility::optional<Type> const* ptr_;
			iterator(utility::optional<Type> const*ptr) :ptr_(ptr){}
			iterator(iterator const&) = default;
			iterator(iterator&&) = default;
			iterator& operator=(iterator const&) = default;
			iterator& operator=(iterator&&) = default;
			~iterator() = default;

			Type const& operator*()const
			{
				return **ptr_;
			}
			iterator& operator++()
			{
				++ptr_;
				return *this;
			}
			iterator operator++(int)
			{
				auto ret = *this;
				++ptr_;
				return ret;
			}
			bool operator==(iterator const& lhs)const
			{
				return ptr_ == lhs.ptr_;
			}
			bool operator!=(iterator const& lhs)const
			{
				return ptr_ != lhs.ptr_;
			}
		};
		iterator begin()const
		{
			return iterator(&value_[0]);
		}
		iterator end()const
		{
			return iterator(&value_[size_]);
		}
		void push_back(Type&& v)
		{
			if (size_ < Max)
			{
				value_[size_] = std::move(v);
				++size_;
			}
		}
		void push_back(Type const& v)
		{
			if (size_ < Max)
			{
				value_[size_] = v;
				++size_;
			}
		}
		Type const& operator[](std::size_t index)const
		{
			return *(value_[index]);
		}
	};
}
namespace algorithm
{

	namespace range
	{
		template<class InputRange, class Pred>bool all_of(InputRange const& ran, Pred pred)
		{
			return std::all_of(std::begin(ran), std::end(ran), pred);
		}
		template<class Type, std::size_t I, class Pred>bool all_of(Type const(&ar)[I], Pred pred)
		{
			return std::all_of(std::begin(ar), std::end(ar), pred);
		}
		template<class InputRange, class Pred>bool any_of(InputRange const& ran, Pred pred)
		{
			return std::any_of(std::begin(ran), std::end(ran), pred);
		}
		template<class Type, std::size_t I, class Pred>bool any_of(Type const(&ar)[I], Pred pred)
		{
			return std::any_of(std::begin(ar), std::end(ar), pred);
		}
		template<class InputRange, class Pred>std::size_t count_if(InputRange const& ran, Pred pred)
		{
			return std::count_if(std::begin(ran), std::end(ran), pred);
		}
		template<class Type, std::size_t I, class Pred>std::size_t count_if(Type const(&ar), Pred pred)
		{
			return std::count_if(std::begin(ar), std::end(ar), pred);
		}

		template<class RandomRange, class Comp>void sort(RandomRange& ran, Comp comp)
		{
			return std::sort(std::begin(ran), std::end(ran), comp);
		}
		template<class Type, std::size_t I, class Comp>void sort(Type(&ar)[I], Comp comp)
		{
			return std::sort(std::begin(ar), std::end(ar), comp);
		}
		template<class RandomRange>void sort(RandomRange& ran)
		{
			return std::sort(std::begin(ran), std::end(ran));
		}
		template<class Type, std::size_t I>void sort(Type(&ar)[I])
		{
			return std::sort(std::begin(ar), std::end(ar));
		}

		template<class RandomRange, class Comp>void stable_sort(RandomRange& ran, Comp comp)
		{
			return std::stable_sort(std::begin(ran), std::end(ran), comp);
		}
		template<class Type, std::size_t I, class Comp>void stable_sort(Type(&ar)[I], Comp comp)
		{
			return std::stable_sort(std::begin(ar), std::end(ar), comp);
		}
		template<class RandomRange>void stable_sort(RandomRange& ran)
		{
			return std::stable_sort(std::begin(ran), std::end(ran));
		}
		template<class Type, std::size_t I>void stable_sort(Type(&ar)[I])
		{
			return std::stable_sort(std::begin(ar), std::end(ar));
		}

		template<class InputRange>std::size_t unique_count(InputRange const& range)
		{
			std::vector<char> flag;
			std::size_t count{};
			for (auto end = std::begin(range);end != std::end(range);++end)
			{
				auto fla = std::begin(flag);
				for (auto beg = std::begin(range);beg != end;++beg)
				{
					if (!*fla)
						continue;
					if (*beg == *end)
					{
						flag.push_back(false);
						goto next;
					}
				}
				flag.push_back(true);
				++count;
			next:;
			}
			return count;
		}

		template<class InputRange>auto max(InputRange const& range)
		{
			auto ret = *std::begin(range);
			for (auto const& v : range)
			{
				ret = std::max(ret, v);
			}
			return ret;
		}
		template<class InputRange>auto min(InputRange const& range)
		{
			auto ret = *std::begin(range);
			for (auto const& v : range)
			{
				ret = std::min(ret, v);
			}
			return ret;
		}

		template<class InputRange, class Pred>auto find(InputRange const& range,Pred pred)
			->utility::optional<decltype(*std::begin(range))>
		{
			for (auto const& v : range)
			{
				if (pred(v))
					return v;
			}
			return utility::none;
		}
	}

	namespace dual_range
	{
		namespace detail
		{
			template<class Iterator,class Pred>struct dual_range_adapter
			{
				Iterator ite;
				Pred pred;
				template<class Value>decltype(auto) operator()(Value& now)
				{
					return pred(*(ite++), now);
				}
			};
			template<class Iterator, class Pred>dual_range_adapter<Iterator, Pred>
				make_dual_range_adapter(Iterator first, Pred pred)
			{
				return dual_range_adapter<Iterator, Pred>{first, pred};
			}
		}
		template<class Range, class Pred>void for_each(Range& ran, Pred pred)
		{
			auto ite = std::begin(ran);
			auto last = std::end(ran);
			if (ite == last)return;
			std::for_each(std::next(ite), last, detail::make_dual_range_adapter(ite, pred));
		}
		template<class Type, std::size_t I, class Pred>void for_each(Type(&ran)[I], Pred pred)
		{
			auto ite = std::begin(ran);
			auto last = std::end(ran);
			if (ite == last)return;
			std::for_each(std::next(ite), last, detail::make_dual_range_adapter(ite, pred));
		}

		template<class Range, class Pred>auto category_range(Range& ran, Pred pred)
		{
			auto ite = std::begin(ran);
			auto last = std::end(ran);
			std::vector<utility::iterator_range<decltype(ite)>> ret{};
			if (ite == last)
				return ret;
			auto pre = ite;
			auto fir = pre;
			++ite;

			for (;ite != last;[&] {pre = ite++;}())
			{
				if (pred(*pre, *ite))
				{
					ret.push_back(utility::make_iterator_range(fir, ite));
					fir = ite;
				}
			}
			ret.push_back(utility::make_iterator_range(fir, ite));
			return ret;
		}
		template<class Type, std::size_t I, class Pred>auto category_range(Type(&ran)[I], Pred pred)
		{
			auto ite = std::begin(ran);
			auto last = std::end(ran);
			std::vector<utility::iterator_range<decltype(ite)>> ret{};
			if (ite == last)
				return ret;
			auto pre = ite;
			auto fir = pre;
			++ite;

			for (;ite != last;[&] {pre = ite++;}())
			{
				if (pred(*pre, *ite))
				{
					ret.push_back(utility::make_iterator_range(fir, ite));
					fir = ite;
				}
			}
			ret.push_back(fir, ite);
			return ret;
		}

		template<class Range, class Pred>std::size_t count_if(Range& ran, Pred pred)
		{
			auto first = std::begin(ran);
			auto last = std::end(ran);
			if (first == last)return 0u;
			return std::count_if(std::next(first), last, detail::make_dual_range_adapter(first, pred));
		}
		template<class Type, std::size_t I, class Pred>std::size_t count_if(Type(&ran)[I], Pred pred)
		{
			auto first = std::begin(ran);
			auto last = std::end(ran);
			if (first == last)return 0u;
			return std::count_if(std::next(first), last, detail::make_dual_range_adapter(first, pred));
		}

	}

	namespace other
	{
		namespace detail
		{
			template<class Argument, class Next>struct breadth_first_search;
			template<class Next,class... Args>struct breadth_first_search<std::tuple<Args...>, Next>
			{
				static auto run(Args... first,Next next)
				{
					std::vector<std::tuple<Args...>> states = { std::make_tuple(first...) };
					states.reserve(1000);
					std::function<void(Args...)> emplace_back = [&states = states](Args... args)
					{
						states.emplace_back(args...);
					};

					auto next_func = [&nex = next, &emplace_back=emplace_back](Args... args) 
					{
						return nex(args..., emplace_back);
					};

					int checked = 0;
					for (int _ = 1;;++_)
					{
						int target = states.size();
						for (int i = checked;i < target;++i)
						{
							if (utility::apply_tuple(next_func, states[i]))
								return _;
							
						}
						checked = target;
					}
				}
			};
		}
		template<class Next, class... Args>auto breadth_first_search(Next next,  Args... first)//Next == std::function<bool(Args..., std::function<void(Args...)> const&)>
		{
			return detail::breadth_first_search<std::tuple<Args...>, Next>::run(first..., next);
		}

		template<class... Args>struct dijkstra_argorithm_t
		{
			template<class Next>std::size_t operator()(Args... start, Args... target, Next next)//Next == std::function<void(Args..., std::function<void(Args..., std::size_t)> const&)>
			{
				auto end = std::make_tuple(target...);

				std::vector<std::pair<std::tuple<Args...>, std::size_t>> confirmed = { std::make_pair(std::make_tuple(start...),0) };
				std::list<std::pair<std::tuple<Args...>, std::size_t>> candidate;
				confirmed.reserve(1000);
				std::size_t from = 0;
				std::function<void(Args..., std::size_t)> emplace_back = [&candidate, &confirmed, &from](Args... args, std::size_t size)
				{
					auto t = std::make_tuple(args...);
					auto ite = std::find_if(std::begin(confirmed), std::end(confirmed), [&t = t](auto const& p){return p.first == t;});
					if (ite != std::end(confirmed))return;
					auto ite2 = std::find_if(std::begin(candidate), std::end(candidate), [&t = t](auto const& p){return p.first == t;});
					if (ite2 != std::end(candidate))
					{
						ite2->second = std::min(ite2->second, from + size);
					}
					else
					{
						candidate.emplace_back(t, from + size);
					}
				};

				auto next_func = [&nex = next, &emplace_back = emplace_back](Args... args)
				{
					return nex(args..., emplace_back);
				};
				
				while (true)
				{
					from = confirmed[utility::size(confirmed) - 1].second;
					utility::apply_tuple(next_func, confirmed[utility::size(confirmed) - 1].first);
					auto ite = candidate.begin();
					for (auto i = candidate.begin();i != candidate.end();++i)
					{
						if (ite->second > i->second)
							ite = i;
					}
					confirmed.push_back(*ite);
					candidate.erase(ite);
					if (confirmed[utility::size(confirmed) - 1].first == end)
						break;
				}
				return confirmed[utility::size(confirmed) - 1].second;
			}
		};
	}
}
namespace iostream
{
	template<class Type>Type read()
	{
		Type ret;
		std::cin >> ret;
		return ret;
	}

	template<class TypeA, class TypeB>std::pair<TypeA, TypeB> twin_read() 
	{
		TypeA a;
		TypeB b;
		std::cin >> a >> b;
		return std::make_tuple(a, b);
	}

	namespace detail
	{
		template<class T>auto tuple_read()
		{
			return std::make_tuple(iostream::read<T>());
		}
		template<class T,class... Ts>auto tuple_read()->typename std::enable_if<(sizeof...(Ts)>0), std::tuple<T, Ts...>>::type
		{
			T v = iostream::read<T>();
			return std::tuple_cat(std::make_tuple(v), tuple_read<Ts...>());
		}
	}
	template<class... Ts>auto tuple_read()
	{
		return detail::tuple_read<Ts...>();
	}

	template<class... Ts>auto vector_read(std::size_t size)->
		typename std::enable_if<(sizeof...(Ts)>1), std::vector<std::tuple<Ts...>>>::type
	{
		std::vector<std::tuple<Ts...>> ret;
		for (std::size_t i = 0;i < size;++i)
		{
			ret.push_back(tuple_read<Ts...>());
		}
		return std::move(ret);
	}
	template<class T>auto vector_read(std::size_t size)
	{
		std::vector<T> ret;
		for (std::size_t i = 0;i < size;++i)
		{
			ret.push_back(read<T>());
		}
		return std::move(ret);
	}
	
}
namespace adaptor
{
	namespace classes
	{
		template<class Iterator, class Pred>struct filter_t
		{
			Iterator first;
			Iterator last;
			Pred pred;
			struct iterator :std::iterator<
				std::forward_iterator_tag,
				typename std::iterator_traits<Iterator>::value_type,
				typename std::iterator_traits<Iterator>::difference_type,
				typename std::iterator_traits<Iterator>::pointer,
				typename std::iterator_traits<Iterator>::reference>
			{
				Iterator ite;
				Iterator last;
				Pred pred;
				
				iterator(Iterator i, Iterator las, Pred p) :ite(i), last(las), pred(p) {}
				iterator(iterator const&) = default;
				iterator(iterator&&) = default;
				iterator& operator=(iterator const&) = default;
				iterator& operator=(iterator&&) = default;
				~iterator() = default;

				iterator& operator++()
				{
					++ite;
					for (;ite != last;++ite)
					{
						if (pred(*ite))
							return *this;
					}
					return *this;
				}
				iterator operator++(int)
				{
					auto ret = *this;
					++ite;
					for (;ite != last;++ite)
					{
						if (pred(*ite))
							return ret;
					}
					return ret;
				}
				typename std::iterator_traits<Iterator>::value_type const& operator*()
				{
					return *ite;
				}
				typename std::iterator_traits<Iterator>::value_type const& operator*()const
				{
					return *ite;
				}
				bool operator==(iterator const& rhs)const
				{
					return rhs.ite == this->ite;
				}
				bool operator!=(iterator const& rhs)const
				{
					return rhs.ite != this->ite;
				}

			};
			iterator begin()const
			{
				return iterator(first, last, pred);
			}
			iterator end()const
			{
				return iterator(last, last, pred);
			}
			filter_t(Iterator fir, Iterator las, Pred p) :first(fir), last(las), pred(p) {}
			filter_t(filter_t const&) = default;
			filter_t(filter_t&&) = default;
			filter_t& operator=(filter_t const&) = default;
			filter_t& operator=(filter_t&&) = default;
			~filter_t() = default;
		};
		struct filter_adaptor_t
		{
			template<class Pred>struct filter_adaptor
			{
				Pred pred;
			};
			template<class Pred>filter_adaptor<Pred> operator()(Pred pred)const
			{
				return filter_adaptor<Pred>{pred};
			}
		};
		template<class Range, class Pred>auto operator|(Range const& range, filter_adaptor_t::filter_adaptor<Pred> filter)
			->filter_t<decltype(range.begin()), Pred>
		{
			return filter_t<decltype(range.begin()), Pred>(range.begin(), range.end(), filter.pred);
		}

		template<class Iterator, class Func>struct transport_t
		{
			Iterator first;
			Iterator last;
			Func func;
			struct iterator :std::iterator<
				std::forward_iterator_tag,
				typename std::iterator_traits<Iterator>::value_type,
				typename std::iterator_traits<Iterator>::difference_type,
				typename std::iterator_traits<Iterator>::pointer,
				typename std::iterator_traits<Iterator>::reference>
			{
				Iterator ite;
				Iterator last;
				Func func;

				iterator(Iterator i, Iterator las, Func p) :ite(i), last(las), func(p) {}
				iterator(iterator const&) = default;
				iterator(iterator&&) = default;
				iterator& operator=(iterator const&) = default;
				iterator& operator=(iterator&&) = default;
				~iterator() = default;

				iterator& operator++()
				{
					++ite;
					
					return *this;
				}
				iterator operator++(int)
				{
					auto ret = *this;
					++ite;
					return ret;
				}
				auto operator*()const
				{
					return func(*ite);
				}
				bool operator==(iterator const& rhs)const
				{
					return rhs.ite == this->ite;
				}
				bool operator!=(iterator const& rhs)const
				{
					return rhs.ite != this->ite;
				}

			};
			iterator begin()const
			{
				return iterator(first, last, func);
			}
			iterator end()const
			{
				return iterator(last, last, func);
			}
			transport_t(Iterator fir, Iterator las, Func p) :first(fir), last(las), func(p) {}
			transport_t(transport_t const&) = default;
			transport_t(transport_t&&) = default;
			transport_t& operator=(transport_t const&) = default;
			transport_t& operator=(transport_t&&) = default;
			~transport_t() = default;
		};
		struct transport_adaptor_t
		{
			template<class Func>struct transport_adaptor
			{
				Func func;
			};
			template<class Func>transport_adaptor<Func> operator()(Func const& func)const
			{
				return transport_adaptor<Func>{func};
			}
		};
		template<class Range, class Func>auto operator|(Range const& range,transport_adaptor_t::transport_adaptor<Func> adaptor)
			->transport_t<decltype(range.begin()), Func>
		{
			return transport_t<decltype(range.begin()), Func>(range.begin(), range.end(), adaptor.func);
		}

		template<class Iterator>struct indexes_t
		{
			Iterator first;
			Iterator last;
			struct iterator :std::iterator<
				std::input_iterator_tag,
				std::pair<typename std::iterator_traits<Iterator>::value_type, std::size_t>,
				typename std::iterator_traits<Iterator>::difference_type,
				typename std::iterator_traits<Iterator>::pointer,
				typename std::iterator_traits<Iterator>::reference>
			{
				Iterator ite;
				std::size_t count;
				iterator(Iterator i) :ite(i), count(0u) {}
				iterator(iterator const&) = default;
				iterator(iterator&&) = default;
				iterator& operator=(iterator const&) = default;
				iterator& operator=(iterator&&) = default;
				~iterator() = default;

				iterator& operator++()
				{
					++ite;
					++count;
					return *this;
				}
				iterator operator++(int)
				{
					auto ret = *this;
					++ite;
					++count;
					return ret;
				}
				std::pair<typename std::iterator_traits<Iterator>::value_type, std::size_t>operator*()const
				{
					return std::make_pair(*ite, count);
				}
				bool operator==(iterator const& rhs)const
				{
					return rhs.ite == this->ite;
				}
				bool operator!=(iterator const& rhs)const
				{
					return rhs.ite != this->ite;
				}
			};
			iterator begin()const
			{
				return iterator(first);
			}
			iterator end()const
			{
				return iterator(last);
			}
		};
		struct indexes_adaptor
		{
		};
		template<class Range>auto operator|(Range const& range, indexes_adaptor)
			->indexes_t<decltype(range.begin())>
		{
			return indexes_t<decltype(range.begin())>{range.begin(), range.end()};
		}

		struct to_vector_adaptor
		{

		};
		template<class Range>auto operator|(Range const& range, to_vector_adaptor)
			->std::vector<typename std::iterator_traits<decltype(range.begin())>::value_type>
		{
			std::vector<typename std::iterator_traits<decltype(std::begin(range))>::value_type> ret{ std::begin(range),std::end(range) };
			return ret;
		}

		struct skip_adaptor
		{
			struct skip_adaptor_t
			{
				int v;
			};
			skip_adaptor_t operator()(int v)const
			{
				return skip_adaptor_t{ v };
			}
		};
		template<class Range>auto operator|(Range const& range, skip_adaptor::skip_adaptor_t adaptor)
			->utility::iterator_range<decltype(range.begin())>
		{
			return utility::make_iterator_range(std::next(std::begin(range), adaptor.v), std::end(range));
		}

		template<class IteratorA, class IteratorB>struct dual_t
		{
			struct iterator:std::iterator<std::forward_iterator_tag,std::pair<
				typename std::iterator_traits<IteratorA>::value_type,
				typename std::iterator_traits<IteratorB>::value_type>>
			{
				IteratorA itea;
				IteratorB iteb;
				iterator(IteratorA a, IteratorB b) :itea(a), iteb(b) {}
				iterator(iterator const&) = default;
				iterator(iterator&&) = default;
				iterator& operator=(iterator const&) = default;
				iterator& operator=(iterator&&) = default;
				~iterator() = default;
				bool operator!=(iterator const& rhs)const
				{
					return itea != rhs.itea&&iteb != rhs.iteb;
				}
				auto operator*()const
				{
					return std::make_pair(*itea, *iteb);
				}
				iterator& operator++()
				{
					++itea;
					++iteb;
					return *this;
				}
			};
			IteratorA firsta;
			IteratorB firstb;
			IteratorA lasta;
			IteratorB lastb;
			iterator begin()const
			{
				return iterator(firsta, firstb);
			}
			iterator end()const
			{
				return iterator(lasta, lastb);
			}
		};
		struct dual_adaptor_t
		{
			template<class Iterator>struct adaptor
			{
				Iterator first;
				Iterator last;
			};
			template<class Range>auto operator()(Range const& range)const ->adaptor<decltype(std::begin(range))>
			{
				return adaptor<decltype(std::begin(range))>{std::begin(range), std::end(range)};
			}
		};
		template<class Range, class Iterator>auto operator|(Range const& lhs, dual_adaptor_t::adaptor<Iterator>const& rhs)
		{
			return dual_t<decltype(std::begin(lhs)), Iterator>{std::begin(lhs), rhs.first, std::end(lhs), rhs.last};
		}
	}
	template<class Range, class Pred>auto filtered(Range const& range, Pred pred)
		->classes::filter_t<decltype(range.begin()), Pred>
	{
		return classes::filter_t<decltype(range.begin()), Pred>(range.begin(), range.end(), pred);
	}
	constexpr classes::filter_adaptor_t filter{};

	template<class Range, class Func>auto transported(Range const& range, Func func)
		->classes::transport_t<decltype(range.begin()), Func>
	{
		return classes::transport_t<decltype(range.begin()), Func>(range.begin(), range.end(), func);
	}
	constexpr classes::transport_adaptor_t transport{};

	template<class Range>auto indexed(Range const& range)
		->classes::indexes_t<decltype(range.begin())>
	{
		return classes::indexes_t<decltype(range.begin())>{range.begin(), range.end()};
	}
	constexpr classes::indexes_adaptor indexes{};

	template<class Range>auto vectored(Range const& range)
		->std::vector<typename std::iterator_traits<decltype(range.begin())>::value_type>
	{
		std::vector<typename std::iterator_traits<decltype(range.begin())>::value_type> ret{ range.begin().range.end() };
		return ret;
	}
	constexpr classes::to_vector_adaptor to_vector{};

	template<class Range>auto range_skip(Range const& range, int v)
		->utility::iterator_range<decltype(range.begin())>
	{
		return utility::make_iterator_range(std::next(range.begin(), v), range.end());
	}
	constexpr classes::skip_adaptor skip{};

	template<class RangeA, class RangeB>auto dual_range(RangeA const& range_a, RangeB const& range_b)
	{
		return classes::dual_t<decltype(std::begin(range_a)), decltype(std::begin(range_b))>
		{
			std::begin(range_a),std::begin(range_b),std::end(range_a),std::end(range_b)
		};
	}
	constexpr classes::dual_adaptor_t dual{};
}
namespace math
{
	template<class T>T pow(T p, int n)
	{
		return n == 0 ? 1 : n == 1 ? p : n == 2 ? p*p : n % 2 == 0 ? pow(pow(p, n / 2), 2) : pow(pow(p, n / 2), 2)*p;
	}

	int log(long long int p, int n)
	{
		utility::int64 t = n;
		for (int i = 0;;++i)
		{
			if (t > p)
				return i;
			t *= n;
		}
	}

	constexpr double pi = 3.141592653589793;

	namespace detail
	{
		int gcd(int larger, int less)
		{
			return less == 0 ? larger : gcd(less, larger%less);
		}
	}

	int gcd(int lhs, int rhs)
	{
		return lhs < rhs ? detail::gcd(rhs, lhs) : detail::gcd(lhs, rhs);
	}

	class polynomial
	{
		std::vector<std::complex<double>> value;
		void swap(polynomial&& p)
		{
			std::swap(value, p.value);
		}
	public:
		polynomial() :value{ 0.0 } {}
		polynomial(polynomial const&) = default;
		polynomial(std::vector<std::complex<double>>&& vec) :value(std::move(vec)) {}
		polynomial(polynomial&& p) :polynomial()
		{
			swap(std::move(p));
		}
		polynomial(std::initializer_list<std::complex<double>> lis) :value(lis) {}
		

		polynomial& operator=(polynomial const&) = default;
		polynomial& operator=(polynomial&& p)
		{
			value = std::vector<std::complex<double>>{ 0.0 };
			swap(std::move(p));
			return *this;
		}

		~polynomial() = default;
		std::complex<double> operator[](std::size_t deg)const
		{
			return deg >= value.size() ? 0.0 : value[deg];
		}
		std::size_t degree()const
		{
			return value.size() - 1;
		}
		void strict_degree_set()
		{
			int N = degree();
			for (;N > 0;--N)
			{
				if (value[N] != 0.0)
					break;
			}
			value.resize(N + 1);
		}

		friend polynomial fourier_transform(polynomial const& p, std::size_t N)
		{
			std::vector<std::complex<double>> vec = p.value;
			vec.resize(N);

			std::size_t i = 0;
			for (std::size_t j = 1;j < N - 1;++j)
			{
				for (std::size_t k = N >> 1;k > (i ^= k);k >>= 1);
				if (j < i)
				{
					std::swap(vec[i], vec[j]);
				}
			}
			std::size_t m;
			for (std::size_t mh = 1;(m = mh << 1) <= N;mh = m)
			{
				std::size_t irev = 0;
				for (std::size_t i = 0;i < N;i += m)
				{
					std::complex<double> c(std::cos(2 * pi*irev / N), std::sin(2 * pi*irev / N));
					std::size_t k;
					for (k = N >> 2;k > (irev ^= k);k >>= 1);
					for (std::size_t j = i;j < mh + i;++j)
					{
						k = j + mh;
						auto x = vec[j] - vec[k];
						vec[j] += vec[k];
						vec[k] = c*x;
					}
				}
			}
			return polynomial(std::move(vec));
		}
		friend polynomial inverse_fourier_transform(polynomial const& p, std::size_t N)
		{
			std::vector<std::complex<double>> vec = p.value;
			vec.resize(N);

			std::size_t i = 0;
			for (std::size_t j = 1;j < N - 1;++j)
			{
				for (std::size_t k = N >> 1;k >(i ^= k);k >>= 1);
				if (j < i)
				{
					std::swap(vec[i], vec[j]);
				}
			}
			std::size_t m;
			for (std::size_t mh = 1;(m = mh << 1) <= N;mh = m)
			{
				std::size_t irev = 0;
				for (std::size_t i = 0;i < N;i += m)
				{
					std::complex<double> c(std::cos(2 * pi*irev / N), -std::sin(2 * pi*irev / N));
					std::size_t k;
					for (k = N >> 2;k >(irev ^= k);k >>= 1);
					for (std::size_t j = i;j < mh + i;++j)
					{
						k = j + mh;
						auto x = vec[j] - vec[k];
						vec[j] += vec[k];
						vec[k] = c*x;
					}
				}
			}
			for (auto& v : vec)
			{
				v /= N;
			}
			return polynomial(std::move(vec));
		}
		friend polynomial operator*(polynomial const& lhs, polynomial const& rhs)
		{
			std::size_t N = 1;
			while (true)
			{
				N *= 2;
				if (N > (lhs.degree() + rhs.degree()))
					break;
			}
			auto lhs_ = fourier_transform(lhs, N);
			auto rhs_ = fourier_transform(rhs, N);
			std::vector<std::complex<double>> vec;
			for (std::size_t i = 0;i < N;++i)
			{
				vec.push_back(lhs_[i] * rhs_[i]);
			}
			auto ret = inverse_fourier_transform(polynomial(std::move(vec)), N);
			ret.strict_degree_set();
			return ret;
		}
	};

	int real_integer(std::complex<int> c)
	{
		int v = c.real();
		return v + (c.real() - v > 0 / 5);
	}

	template<class T>polynomial make_poly(std::vector<T> const& vec)
	{
		auto range = vec | adaptor::transport([](T const& v) {return static_cast<std::complex<double>>(v);});
		std::vector<std::complex<double>> ret(std::begin(range), std::end(range));
		return polynomial(std::move(ret));
	}
}
namespace string
{
	namespace detail
	{
		struct substring
		{
			std::string const& str_;
			std::size_t start_;
			std::size_t size_;

			bool operator==(substring const& rhs)const
			{
				if (size_ != rhs.size_)
					return false;
				for (std::size_t i = 0;i < size_;++i)
				{
					if (rhs.str_[rhs.start_ + i] != str_[start_ + i])
						return false;
				}
				return true;
			}
			bool operator!=(substring const& rhs)const
			{
				return !(rhs.operator==(*this));
			}
			std::string str()const
			{
				return str_.substr(start_, size_);
			}
		};

		struct substring_iterator :std::iterator<std::input_iterator_tag, substring>
		{
			std::string const& str_;
			std::size_t start_;
			std::size_t size_;
			substring_iterator(std::string const& str, std::size_t start, std::size_t size) :str_(str), start_(start), size_(size) {}
			substring_iterator(substring_iterator&&) = default;
			substring_iterator(substring_iterator const&) = default;
			substring_iterator& operator=(substring_iterator&&) = default;
			substring_iterator& operator=(substring_iterator const&) = default;
			~substring_iterator() = default;

			substring_iterator& operator++()
			{
				++start_;
				return *this;
			}
			substring_iterator operator++(int)
			{
				auto ret = *this;
				++start_;
				return ret;
			}
			substring operator*()const
			{
				return substring{ str_,start_,size_ };
			}

			bool operator==(substring_iterator const& rhs)const
			{
				return &str_ == &str_ &&
					start_ == rhs.start_&&
					size_ == rhs.size_;
			}
			bool operator!=(substring_iterator const& rhs)const
			{
				return !rhs.operator==(*this);
			}
		};
	}
	class substring_adaptor
	{
		std::string const& str_;
		std::size_t size_;
	public:
		substring_adaptor(std::string const& str, std::size_t size) :str_(str), size_(size) {}
		substring_adaptor(substring_adaptor&&) = default;
		substring_adaptor(substring_adaptor const&) = default;
		substring_adaptor& operator=(substring_adaptor&&) = default;
		substring_adaptor& operator=(substring_adaptor const&) = default;
		~substring_adaptor() = default;

		detail::substring_iterator begin()const
		{
			if (str_.size() < size_)
				return detail::substring_iterator(str_, 0, 0);
			return detail::substring_iterator(str_, 0, size_);
		}
		detail::substring_iterator end()const
		{
			if (str_.size() < size_)
				return detail::substring_iterator(str_, 0, 0);
			return detail::substring_iterator(str_, str_.size() - size_ + 1, size_);
		}
	};
	
}
void Main(std::integral_constant<int, 0>);
void Main(std::integral_constant<int, 1>);
void Main(std::integral_constant<int, 2>);
void Main(std::integral_constant<int, 3>);
void Main(std::integral_constant<int, 4>);
#endif//テンプレートここまで
//ここを書き換える
constexpr int problem = 0;

//ここは書き換えない
int main()
{
	std::cin.sync_with_stdio(false);
	Main(std::integral_constant<int, problem>{});
}

void Main(std::integral_constant<int, 0>)
{

}

void Main(std::integral_constant<int, 1>)
{

}

void Main(std::integral_constant<int, 2>)
{

}

void Main(std::integral_constant<int, 3>)
{

}

void Main(std::integral_constant<int, 4>)
{

}