Submission #979080


Source Code Expand

//ここからテンプレート
//#define PLASMA_NO_BOOST
#if 1

#include<iostream>
#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>
#include<numeric>
#include<iomanip>
#include<vector>
#include<queue>
#include<random>
#include<map>
#include<chrono>
#include<stack>
#include<set>

#ifndef PLASMA_NO_BOOST
#include<boost/optional.hpp>
#include<boost/optional/optional_io.hpp>
#include<boost/variant.hpp>
#include<boost/range/adaptor/transformed.hpp>
#include<boost/range/adaptor/indexed.hpp>
#include<boost/range/adaptor/filtered.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/irange.hpp>
#include<boost/multi_array.hpp>
#include<boost/preprocessor.hpp>
#endif

typedef long long int int64;
typedef unsigned long long uint64;
typedef long double double64;

#ifdef PLASMA_NO_BOOST
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));
}
#else
using boost::optional;
using boost::none_t;
using boost::none;
#endif

#ifndef PLASMA_NO_BOOST
namespace adaptor
{
	using namespace boost::adaptors;
}
namespace algorithm
{
	using namespace boost::range;
	template<class SinglePassRange, class Pred>bool any_of(SinglePassRange const& range, Pred pred)
	{
		return std::any_of(std::begin(range), std::end(range), pred);
	}
	template<class SinglePassRange, class Pred>bool all_of(SinglePassRange const& range, Pred pred)
	{
		return std::all_of(std::begin(range), std::end(range), pred);
	}
}
#endif
namespace math
{
	template<class T>constexpr T pow(T p, int n)
	{
		return n == 0 ? T(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)
	{
		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);
	}

	void fourier_transform(
		std::vector<std::complex<double>>& vec, std::size_t N)
	{
		std::vector<std::complex<double>> butterfly;
		vec.resize(N);
		butterfly.resize(N);

		std::complex<double> half(std::cos(pi), std::sin(pi));
		for (uint64 i = 1, k = N / 2;i < N;[&]() {i *= 2;k /= 2;}())//i*k == N/4
		{
			std::complex<double> circle(std::cos(pi / i), std::sin(pi / i));
			std::complex<double> c(1.0, 0);
			for (auto count = 0ull; count < i;++count)
			{
				for (auto j = 0ull;j < k;++j)
				{
					butterfly[count*k + j] =
						vec[2 * count*k + j] + vec[2 * count*k + j + k] * c;
					butterfly[count*k + j + N / 2] =
						vec[2 * count*k + j] + vec[2 * count*k + j + k] * c*half;
				}
				c *= circle;
			}
			std::swap(vec, butterfly);
		}
	}

	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(std::complex<double> c) :polynomial({ c }) {}

		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()
		{
			std::size_t N = degree();
			for (;N > 0;--N)
			{
				if (value[N] != 0.0)
					break;
			}
			value.resize(N + 1);
		}
		void integer_degree_set()
		{
			std::size_t N = degree();
			for (;N > 0;--N)
			{
				std::cout << value[N] << " " << (std::norm(value[N]) > (1.0e-20)) << std::endl;
				if (std::norm(value[N]) > (1.0e-20))
					break;
			}
			value.resize(N + 1);
		}

		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_ = lhs.value;
			auto rhs_ = rhs.value;
			fourier_transform(lhs_, N);
			fourier_transform(rhs_, N);
			std::vector<std::complex<double>> vec;
			vec.reserve(N);
			for (std::size_t i = 0;i < N;++i)
			{
				vec.push_back(lhs_[i] * rhs_[i]);
			}
			for (auto& v : vec)
			{
				v = 2 * v.real() - v;
			}
			fourier_transform(vec, N);
			for (auto& v : vec)
			{
				v = (2 * v.real() - v)*(1.0 / N);
			}
			std::size_t k = N;
			for (;k > 0;--k)
			{
				if (std::norm(vec[k]) > 1.0e-23)
					break;
			}
			vec.resize(k + 1);
			return polynomial(std::move(vec));
		}
	};

	int real_integer(std::complex<double> c)
	{
		int v = static_cast<int>(c.real());
		double u = c.real() - v;
		return v + static_cast<int>(2 * u);
	}

	template<class T>polynomial make_poly(std::vector<T> const& vec)
	{
		auto range = vec | adaptor::transformed([](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));
	}
	polynomial make_poly(std::initializer_list<double>init)
	{
		std::vector<std::complex<double>> vec;
		for (auto v : init)
		{
			vec.emplace_back(v);
		}
		return polynomial(std::move(vec));
	}
	polynomial make_poly(std::initializer_list<int> init)
	{
		std::vector<std::complex<double>> vec;
		for (auto v : init)
		{
			vec.emplace_back(v);
		}
		return polynomial(std::move(vec));
	}
	template<class T>class infinite_value
	{
		optional<T> val;
	public:
		infinite_value(T const& v) :val(v) {}
		infinite_value(T&& v) :val(std::move(v)) {}
		infinite_value(none_t = none) :val() {}
		infinite_value(infinite_value const&) = default;
		infinite_value(infinite_value&&) = default;
		~infinite_value() = default;

		infinite_value& operator=(T const& v)
		{
			val = v;
			return *this;
		}
		infinite_value& operator=(T&& v)
		{
			val = std::move(v);
			return *this;
		}
		infinite_value& operator=(none_t)
		{
			val = boost::none;
			return *this;
		}
		infinite_value& operator=(infinite_value const&) = default;
		infinite_value& operator=(infinite_value&&) = default;

		operator bool()const
		{
			return static_cast<bool>(val);
		}
		T const& operator*()const
		{
			return *val;
		}

		friend infinite_value operator+(infinite_value const& lhs, infinite_value const& rhs)
		{
			return lhs&&rhs ? infinite_value<T>(*lhs + *rhs) : infinite_value<T>(none);
		}
		friend infinite_value operator+(infinite_value const& lhs, T const& rhs)
		{
			return lhs ? infinite_value<T>(*lhs + rhs) : infinite_value<T>(none);
		}
		friend infinite_value operator+(T const& lhs, infinite_value const& rhs)
		{
			return lhs&&rhs ? infinite_value<T>(*lhs + *rhs) : infinite_value<T>(none);
		}

		friend bool operator==(infinite_value const& lhs, infinite_value const& rhs)
		{
			return (!lhs && !rhs) || (lhs&&rhs && (*lhs == *rhs));
		}
		friend bool operator==(infinite_value const& lhs, T const& rhs)
		{
			return lhs && (*lhs == rhs);
		}
		friend bool operator==(T const& lhs, infinite_value const& rhs)
		{
			return rhs && (lhs == *rhs);
		}


		friend bool operator<(infinite_value const& lhs, infinite_value const& rhs)
		{
			return !lhs ? false : !rhs ? true : *lhs < *rhs;
		}
		friend bool operator<(infinite_value const& lhs, T const& rhs)
		{
			return !lhs ? false : *lhs < rhs;
		}
		friend bool operator<(T const& lhs, infinite_value const& rhs)
		{
			return !rhs ? true : lhs < *rhs;
		}
		friend bool operator<=(infinite_value const& lhs, infinite_value const& rhs)
		{
			return (lhs < rhs) || (lhs == rhs);
		}
		friend bool operator<=(infinite_value const& lhs, T const& rhs)
		{
			return (lhs < rhs) || (lhs == rhs);
		}
		friend bool operator<=(T const& lhs, infinite_value const& rhs)
		{
			return (lhs < rhs) || (lhs == rhs);
		}


		friend bool operator>(infinite_value const& lhs, infinite_value const& rhs)
		{
			return  !rhs ? false : !lhs ? true : *lhs > *rhs;
		}
		friend bool operator>(infinite_value const& lhs, T const& rhs)
		{
			return !lhs ? true : *lhs > rhs;
		}
		friend bool operator>(T const& lhs, infinite_value const& rhs)
		{
			return !rhs ? false : lhs > *rhs;
		}
		friend bool operator>=(infinite_value const& lhs, infinite_value const& rhs)
		{
			return (lhs > rhs) || (lhs == rhs);
		}
		friend bool operator>=(infinite_value const& lhs, T const& rhs)
		{
			return (lhs > rhs) || (lhs == rhs);
		}
		friend bool operator>=(T const& lhs, infinite_value const& rhs)
		{
			return (lhs > rhs) || (lhs == rhs);
		}

	};
	template<std::size_t Mod>class modulo_number
	{
		uint64 val = {};
		static constexpr uint64 abs(int64 n)
		{
			return n <= -1 ? n + Mod : n;
		}
	public:
		modulo_number(modulo_number const&) = default;
		modulo_number(modulo_number&&) = default;
		modulo_number& operator=(modulo_number const&) = default;
		modulo_number& operator=(modulo_number&&) = default;
		~modulo_number() = default;

		constexpr modulo_number(uint64 num = {}) : val(num%Mod) {}
		constexpr modulo_number(unsigned int num) : val(num%Mod) {}
		constexpr modulo_number(int64 num) : val(abs(num%Mod)) {}
		constexpr modulo_number(int num) : val(abs(num%Mod)) {}

		modulo_number& operator=(uint64 num)
		{
			val = num%Mod;
			return *this;
		}
		modulo_number& operator=(int64 num)
		{
			val = abs(num%Mod);
			return *this;
		}
		modulo_number& operator=(unsigned int num)
		{
			val = num%Mod;
			return *this;
		}
		modulo_number& operator=(int num)
		{
			val = abs(num%Mod);
			return *this;
		}


		constexpr uint64 get()const
		{
			return val;
		}

		friend constexpr modulo_number<Mod> operator+(modulo_number<Mod>const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>((lhs.val + rhs.val) % Mod);
		}
		friend constexpr modulo_number<Mod> operator+(modulo_number<Mod>const& lhs, int const& rhs)
		{
			return lhs + modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator+(modulo_number<Mod>const& lhs, unsigned int const& rhs)
		{
			return lhs + modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator+(modulo_number<Mod>const& lhs, int64 const& rhs)
		{
			return lhs + modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator+(modulo_number<Mod>const& lhs, uint64 const& rhs)
		{
			return lhs + modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator+(int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) + rhs;
		}
		friend constexpr modulo_number<Mod> operator+(unsigned int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) + rhs;
		}
		friend constexpr modulo_number<Mod> operator+(int64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) + rhs;
		}
		friend constexpr modulo_number<Mod> operator+(uint64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) + rhs;
		}

		friend constexpr modulo_number<Mod> operator-(modulo_number<Mod>const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>((lhs.val + Mod - rhs.val) % Mod);
		}
		friend constexpr modulo_number<Mod> operator-(modulo_number<Mod>const& lhs, int const& rhs)
		{
			return lhs - modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator-(modulo_number<Mod>const& lhs, unsigned int const& rhs)
		{
			return lhs - modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator-(modulo_number<Mod>const& lhs, int64 const& rhs)
		{
			return lhs - modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator-(modulo_number<Mod>const& lhs, uint64 const& rhs)
		{
			return lhs - modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator-(int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) - rhs;
		}
		friend constexpr modulo_number<Mod> operator-(unsigned int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) - rhs;
		}
		friend constexpr modulo_number<Mod> operator-(int64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) - rhs;
		}
		friend constexpr modulo_number<Mod> operator-(uint64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) - rhs;
		}

		friend constexpr modulo_number<Mod> operator*(modulo_number<Mod>const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>((lhs.val*rhs.val) % Mod);
		}
		friend constexpr modulo_number<Mod> operator*(modulo_number<Mod>const& lhs, int const& rhs)
		{
			return lhs * modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator*(modulo_number<Mod>const& lhs, unsigned int const& rhs)
		{
			return lhs * modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator*(modulo_number<Mod>const& lhs, int64 const& rhs)
		{
			return lhs * modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator*(modulo_number<Mod>const& lhs, uint64 const& rhs)
		{
			return lhs * modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator*(int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) * rhs;
		}
		friend constexpr modulo_number<Mod> operator*(unsigned int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) * rhs;
		}
		friend constexpr modulo_number<Mod> operator*(int64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) * rhs;
		}
		friend constexpr modulo_number<Mod> operator*(uint64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) * rhs;
		}

		friend constexpr modulo_number<Mod> operator/(modulo_number<Mod>const& lhs, modulo_number<Mod>const& rhs)
		{
			return lhs*math::pow(rhs, Mod - 2);
		}
		friend constexpr modulo_number<Mod> operator/(modulo_number<Mod>const& lhs, int const& rhs)
		{
			return lhs / modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator/(modulo_number<Mod>const& lhs, unsigned int const& rhs)
		{
			return lhs / modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator/(modulo_number<Mod>const& lhs, int64 const& rhs)
		{
			return lhs / modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator/(modulo_number<Mod>const& lhs, uint64 const& rhs)
		{
			return lhs / modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator/(int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) / rhs;
		}
		friend constexpr modulo_number<Mod> operator/(unsigned int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) / rhs;
		}
		friend constexpr modulo_number<Mod> operator/(int64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) / rhs;
		}
		friend constexpr modulo_number<Mod> operator/(uint64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) / rhs;
		}

		template<class Rhs>decltype(auto) operator+=(Rhs const& rhs)
		{
			return *this = *this + rhs;
		}
		template<class Rhs>decltype(auto) operator*=(Rhs const& rhs)
		{
			return *this = *this * rhs;
		}
		template<class Rhs>decltype(auto) operator-=(Rhs const& rhs)
		{
			return *this = *this - rhs;
		}
		template<class Rhs>decltype(auto) operator/=(Rhs const& rhs)
		{
			return *this = *this / rhs;
		}
	};

	template<class T>constexpr T factorial(std::size_t n, std::size_t goal = 1)
	{
		return n == goal ? T(n) : n == 0 ? T(1) : factorial<T>(n, (n + goal) / 2 + 1)*factorial<T>((n + goal) / 2, goal);
	}

	namespace detail
	{
		constexpr uint64 integral_sqrt_i(uint64 v, uint64 start, uint64 end)
		{
			return start == end ? start :
				pow((start + end) / 2 + 1, 2) <= v ?
				integral_sqrt_i(v, (start + end) / 2 + 1, end) :
				integral_sqrt_i(v, start, (start + end) / 2);
		}
	}

	constexpr uint64 integral_sqrt(uint64 v)
	{
		return v == 0 ? 0 :
			v == 1 ? 1 :
			detail::integral_sqrt_i(v, 1, 0b100000000000000000000000000000000ull);
	}

	namespace detail
	{
		constexpr bool is_prime_i(uint64 v, uint64 start, uint64 end)
		{
			return start == end ? v%end != 0 :
				is_prime_i(v, start, (start + end) / 2) &&
				is_prime_i(v, (start + end) / 2 + 1, end);
		}
	}

	constexpr bool is_prime(uint64 v)
	{
		return v == 0 ? false :
			v == 1 ? false :
			v == 2 ? true :
			v == 3 ? true : detail::is_prime_i(v, 2, integral_sqrt(v));
	}

	class dynamic_modulo
	{
		uint64 value;
		uint64 mod;
		static constexpr uint64 abs(int64 v, uint64 mod)
		{
			return v <= -1 ? v + mod : v;
		}
	public:
		constexpr dynamic_modulo() :value(), mod(2) {}
		constexpr dynamic_modulo(uint64 v, uint64 m) : value(v), mod(m) {}
		dynamic_modulo(dynamic_modulo const&) = default;
		dynamic_modulo(dynamic_modulo&&) = default;
		dynamic_modulo& operator=(dynamic_modulo const&) = default;
		dynamic_modulo& operator=(dynamic_modulo&&) = default;
		~dynamic_modulo() = default;

		constexpr uint64 get()const
		{
			return value;
		}

		constexpr friend auto operator+(dynamic_modulo const& lhs, dynamic_modulo const& rhs)
		{
			return lhs.mod != rhs.mod ?
				throw std::logic_error("math::dynamic_modulo mod number error") :
				dynamic_modulo((lhs.value + rhs.value) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator+(dynamic_modulo const& lhs, uint64 const& rhs)
		{
			return dynamic_modulo((lhs.value + rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator+(dynamic_modulo const& lhs, int64 const& rhs)
		{
			return dynamic_modulo(abs((lhs.value + rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator+(dynamic_modulo const& lhs, unsigned int const& rhs)
		{
			return dynamic_modulo((lhs.value + rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator+(dynamic_modulo const& lhs, int const& rhs)
		{
			return dynamic_modulo(abs((lhs.value + rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator+(uint64 const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo((lhs.value + rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator+(int64 const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value + rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator+(unsigned int const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo((lhs.value + rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator+(int const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value + rhs) % lhs.mod, lhs.mod), lhs.mod);
		}

		constexpr friend auto operator*(dynamic_modulo const& lhs, dynamic_modulo const& rhs)
		{
			return lhs.mod != rhs.mod ?
				throw std::logic_error("math::dynamic_modulo mod number error") :
				dynamic_modulo((lhs.value * rhs.value) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator*(dynamic_modulo const& lhs, uint64 const& rhs)
		{
			return dynamic_modulo((lhs.value * rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator*(dynamic_modulo const& lhs, int64 const& rhs)
		{
			return dynamic_modulo(abs((lhs.value * rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator*(dynamic_modulo const& lhs, unsigned int const& rhs)
		{
			return dynamic_modulo((lhs.value * rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator*(dynamic_modulo const& lhs, int const& rhs)
		{
			return dynamic_modulo(abs((lhs.value * rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator*(uint64 const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo((lhs.value * rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator*(int64 const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value * rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator*(unsigned int const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo((lhs.value * rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator*(int const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value * rhs) % lhs.mod, lhs.mod), lhs.mod);
		}

		constexpr friend auto operator-(dynamic_modulo const& lhs, dynamic_modulo const& rhs)
		{
			return lhs.mod != rhs.mod ?
				throw std::logic_error("math::dynamic_modulo mod number error") :
				dynamic_modulo(abs((lhs.value - rhs.value) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(dynamic_modulo const& lhs, uint64 const& rhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(dynamic_modulo const& lhs, int64 const& rhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(dynamic_modulo const& lhs, unsigned int const& rhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(dynamic_modulo const& lhs, int const& rhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(uint64 const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(int64 const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(unsigned int const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(int const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}

		template<class Rhs>dynamic_modulo& operator+=(Rhs const& rhs)
		{
			return *this = *this + rhs;
		}
		template<class Rhs>dynamic_modulo& operator-=(Rhs const& rhs)
		{
			return *this = *this - rhs;
		}
		template<class Rhs>dynamic_modulo& operator*=(Rhs const& rhs)
		{
			return *this = *this * rhs;
		}
	};
}
namespace geometry
{
	template<class Type>struct point
	{
		Type x, y;
	};
	template<class Type>auto make_point(Type x, Type y)
	{
		return point<Type>{x, y};
	}
	template<class Type>auto operator+(point<Type>const& lhs, point<Type>const& rhs)
	{
		return make_point(lhs.x + rhs.x, lhs.y + rhs.y);
	}
	template<class Type>auto operator-(point<Type>const& lhs, point<Type>const& rhs)
	{
		return make_point(lhs.x - rhs.x, lhs.y - rhs.y);
	}
	template<class Point>struct box
	{
		Point small, large;
	};
	template<class Point>auto make_box(Point a, Point b)
	{
		return box<Point>{
			make_point(std::min(a.x, b.x), std::min(a.y, b.y)),
				make_point(std::max(a.x, b.x), std::max(a.y, b.y))};
	}
#ifndef  PLASMA_NO_BOOST
	template<class Point>boost::optional<box<Point>> hit_check(box<Point> a, box<Point> b)
	{
		if (a.small.x > b.small.x)
			std::swap(a, b);
		if (a.large.x < b.small.x)
			return boost::none;
		auto small_x = b.small.x;
		auto large_x = std::min(b.large.x, a.large.x);
		if (a.small.y < b.small.y)
		{
			if (b.small.y < a.large.y)
				return make_box(
					make_point(small_x, b.small.y),
					make_point(large_x, std::min(a.large.y, b.large.y)));
			else
				return boost::none;
		}
		else
		{
			if (a.small.y < b.large.y)
				return make_box(
					make_point(small_x, a.small.y),
					make_point(large_x, std::min(a.large.y, b.large.y)));
			else
				return boost::none;
		}
	}
#endif
}
namespace graph_traits
{
	class graph
	{
		std::vector<int64> node_data;
		std::vector<std::vector<std::pair<int, int64>>> edge_data;
	public:
		graph() = default;
		graph(std::vector<int64>&& n) :node_data(std::move(n)), edge_data{}
		{
			edge_data.resize(node_data.size());
		}
		graph(std::size_t size) :node_data(size), edge_data{}
		{

		}

		void resize(int size)
		{
			node_data.resize(size);
			edge_data.resize(size);
		}
		void edge_reserve(int size)
		{
			for (auto& v : edge_data)
			{
				v.reserve(size);
			}
		}

		void add_node(int64 data)
		{
			node_data.emplace_back(data);
			edge_data.emplace_back();
		}
		void add_edge(int from, int to, int64 data)
		{
			edge_data[from].emplace_back(to, data);
		}
		std::vector<math::infinite_value<int64>> dijkstra(int from)const
		{
			struct compare
			{
				bool operator()(
					std::pair<int, math::infinite_value<int64>>const& lhs,
					std::pair<int, math::infinite_value<int64>>const& rhs)const
				{
					return lhs.second > rhs.second;
				}
			};
			std::priority_queue<
				std::pair<int, math::infinite_value<int64>>,
				std::vector<std::pair<int, math::infinite_value<int64>>>,
				compare>nodes;
			std::vector<math::infinite_value<int64>> ret(node_data.size());
			for (int i{};i < node_data.size();++i)
			{
				nodes.emplace(i, math::infinite_value<int64>());
			}
			nodes.emplace(from, int());

			while (nodes.size())
			{
				auto p = nodes.top();
				nodes.pop();
				if (ret[p.first] <= p.second)
					continue;
				ret[p.first] = p.second;
				for (auto const& d : edge_data[p.first])
				{
					nodes.emplace(d.first, std::min(ret[d.first], ret[p.first] + d.second));
				}
			}
			return ret;
		}

		int64 operator[](int n)const
		{
			return node_data[n];
		}
	};
}
namespace container
{
	template<class T>using p_queue = std::priority_queue<T, std::vector<T>, std::greater<T>>;
}

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>);
void Main(std::integral_constant<int, 5>);
#endif//テンプレートここまで
//ここを書き換える
constexpr int problem = 2;

//ここは書き換えない
int main()
{
	std::cin.sync_with_stdio(false);
	std::cout << std::setprecision(std::numeric_limits<long double>::digits10 + 1);
	Main(std::integral_constant<int, problem>{});
}

void Main(std::integral_constant<int, 1>)
{
	std::vector<std::string> map;
	std::vector<std::string> run;
	int H, W;
	std::cin >> H >> W;
	for (int i{};i < H;++i)
	{
		std::string str;
		std::cin >> str;
		map.emplace_back(std::move(str));
		run.emplace_back(std::string(W, '.'));
	}
	int h = 0, w = 0;
	run[0][0] = '#';
	while (h != (H - 1) || w != (W - 1))
	{
		if (h != (H - 1) && map[h + 1][w] == '#')
		{
			run[h + 1][w] = '#';
			++h;
		}
		else if (w != (W - 1) && map[h][w + 1] == '#')
		{
			run[h][w + 1] = '#';
			++w;
		}
		else
		{
			std::cout << "Impossible" << std::endl;
			return;
		}
	}
	if (map == run)
	{
		std::cout << "Possible" << std::endl;
	}
	else
	{
		std::cout << "Impossible" << std::endl;
	}
}

void Main(std::integral_constant<int, 2>)
{
	int N;
	std::cin >> N;
	std::vector<int> p(N);
	std::vector<int> a, b;
	for (int i{};i < N;++i)
	{
		int x;
		std::cin >> x;
		p[x - 1] = i;
	}
	for (int i{};i < N;++i)
	{
		a.emplace_back(N*(i + 1) + p[i]);
		b.emplace_back(N*(N - i) + p[i]);
	}
	for (auto x : a)
	{
		std::cout << x << " ";
	}
	std::cout << std::endl;
	for (auto x : b)
	{
		std::cout << x << " ";
	}
	std::cout << std::endl;
}

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

}

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

}

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

}

Submission Info

Submission Time
Task B - Construct Sequences
User plasmaeffect
Language C++14 (GCC 5.4.1)
Score 400
Code Size 30552 Byte
Status AC
Exec Time 8 ms
Memory 1024 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 22
Set Name Test Cases
Sample example0.txt, example1.txt, example2.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, example0.txt, example1.txt, example2.txt
Case Name Status Exec Time Memory
000.txt AC 3 ms 384 KB
001.txt AC 3 ms 256 KB
002.txt AC 3 ms 256 KB
003.txt AC 3 ms 256 KB
004.txt AC 3 ms 256 KB
005.txt AC 8 ms 1024 KB
006.txt AC 4 ms 384 KB
007.txt AC 8 ms 896 KB
008.txt AC 5 ms 640 KB
009.txt AC 8 ms 1024 KB
010.txt AC 8 ms 1024 KB
011.txt AC 8 ms 1024 KB
012.txt AC 8 ms 1024 KB
013.txt AC 8 ms 1024 KB
014.txt AC 8 ms 1024 KB
015.txt AC 8 ms 1024 KB
016.txt AC 8 ms 1024 KB
017.txt AC 8 ms 1024 KB
018.txt AC 8 ms 1024 KB
example0.txt AC 3 ms 256 KB
example1.txt AC 3 ms 256 KB
example2.txt AC 2 ms 256 KB