結果

問題 No.2709 1975 Powers
ユーザー 094094
提出日時 2024-03-31 15:06:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 21,047 bytes
コンパイル時間 2,030 ms
コンパイル使用メモリ 174,804 KB
実行使用メモリ 718,848 KB
最終ジャッジ日時 2024-09-30 20:16:31
合計ジャッジ時間 22,183 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 418 ms
216,064 KB
testcase_03 AC 699 ms
355,712 KB
testcase_04 MLE -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 124 ms
69,760 KB
testcase_08 WA -
testcase_09 MLE -
testcase_10 AC 132 ms
74,368 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 MLE -
testcase_14 AC 367 ms
199,680 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 MLE -
testcase_20 WA -
testcase_21 WA -
testcase_22 MLE -
testcase_23 MLE -
testcase_24 WA -
testcase_25 MLE -
testcase_26 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff #

#if !__INCLUDE_LEVEL__
#include __FILE__

using namespace std;
using namespace m9;

long long modpow(long long a, long long b, long long mod)
{
	a %= mod;
	long long r = 1;
	while(b)
	{
		r = r * ((b % 2) ? a : 1) % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return r;
}

long long modinv(long long a, long long mod)
{
	return modpow(a, mod - 2, mod);
}


int main()
{
	LL(n, p, q);
	VLL(a, n);
	V<vvll> dp(n + 1, vvll(5, vll(p, 0))); // dp[n][k][q]:nまで見て、k個使ってあまりがqの個数
	vi sisuu = {10, 9, 7, 5};
	dp[0][0][0] = 1;
	rep(i, 1, n + 1)
	{
		dp[i] = dp[i - 1];
		rep(j, 4)
		{
			ll m = modpow(sisuu[j], a[i - 1], p);
			rep(k, 0, p)dp[i][j + 1][(k + m) % p] += dp[i - 1][j][k];
		}
	}
	// rep(i, n + 1)rep(j, 5)dbg(dp[i][j], i, j);
	print(dp[n][4][q]);
}

#else

#include <cstdint>
#include <cassert>
#include <cmath>
#include <unistd.h>
#include <string>
#include <array>
#include <vector>
#include <set>

#define MY_FASTIO_VER2
//#define IS_OUTPUT_ONLY

namespace m9 {
	struct fastin
	{
		std::array<signed char, 1048576> _buf;
		ssize_t n_w, n_r;
	#ifdef IS_OUTPUT_ONLY
		fastin() {}
	#else
		fastin() { _do_read(); }
	#endif
		long long rd_ll() noexcept
		{
			long long ret = 0, sgn = 1;
			signed char ch = _current_char();
			while(ch == ' ' || ch == '\n')ch = _next_char();
			if(ch == '-') sgn *= -1, ch = _next_char();
			for(; '0' <= ch && ch <= '9'; ch = _next_char())
			{
				ret = (ret * 10) + ch - '0';
			}
			return sgn * ret;
		}
		double rd_dbl() noexcept
		{
			double ret{}, sgn = 1;
			signed char ch = _current_char();
			while(ch == ' ' or ch == '\n')ch = _next_char();
			if(ch == '-')sgn *= -1, ch = _next_char();
			bool foundDot = false;
			double mul = 1;
			for(; ('0' <= ch && ch <= '9') or ch == '.'; ch = _next_char())
			{
				if(ch == '.') { foundDot = true; continue; }
				if(foundDot) { ret = ret + (ch - '0') / (mul *= 10); }
				else { ret = (ret * 10) + ch - '0'; }
			}
			return sgn * ret;
		}
		int rd_int() noexcept
		{
			long long _result = rd_ll();
			assert(-2147483648ll <= _result && _result <= 2147483647ll);
			return static_cast<int>(_result);
		}
		std::string rd_str() noexcept
		{
			std::string _res{};
			signed char ch = _current_char();
			while(ch == ' ' || ch == '\n')ch = _next_char();
			for(; ch != -1 && ch != '\n' && ch != ' '; ch = _next_char())
			{
				_res += std::string(1, ch);
			}
			return _res;
		}
		char rd_chr() noexcept
		{
			signed char ch = _current_char();
			while(ch == ' ' || ch == '\n')ch = _next_char();
			_next_char();
			return ch;
		}
	private:
		void _do_read() noexcept
		{
			ssize_t r = read(0, &_buf[0], _buf.size());
			assert(r >= 0);
			n_w = r, n_r = 0;
		}
		inline signed char _next_char() noexcept
		{
			if(++n_r == n_w)_do_read();
			return _current_char();
		}
		inline signed char _current_char() noexcept
		{
			return (n_r == n_w ? -1 : _buf[n_r]);
		}
	} fi;

	struct fastout
	{
		unsigned _wt_double_digit = 15;
		inline void wt_bool(bool x) noexcept { putchar_unlocked(x ? '1' : '0'); }
		inline void wt_ll(long long x) noexcept
		{
			std::array<signed char, 32> _buf;
			ssize_t _siz = 0;
			if(x < 0)
			{
				x *= -1;
				putchar_unlocked('-');
			}
			if(x == 0)putchar_unlocked('0');
			while(x > 0)
			{
				_buf[_siz++] = x % 10 + '0';
				x /= 10;
			}
			while(_siz--)putchar_unlocked(_buf[_siz]);
		}
		inline void wt_int(int x) noexcept { wt_ll(static_cast<long long>(x)); }
		inline void wt_ull(unsigned long long x) noexcept
		{
			std::array<signed char, 32> _buf;
			ssize_t _siz = 0;
			if(x == 0)putchar_unlocked('0');
			while(x > 0)
			{
				_buf[_siz++] = x % 10 + '0';
				x /= 10;
			}
			while(_siz--)putchar_unlocked(_buf[_siz]);
		}
		inline void wt_chr(char x) noexcept { putchar_unlocked(x); }
		inline void wt_str(std::string x) noexcept
		{
			ssize_t _siz = static_cast<ssize_t>(x.length());
			for(ssize_t i = 0; i < _siz; i++)putchar_unlocked(x[i]);
		}
		inline void wt_dbl(double x) noexcept
		{
			int k, r = 0;
			double v = 1;
			if(x < 0)
			{
				x *= -1;
				putchar_unlocked('-');
			}
			x += 0.5 * pow(0.1, _wt_double_digit);
			while(x >= 10 * v)v *= 10, r++;
			while(r-- >= 0)
			{
				k = floor(x / v);
				if(k >= 10)k = 9;
				if(k <= -1)k = 0;
				x -= k * v;
				v *= 0.1;
				putchar_unlocked(k + '0');
			}
			if(_wt_double_digit > 0)
			{
				putchar_unlocked('.');
				v = 1;
				for(ssize_t _ = 0; _ < _wt_double_digit; _++)
				{
					v *= 0.1;
					k = floor(x / v);
					if(k >= 10)k = 9;
					if(k <= -1)k = 0;
					x -= k * v;
					putchar_unlocked(k + '0');
				}
			}
		}
	} fo;

	inline void set_digit(unsigned d) { fo._wt_double_digit = d; }
	inline void scan(int& x) noexcept { x = fi.rd_int(); }
	inline void scan(long& x) noexcept { x = (sizeof(long) == 32 ? fi.rd_int() : fi.rd_ll()); }
	inline void scan(long long& x) noexcept { x = fi.rd_ll(); }
	inline void scan(unsigned& x) noexcept
	{
		int a = fi.rd_int();
		assert(a >= 0);
		x = a;
	}
	inline void scan(unsigned long& x) noexcept
	{
		long a;
		scan(a);
		assert(a >= 0l);
		x = a;
	}
	inline void scan(unsigned long long& x) noexcept
	{
		long long a = fi.rd_ll();
		assert(a >= 0ll);
		x = a;
	}
	// inline void scan(double& x) noexcept { x = static_cast<double>(fi.rd_ll()); }
	inline void scan(double& x) noexcept { x = fi.rd_dbl(); }
	inline void scan(char& x) noexcept { x = fi.rd_chr(); }
	inline void scan(std::string& x) noexcept { x = fi.rd_str(); }
	template <class T, class U>
	inline void scan(std::pair<T, U>& x) { scan(x.first); scan(x.second); }
	template <class T>
	inline void scan(std::vector<T>& x) { for(auto& e : x)scan(e); }
	void IN() {}
	template <class Car, class... Cdr>
	void IN(Car&& car, Cdr &&...cdr)
	{
		scan(car);
		IN(std::forward<Cdr>(cdr)...);
	}

	inline void wt_any(const bool& x) noexcept { fo.wt_bool(x); }
	inline void wt_any(const int& x) noexcept { fo.wt_int(x); }
	inline void wt_any(const long& x) noexcept { fo.wt_ll(static_cast<long>(x)); }
	inline void wt_any(const long long& x) noexcept { fo.wt_ll(x); }
	inline void wt_any(const unsigned& x) noexcept { fo.wt_ull(static_cast<unsigned long long>(x)); }
	inline void wt_any(const unsigned long& x) noexcept { fo.wt_ull(static_cast<unsigned long long>(x)); }
	inline void wt_any(const unsigned long long& x) noexcept { fo.wt_ull(x); }
	inline void wt_any(const double& x) noexcept { fo.wt_dbl(x); }
	inline void wt_any(const long double& x) noexcept { fo.wt_dbl(x); }
	inline void wt_any(const char& x) noexcept { fo.wt_chr(x); }
	inline void wt_any(const char x[]) noexcept
	{
		size_t _siz = 0;
		while(x[_siz] != '\0')fo.wt_chr(x[_siz++]);
	}
	inline void wt_any(const std::string& x) noexcept { fo.wt_str(x); }
	template <class T, class U>
	inline void wt_any(const std::pair<T, U>& x)
	{
		wt_any(x.first);
		wt_any(' ');
		wt_any(x.second);
	}
	template <class T>
	inline void wt_any(const std::vector<T>& x)
	{
		ssize_t _siz = x.size();
		for(ssize_t i = 0; i < _siz - 1; i++)wt_any(x[i]), wt_any(' ');
		if(not x.empty())wt_any(x.back());
	}
	template <class T>
	inline void wt_any(const std::set<T>& x)
	{
		for(const auto& e : x)wt_any(e), wt_any(' ');
	}

	int print() { wt_any('\n'); return 0; }
	template <class T>
	int print(const T& t)
	{
		wt_any(t);
		wt_any('\n');
		return 0;
	}
	template <class T>
	int print(const std::vector<std::vector<T>>& x)
	{
		for(const auto& v : x)print(v);
		return 0;
	}
	template <class Car, class... Cdr>
	int print(const Car& car, const Cdr &...cdr)
	{
		wt_any(car);
		wt_any(' ');
		print(cdr...);
		return 0;
	}
	template <class T>
	int wt(const T& t)
	{
		wt_any(t);
		return 0;
	}
	template <class Car, class... Cdr>
	int wt(const Car& car, const Cdr &...cdr)
	{
		wt_any(car);
		wt(cdr...);
		return 0;
	}
	void yn(bool fl = true) { print(fl ? "Yes" : "No"); }
	template <class... T>
	void drop(const T&... x) { print(x...); exit(0); }
	void dyn(bool fl = true) { print(fl ? "Yes" : "No"); exit(0); }
} // namespace m9

#define INT(...)  int __VA_ARGS__; IN(__VA_ARGS__)
#define LL(...)  long long __VA_ARGS__; IN(__VA_ARGS__)
#define ULL(...)  unsigned long long __VA_ARGS__; IN(__VA_ARGS__)
#define STR(...)  std::string __VA_ARGS__; IN(__VA_ARGS__)
#define CHR(...)  char __VA_ARGS__; IN(__VA_ARGS__)
#define DBL(...)  double __VA_ARGS__; IN(__VA_ARGS__)

namespace m9 {
	using ll = long long;
	using ull = unsigned long long;
	using pii = std::pair<int, int>;
	using pll = std::pair<ll, ll>;
} // namespace m9

#define VEC(a, type, n) std::vector<type> (a)(n); IN(a)
#define VVEC(a, type, h, w) std::vector<std::vector<type>> (a)(h, std::vector<type>(w)); IN(a)

#define VI(a, n) VEC(a, int, n)
#define VVI(a, h, w) VVEC(a, int, h, w)
#define VPII(a, n) VEC(a, pii, n)
#define VVPII(a, h, w) VVEC(a, pii, h, w)
#define VLL(a, n) VEC(a, ll, n)
#define VVLL(a, h, w) VVEC(a, ll, h, w)
#define VPLL(a, n) VEC(a, pll, n)
#define VVPLL(a, h, w) VVEC(a, pll, h, w)
#define VULL(a, n) VEC(a, ull, n)
#define VVULL(a, h, w) VVEC(a, ull, h, w)
#define VC(a, n) VEC(a, char, n)
#define VVC(a, h, w) VVEC(a, char, h, w)
#define VD(a, n) VEC(a, double, n)
#define VVD(a, h, w) VVEC(a, double, h, w)
#define VS(a, n) VEC(a, std::string, n)

#include <iostream>

namespace m9 {
#define MY_MODINT
	template <long long Mod> struct modInt {
		long long x;
		constexpr modInt() noexcept : x() {}
		template <class T>
		constexpr modInt(T v = 0) noexcept : x(v% Mod) { if(x < 0)x += Mod; }
		constexpr long long val() const noexcept { return x; }
		constexpr modInt operator-() const noexcept { return x ? Mod - x : 0; }
		constexpr modInt operator+(const modInt& r) const noexcept { return modInt(*this) += r; }
		constexpr modInt operator-(const modInt& r) const noexcept { return modInt(*this) -= r; }
		constexpr modInt operator*(const modInt& r) const noexcept { return modInt(*this) *= r; }
		constexpr modInt operator/(const modInt& r) const noexcept { return modInt(*this) /= r; }
		constexpr modInt& operator+=(const modInt& r) noexcept { x += r.x; if(x >= Mod)x -= Mod; return *this; }
		constexpr modInt& operator-=(const modInt& r) noexcept { x -= r.x; if(x < 0)x += Mod; return *this; }
		constexpr modInt& operator*=(const modInt& r) noexcept { x = x * r.x % Mod; return *this; }
		constexpr modInt& operator/=(const modInt& r) noexcept { x = x * r.inv().val() % Mod; return *this; }
		constexpr modInt powm(long long n) noexcept
		{
			if(n < 0)return powm(-n).inv();
			modInt x = *this, r = 1;
			for(; n; x *= x, n >>= 1)if(n & 1)r *= x;
			return r;
		}
		constexpr modInt inv() const noexcept
		{
			long long a = x, b = Mod, u = 1, v = 0;
			while(b)
			{
				long long t = a / b;
				a -= t * b;
				std::swap(a, b);
				u -= t * v;
				std::swap(u, v);
			}
			return modInt(u);
		}
		constexpr modInt comb(long long a) noexcept
		{
			modInt n = *this, s = 1;
			for(int i = 0; i < a; i++)s *= (n - modInt(i));
			modInt m = 1;
			for(int i = 1; i <= a; i++)m *= modInt(i);
			return s * m.powm(Mod - 2);
		}
		constexpr bool operator==(const modInt& r) { return this->x == r.x; }
		constexpr bool operator!=(const modInt& r) { return this->x != r.x; }
		friend std::ostream& operator<<(std::ostream& os, const modInt<Mod>& a) { return os << a.x; }
		friend std::istream& operator>>(std::istream& is, modInt<Mod>& a)
		{
			long long v;
			is >> v;
			a = modInt<Mod>(v);
			return is;
		}
	};

	template <long long M> inline void wt_any(const modInt<M>& x) { wt_any(x.val()); }

	using mint1000000007 = modInt<1000000007>;
	using mint998244353 = modInt<998244353>;
	mint1000000007 operator"" _m107(unsigned long long x) { return mint1000000007(x); }
	mint998244353 operator"" _m998(unsigned long long x) { return mint998244353(x); }

	struct cent_t {
	private:
		__int128_t N;
	public:
		template <class T>
		constexpr cent_t(T n) : N(static_cast<__int128_t>(n)) {}
		friend std::ostream& operator<<(std::ostream& os, const cent_t& a)
			{ if(a.N > INT64_MAX)return os << "too big integer"; else return os << static_cast<long long>(a.N); }
		friend std::istream& operator>>(std::istream& is, cent_t& a)
			{ long long tmp{}; is >> tmp; a.N = static_cast<__int128_t>(tmp); return is; }
		constexpr __int128_t val() const noexcept { return N; }
		constexpr cent_t operator-() const noexcept { return -N; }
		template <class INTEGER> constexpr cent_t operator+(const INTEGER& x) const noexcept { return N + x.N; }
		template <class INTEGER> constexpr cent_t operator-(const INTEGER& x) const noexcept { return N - x.N; }
		template <class INTEGER> constexpr cent_t operator*(const INTEGER& x) const noexcept { return N * x.N; }
		template <class INTEGER> constexpr cent_t operator/(const INTEGER& x) const noexcept { return N / x.N; }
		template <class INTEGER> constexpr cent_t operator<<(const INTEGER& x) const noexcept { return N << x; }
		template <class INTEGER> constexpr cent_t operator>>(const INTEGER& x) const noexcept { return N >> x; }
		template <class INTEGER> constexpr cent_t operator+=(const INTEGER& x) noexcept { N += x.N; return *this; }
		template <class INTEGER> constexpr cent_t operator-=(const INTEGER& x) noexcept { N -= x.N; return *this; }
		template <class INTEGER> constexpr cent_t operator*=(const INTEGER& x) noexcept { N *= x.N; return *this; }
		template <class INTEGER> constexpr cent_t operator/=(const INTEGER& x) noexcept { N /= x.N; return *this; }
		template <class INTEGER> constexpr cent_t operator<<=(const INTEGER& x) const noexcept { N <<= x.N; return *this; }
		template <class INTEGER> constexpr cent_t operator>>=(const INTEGER& x) const noexcept { N >>= x.N; return *this; }
		constexpr cent_t operator++() noexcept { N += 1; return *this; }
		constexpr cent_t operator--() noexcept { N -= 1; return *this; }
		template <class INTEGER> constexpr bool operator==(const INTEGER& x) { return this->N == x.N; }
		template <class INTEGER> constexpr bool operator!=(const INTEGER& x) { return this->N != x.N; }
		template <class INTEGER> constexpr bool operator<(const INTEGER& x) { return this->N < x.N; }
		template <class INTEGER> constexpr bool operator>(const INTEGER& x) { return this->N > x.N; }
		template <class INTEGER> constexpr bool operator<=(const INTEGER& x) { return this->N <= x.N; }
		template <class INTEGER> constexpr bool operator>=(const INTEGER& x) { return this->N >= x.N; }
	};

	using i8 = signed char;
	using u8 = unsigned char;
	using i32 = signed int;
	using u32 = unsigned int;
	using i64 = signed long long;
	using u64 = unsigned long long;

	i8 operator"" _i8(unsigned long long x) { return static_cast<i8>(x); }
	u8 operator"" _u8(unsigned long long x) { return static_cast<u8>(x); }
	i32 operator"" _i32(unsigned long long x) { return static_cast<i32>(x); }
	u32 operator"" _u32(unsigned long long x) { return static_cast<u32>(x); }
	i64 operator"" _i64(unsigned long long x) { return static_cast<i64>(x); }
	u64 operator"" _u64(unsigned long long x) { return static_cast<u64>(x); }
	cent_t operator"" _i128(unsigned long long x) { return cent_t(x); }

	using f32 = float;
	using f64 = double;
	double operator"" _f32(unsigned long long x) { return static_cast<f32>(x); }
	double operator"" _f64(unsigned long long x) { return static_cast<f64>(x); }
} // namespace m9

#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
// #include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstdint>
#include <cstring>
#include <ctime>
#include <chrono>
// #include <bit>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>
#include <random>
#include <regex>
//#define INCLUDE_BOOST
#ifdef INCLUDE_BOOST
#if __has_include(<boost/range/irange.hpp>)
#include <boost/range/irange.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/algorithm/string/classification.hpp>
#endif
#endif
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,fma,abm,mmx,avx,avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define all(x) std::begin(x), std::end(x)
#define Sort(x) sort(all(x))
#define rSort(x) sort(all(x)); reverse(all(x))
#define UNIQUE(v) v.erase(unique(all(v)), v.end())
#define uniq(v) sort(all(v)); UNIQUE(v)
#define l_b(c, x) distance(begin(c), lower_bound(all(c), (x)))
#define u_b(c, x) distance(begin(c), upper_bound(all(c), (x)))
#define fi first
#define se second
#define m_p make_pair
#define m_t make_tuple
#define pb push_back
#define eb emplace_back
#define cauto const auto&
#define _rep_overload(_1, _2, _3, _4, name, ...) name
#define _rep1(i, n) _rep2(i, 0, n)
#define _rep2(i, a, b) for(ll i = (a); i < (b); i++)
#define _rep3(i, a, b, c) for(ll i = (a); i < (b); i += c)
#define rep(...) _rep_overload(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__)
#define myceil(a, b) ((a) + ((b) - 1)) / (b)
#define continue_with(...) ({__VA_ARGS__; continue;})
#define break_with(...) ({__VA_ARGS__; break;})

namespace m9 {
	using ll = long long;
	using ull = unsigned long long;
	using pii = std::pair<int, int>;
	using pll = std::pair<ll, ll>;
} // namespace m9

namespace m9 {
	template <class T> using V = std::vector<T>;
	using vb = V<std::int8_t>;
	using vi = V<int>;
	using vu = V<unsigned>;
	using vll = V<ll>;
	using vull = V<ull>;
	using vd = V<double>;
	using vc = V<char>;
	using vs = V<std::string>;
	using vpii = V<pii>;
	using vpll = V<pll>;

	using vvb = V<vb>;
	using vvi = V<vi>;
	using vvu = V<vu>;
	using vvll = V<vll>;
	using vvull = V<vull>;
	using vvd = V<vd>;
	using vvc = V<vc>;
	using vvs = V<vs>;
	using vvpii = V<vpii>;
	using vvpll = V<vpll>;

	template <class T>
	inline bool chmin(T& a, const T& b) { if(b < a) { a = b; return true; } return false; }
	template <class T>
	inline bool chmax(T& a, const T& b) { if(a < b) { a = b; return true; } return false; }

	ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
	ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
	ll fact(ll n, ll m) { ll f = n; for(ll i = n - 1; i >= 1; i--) { f *= i; if(m != -1)f %= m; } return f; }

	constexpr ll inf = 0x1fffffffffffffff;
	constexpr ll mod = 1000000007LL;
	constexpr ll mod2 = 998244353LL;
	constexpr double eps = 1e-8;
	constexpr double pi = 3.141592653589793238462643383279;
} // namespace m9

namespace m9 {
	struct sorted_operator {
		template <class T> friend std::vector<T> operator>>(std::vector<T>a, sorted_operator)
			{ std::sort(std::begin(a), std::end(a)); return a; }
		friend std::string operator>>(std::string a, sorted_operator)
			{ std::sort(std::begin(a), std::end(a)); return a; }
	} Sor;
	struct reversed_operator {
		template <class T> friend std::vector<T> operator>>(std::vector<T> a, reversed_operator)
			{ std::reverse(std::begin(a), std::end(a)); return a; }
		friend std::string operator>>(std::string a, reversed_operator)
			{ std::reverse(std::begin(a), std::end(a)); return a; }
	} Rev;
	struct unique_operator {
		template <class T> friend std::vector<T> operator>>(std::vector<T> a, unique_operator)
			{ a.erase(unique(std::begin(a), std::end(a)), std::end(a)); return a; }
		friend std::string operator>>(std::string a, unique_operator)
			{ a.erase(unique(std::begin(a), std::end(a)), std::end(a)); return a; }	
	} Set;
	template <class T>
	void INCVEC(std::vector<T>& a) { for(T& e : a)e++; }
	template <class T>
	void DECVEC(std::vector<T>& a) { for(T& e : a)e--; }
	struct inc_operator {
		template <class T> friend std::vector<T> operator>>(std::vector<T> a, inc_operator)
			{ INCVEC(a); return a; }
	} Inc;
	struct dec_operator {
		template <class T> friend std::vector<T> operator>>(std::vector<T> a, dec_operator)
			{ DECVEC(a); return a; }
	} Dec;
	template <class T, class F>
	auto operator>> (std::vector<T> a, F f) -> std::vector<decltype(f(a.front()))>
	{
		std::vector<decltype(f(a.front()))> res{};
		for(const T& e : a)res.emplace_back(f(e));
		return res;
	}
} // namespace m9

// debug

#ifdef ONLINE_JUDGE
#define dbg(...) void(0)
#else
#define dbg(...) _debug(#__VA_ARGS__, __VA_ARGS__)
#endif

namespace m9 {
	template <class Car, class... Cdr>
	void _debug(const char* s, Car&& car, Cdr&&... cdr)
	{
		constexpr const char* open_br = sizeof...(cdr) == 0 ? "" : "(";
		constexpr const char* close_br = sizeof...(cdr) == 0 ? "" : ")";
#ifdef MY_FASTIO_VER2
		wt_any(open_br); wt_any(s); wt_any(close_br);
		wt_any(" : ");
		wt_any(open_br); wt_any(std::forward<Car>(car));
		((wt_any(", "), wt_any(std::forward<Cdr>(cdr))), ...);
		wt_any(close_br); wt_any("\n");
#else
		std::cerr << open_br << s << close_br << " : " << open_br << std::forward<Car>(car);
		((std::cerr << ", " << std::forward<Cdr>(cdr)), ...);
		std::cerr << close_br << "\n";
#endif
	}
} // namespace m9

#endif
0