---
tags: codebook
---

# competition template

## 2021/01/12

//Input Output
#include<iostream>
#include<iomanip>
#include<fstream>
#include<sstream>
#include<streambuf>
//C lib
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<cctype>
//Container
#include<array>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<bitset>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
//Others
#include<tuple>
#include<algorithm>
#include<functional>
#include<numeric>
#include<iterator>
#include<limits>
#include<utility>
#include<complex>
#include<type_traits>
#include<initializer_list>
#include<random>

using namespace std;

#if __cplusplus > 201703L
#include<concepts>
#include<ranges>
#include<bit>
#include<numbers>
using namespace numbers;
#include<span>
#endif

void _debug() {cerr << '\n';}
template <typename A, typename... B>
void _debug(A a, B... b) {cerr << a << ' ', _debug(b...);}
#define debug(...) cerr << '(' << (#__VA_ARGS__) << ") : ", _debug(__VA_ARGS__)

namespace abb {A_ARGS__) << ") : ", _debug(__VA_ARGS__)

namespace abb {
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using Q = queue<T>;
template<typename T> using DQ = deque<T>;
template<typename T> using V2d = vector<vector<T>>;
template<typename T> using US = unordered_set<T>;
template<typename T, size_t s> using A = array<T, s>;
template<typename T1, typename T2> using UM = unordered_map<T1, T2>;
template<typename T1, typename T2 = T1> using P = pair<T1, T2>;
template<typename T, typename Cmp = less<T>> using S = set<T, Cmp>;
template<typename T, typename Cmp = less<T>> using PQ = priority_queue<T, V<T>, Cmp>;
template<typename T1, typename T2, typename Cmp = less<T1>> using M = map<T1, T2, Cmp>;
template<typename T> using F = function<T>;
}

namespace output {
template<typename T1, typename T2>
inline ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
	return os << '(' << p.first << ", " << p.second << ')';
}
#define unfold1(Container) \
template<typename T> \
inline ostream& operator<<(ostream& os, const Container<T>& x) { \
	for (const auto& i : x) \
		os << i << ' '; \
	return os; \
}
#define unfold2(Container) \
template<typename T1,typename T2> \
inline ostream& operator<<(ostream& os,const Container<T1,T2>& x){ \
	for (const auto& i : x) \
		os << i << ' '; \
	return os; \
}
unfold1(vector); unfold1(set); unfold1(deque); unfold2(map)
#undef unfold1
#undef unfold2
};

namespace rit {
struct fast_istream {
	operator bool() const {return bool(cin);}
	fast_istream() {cin.tie(nullptr);}
} fin;
#if __cplusplus > 201703L
template<typename T>
fast_istream& operator>>(fast_istream& is, T& n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
fast_istream & operator>>(fast_istream& is, T& n) {
#endif
	while (isspace(cin.rdbuf()->sgetc()))
		cin.rdbuf()->snextc();
	bool sign = false;
	if (cin.rdbuf()->sgetc() == '-')
		sign = true, cin.rdbuf()->snextc();
	for (n = 0; isdigit(cin.rdbuf()->sgetc());)
		n *= 10, n += cin.rdbuf()->sbumpc() - '0';
	n = sign ? -n : n;
	return is;
}
fast_istream& operator>>(fast_istream& is, char& n) {
	while (isspace(cin.rdbuf()->sgetc()))
		cin.rdbuf()->snextc();
	n = cin.rdbuf()->sbumpc();
	return is;
}
}

#define endl '\n'
namespace wit {
struct fast_ostream {
	operator bool() const {return bool(cout);}
	fast_ostream() {cout.tie(nullptr);}
} fout;
constexpr int buffer_size = 30;
#if __cplusplus > 201703L
template<typename T>
fast_ostream& operator<<(fast_ostream& os, T n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
fast_ostream & operator<<(fast_ostream& os, T n) {
#endif
	if (!n) {cout.rdbuf()->sputc('0'); return os;}
	if (n < 0) cout.rdbuf()->sputc('-'), n = -n;
	static char buffer[buffer_size];
	int cnt = buffer_size;
	for (; n; n /= 10)
		buffer[--cnt] = n % 10 + '0';
	cout.rdbuf()->sputn(buffer + cnt, buffer_size - cnt);
	return os;
}
fast_ostream& operator<< (fast_ostream& os, const char& n) {
	cout.rdbuf()->sputc(n); return os;
}
}

namespace algo {
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
inline void sort(T& v, function<bool(Val, Val)> cmp = less<Val>()) {sort(v.begin(), v.end(), cmp);}
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val_a, typename Val_b>
inline void replace(T& v, const Val_a& a, const Val_b& b) {replace(v.begin(), v.end(), static_cast<int>(a), static_cast<int>(b));}
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type >
inline _ unique(T& v, function<bool(Val, Val)> cmp = equal_to<Val>()) {return unique(v.begin(), v.end(), cmp);}
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
inline _ lower_bound(T& v, const Val& x, function<bool(Val, Val)> cmp = less<Val>()) {return lower_bound(v.begin(), v.end(), x, cmp);}
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
inline _ upper_bound(T& v, const Val& x, function<bool(Val, Val)> cmp = less<Val>()) {return upper_bound(v.begin(), v.end(), x, cmp);}
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
inline void iota(T& v, const Val& x) {iota(v.begin(), v.end(), x);}
}

//sublime autofill keywords:
/*STL: push_back emplace_back pop_back push pop push_front pop_front size assign resize empty*/
/*algorithm: lower_bound upper_bound equal_range next_permutation prev_permutation binary_search*/
/*copy replace for_each fill find unique remove is_sorted min max min_element max_element*/
/*ios: fixed setprecision setw stringstream / numeric: iota accumulate adjacent_difference partial_sum*/
/*utility: move / limits: numeric_limits / iterator: begin end back_inserter front_inserter distance next prev*/

//#define MULTI_TASKCASE
using namespace abb;
using namespace output;
using namespace rit;
using namespace wit;
using namespace algo;

inline void init() {

}

inline void solve() {

}

//#define FILEIO
main(int, char* argv[]) {
	ios::sync_with_stdio(false);
#ifdef FILEIO
	fstream filein(argv[1], ios::in);
	fstream fileout(argv[2], ios::out);
	cin.rdbuf(filein.rdbuf());
	cout.rdbuf(fileout.rdbuf());
#endif
	init();
	int t = 1;
#ifdef MULTI_TASKCASE
	cin >> t; cin.ignore();
#endif
	while (t--) solve();
	return 0;
}
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using Q = queue<T>;
template<typename T> using DQ = deque<T>;
template<typename T> using V2d = vector<vector<T>>;
template<typename T> using US = unordered_set<T>;
template<typename T, size_t s> using A = array<T, s>;
template<typename T1, typename T2> using UM = unordered_map<T1, T2>;
template<typename T1, typename T2 = T1> using P = pair<T1, T2>;
template<typename T, typename Cmp = less<T>> using S = set<T, Cmp>;
template<typename T, typename Cmp = less<T>> using PQ = priority_queue<T, V<T>, Cmp>;
template<typename T1, typename T2, typename Cmp = less<T1>> using M = map<T1, T2, Cmp>;
template<typename T> using F = function<T>;
}

namespace output {
template<typename T1, typename T2>
inline ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
	return os << '(' << p.first << ", " << p.second << ')';
}
#define unfold1(Container) \
template<typename T> \
inline ostream& operator<<(ostream& os, const Container<T>& x) { \
	for (const auto& i : x) \
		os << i << ' '; \
	return os; \
}
#define unfold2(Container) \
template<typename T1,typename T2> \
inline ostream& operator<<(ostream& os,const Container<T1,T2>& x){ \
	for (const auto& i : x) \
		os << i << ' '; \
	return os; \
}
unfold1(vector); unfold1(set); unfold1(deque); unfold2(map)
#undef unfold1
#undef unfold2
};

namespace rit {
struct fast_istream {
	operator bool() const {return bool(cin);}
	fast_istream() {cin.tie(nullptr);}
} fin;
#if __cplusplus > 201703L
template<typename T>
fast_istream& operator>>(fast_istream& is, T& n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
fast_istream & operator>>(fast_istream& is, T& n) {
#endif
	while (isspace(cin.rdbuf()->sgetc()))
		cin.rdbuf()->snextc();
	bool sign = false;
	if (cin.rdbuf()->sgetc() == '-')
		sign = true, cin.rdbuf()->snextc();
	for (n = 0; isdigit(cin.rdbuf()->sgetc());)
		n *= 10, n += cin.rdbuf()->sbumpc() - '0';
	n = sign ? -n : n;
	return is;
}
fast_istream& operator>>(fast_istream& is, char& n) {
	while (isspace(cin.rdbuf()->sgetc()))
		cin.rdbuf()->snextc();
	n = cin.rdbuf()->sbumpc();
	return is;
}
}

#define endl '\n'
namespace wit {
struct fast_ostream {
	operator bool() const {return bool(cout);}
	fast_ostream() {cout.tie(nullptr);}
} fout;
constexpr int buffer_size = 30;
#if __cplusplus > 201703L
template<typename T>
fast_ostream& operator<<(fast_ostream& os, T n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
fast_ostream & operator<<(fast_ostream& os, T n) {
#endif
	if (!n) {cout.rdbuf()->sputc('0'); return os;}
	if (n < 0) cout.rdbuf()->sputc('-'), n = -n;
	static char buffer[buffer_size];
	int cnt = buffer_size;
	for (; n; n /= 10)
		buffer[--cnt] = n % 10 + '0';
	cout.rdbuf()->sputn(buffer + cnt, buffer_size - cnt);
	return os;
}
fast_ostream& operator<< (fast_ostream& os, const char& n) {
	cout.rdbuf()->sputc(n); return os;
}
}

namespace algo {
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
inline void sort(T& v, function<bool(Val, Val)> cmp = less<Val>()) {sort(v.begin(), v.end(), cmp);}
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val_a, typename Val_b>
inline void replace(T& v, const Val_a& a, const Val_b& b) {replace(v.begin(), v.end(), static_cast<int>(a), static_cast<int>(b));}
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type >
inline _ unique(T& v, function<bool(Val, Val)> cmp = equal_to<Val>()) {return unique(v.begin(), v.end(), cmp);}
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
inline _ lower_bound(T& v, const Val& x, function<bool(Val, Val)> cmp = less<Val>()) {return lower_bound(v.begin(), v.end(), x, cmp);}
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
inline _ upper_bound(T& v, const Val& x, function<bool(Val, Val)> cmp = less<Val>()) {return upper_bound(v.begin(), v.end(), x, cmp);}
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
inline void iota(T& v, const Val& x) {iota(v.begin(), v.end(), x);}
}

//sublime autofill keywords:
/*STL: push_back emplace_back pop_back push pop push_front pop_front size assign resize empty*/
/*algorithm: lower_bound upper_bound equal_range next_permutation prev_permutation binary_search*/
/*copy replace for_each fill find unique remove is_sorted min max min_element max_element*/
/*ios: fixed setprecision setw stringstream / numeric: iota accumulate adjacent_difference partial_sum*/
/*utility: move / limits: numeric_limits / iterator: begin end back_inserter front_inserter distance next prev*/

//#define MULTI_TASKCASE
using namespace abb;
using namespace output;
using namespace rit;
using namespace wit;
using namespace algo;

inline void init() {

}

inline void solve() {

}

//#define FILEIO
main(int, char* argv[]) {
	ios::sync_with_stdio(false);
#ifdef FILEIO
	fstream filein(argv[1], ios::in);
	fstream fileout(argv[2], ios::out);
	cin.rdbuf(filein.rdbuf());
	cout.rdbuf(fileout.rdbuf());
#endif
	init();
	int t = 1;
#ifdef MULTI_TASKCASE
	cin >> t; cin.ignore();
#endif
	while (t--) solve();
	return 0;
}

## 2020/12/29

//Input Output
#include<iostream>
#include<fstream>
#include<sstream>
#include<streambuf>
//C lib
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<cctype>
//Container
#include<array>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<bitset>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
//Others
#include<tuple>
#include<algorithm>
#include<functional>
#include<numeric>
#include<iterator>
#include<limits>
#include<utility>
#include<complex>
#include<type_traits>
#include<initializer_list>

using namespace std;

#if __cplusplus > 201703L
#include<concepts>
#include<ranges>
#include<bit>
#include<numbers>
using namespace numbers;
#include<span>
#endif

#define debug(x) cout << #x << " : " << x << '\n' << flush

namespace abb {
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using Q = queue<T>;
template<typename T> using DQ = deque<T>;
template<typename T> using V2d = vector<vector<T>>;
template<typename T> using US = unordered_set<T>;
template<typename T, size_t s> using A = array<T, s>;
template<typename T1, typename T2> using UM = unordered_map<T1, T2>;
template<typename T1, typename T2 = T1> using P = pair<T1, T2>;
template<typename T, typename Cmp = less<T>> using S = set<T, Cmp>;
template<typename T, typename Cmp = less<T>> using PQ = priority_queue<T, V<T>, Cmp>;
template<typename T1, typename T2, typename Cmp = less<T1>> using M = map<T1, T2, Cmp>;
template<typename T> using F = function<T>;
}

namespace output {
template<typename T1, typename T2>
inline ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
	return os << '(' << p.first << ", " << p.second << ')';
}
#define unfold1(Container) \
template<typename T> \
inline ostream& operator<<(ostream& os, const Container<T>& x) { \
	for (const auto& i : x) \
		os << i << ' '; \
	return os; \
}
#define unfold2(Container) \
template<typename T1,typename T2> \
inline ostream& operator<<(ostream& os,const Container<T1,T2>& x){ \
	for (const auto& i : x) \
		os << i << ' '; \
	return os; \
}
unfold1(vector); unfold1(set); unfold1(deque); unfold2(map)
#undef unfold1
#undef unfold2
};

namespace rit {
struct fast_istream {
	operator bool() const {return bool(cin);}
	fast_istream() {cin.tie(nullptr);}
} fin;
#if __cplusplus > 201703L
template<typename T>
fast_istream& operator>>(fast_istream& is, T& n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
fast_istream & operator>>(fast_istream& is, T& n) {
#endif
	while (isspace(cin.rdbuf()->sgetc()))
		cin.rdbuf()->snextc();
	bool sign = false;
	if (cin.rdbuf()->sgetc() == '-')
		sign = true, cin.rdbuf()->snextc();
	for (n = 0; isdigit(cin.rdbuf()->sgetc());)
		n *= 10, n += cin.rdbuf()->sbumpc() - '0';
	n = sign ? -n : n;
	return is;
}
fast_istream& operator>>(fast_istream& is, char& n) {
	while (isspace(cin.rdbuf()->sgetc()))
		cin.rdbuf()->snextc();
	n = cin.rdbuf()->sbumpc();
	return is;
}
}

#define endl '\n'
namespace wit {
struct fast_ostream {
	operator bool() const {return bool(cout);}
	fast_ostream() {cout.tie(nullptr);}
} fout;
constexpr int buffer_size = 30;
#if __cplusplus > 201703L
template<typename T>
fast_ostream& operator<<(fast_ostream& os, T n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
fast_ostream & operator<<(fast_ostream& os, T n) {
#endif
	if (!n) {cout.rdbuf()->sputc('0'); return os;}
	if (n < 0) cout.rdbuf()->sputc('-'), n = -n;
	static char buffer[buffer_size];
	int cnt = buffer_size;
	for (; n; n /= 10)
		buffer[--cnt] = n % 10 + '0';
	cout.rdbuf()->sputn(buffer + cnt, buffer_size - cnt);
	return os;
}
fast_ostream& operator<< (fast_ostream& os, const char& n) {
	cout.rdbuf()->sputc(n); return os;
}
}

namespace algo {
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
inline void sort(T& v, function<bool(Val, Val)> cmp = less <Val>()) {sort(v.begin(), v.end(), cmp);}
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
inline _ lower_bound(T& v, const Val& x, function<bool(Val, Val)> cmp = less<Val>()) {return lower_bound(v.begin(), v.end(), x);}
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
inline _ upper_bound(T& v, const Val& x, function<bool(Val, Val)> cmp = less<Val>()) {return upper_bound(v.begin(), v.end(), x);}
template<typename T, typename _ = decltype(std::begin(std::declval<T>())), typename Val = typename T::value_type>
inline void iota(T& v, const Val& x) {iota(v.begin(), v.end(), x);}
}

//sublime autofill keywords:
/*STL: push_back emplace_back pop_back push pop push_front pop_front size assign resize empty*/
/*algorithm: lower_bound upper_bound equal_range next_permutation prev_permutation binary_search*/
/*copy replace for_each fill find unique remove is_sorted min max min_element max_element*/
/*ios: fixed setprecision setw stringstream / numeric: iota accumulate adjacent_difference partial_sum*/
/*utility: move / limits: numeric_limits / iterator: begin end back_inserter front_inserter distance next prev*/

//#define MULTI_TASKCASE
using namespace abb;
using namespace output;
using namespace rit;
using namespace wit;
using namespace algo;

inline void init() {

}

inline void solve() {

}

//#define FILEIO
main() {
	ios::sync_with_stdio(false);
#ifdef FILEIO
	fstream filein("in.txt", ios::in);
	fstream fileout("out.txt", ios::out);
	cin.rdbuf(filein.rdbuf());
	cout.rdbuf(fileout.rdbuf());
#endif
	init();
	int t = 1;
#ifdef MULTI_TASKCASE
	cin >> t; cin.ignore();
#endif
	while (t--) solve();
	return 0;
}

## 2020/12/21

//Input Output
#include<iostream>
#include<fstream>
#include<sstream>
#include<streambuf>
//C lib
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<cctype>
//Container
#include<array>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<bitset>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
//Others
#include<tuple>
#include<algorithm>
#include<functional>
#include<numeric>
#include<iterator>
#include<limits>
#include<utility>
#include<complex>
#include<type_traits>
#include<initializer_list>

using namespace std;

#if __cplusplus > 201703L
#include<concepts>
#include<ranges>
#include<bit>
#include<numbers>
using namespace numbers;
#include<span>
#endif

#define debug(x) cout << #x << " : " << x << '\n' << flush

namespace abb {
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using Q = queue<T>;
template<typename T> using DQ = deque<T>;
template<typename T> using V2d = vector<vector<T>>;
template<typename T> using US = unordered_set<T>;
template<typename T, size_t s> using A = array<T, s>;
template<typename T1, typename T2> using UM = unordered_map<T1, T2>;
template<typename T1, typename T2 = T1> using P = pair<T1, T2>;
template<typename T, typename Cmp = less<T>> using S = set<T, Cmp>;
template<typename T, typename Cmp = less<T>> using PQ = priority_queue<T, V<T>, Cmp>;
template<typename T1, typename T2, typename Cmp = less<T1>> using M = map<T1, T2, Cmp>;
template<typename T> using F = function<T>;
}

namespace output {
template<typename T1, typename T2>
inline ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
	return os << '(' << p.first << ", " << p.second << ')';
}
#define unfold1(Container) \
template<typename T> \
inline ostream& operator<<(ostream& os, const Container<T>& x) { \
	for (const auto& i : x) \
		os << i << ' '; \
	return os; \
}
#define unfold2(Container) \
template<typename T1,typename T2> \
inline ostream& operator<<(ostream& os,const Container<T1,T2>& x){ \
	for (const auto& i : x) \
		os << i << ' '; \
	return os; \
}
unfold1(vector); unfold1(set); unfold1(deque); unfold2(map)
#undef unfold1
#undef unfold2
};

namespace rit {
struct fast_istream {
	operator bool() const {return bool(cin);}
	fast_istream() {cin.tie(nullptr);}
} fin;
#if __cplusplus > 201703L
template<typename T>
fast_istream& operator>>(fast_istream& is, T& n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
fast_istream & operator>>(fast_istream& is, T& n) {
#endif
	while (isspace(cin.rdbuf()->sgetc()))
		cin.rdbuf()->snextc();
	bool sign = false;
	if (cin.rdbuf()->sgetc() == '-')
		sign = true, cin.rdbuf()->snextc();
	for (n = 0; isdigit(cin.rdbuf()->sgetc());)
		n *= 10, n += cin.rdbuf()->sbumpc() - '0';
	n = sign ? -n : n;
	return is;
}
fast_istream& operator>>(fast_istream& is, char& n) {
	while (isspace(cin.rdbuf()->sgetc()))
		cin.rdbuf()->snextc();
	n = cin.rdbuf()->sbumpc();
	return is;
}
}

#define endl '\n'
namespace wit {
struct fast_ostream {
	operator bool() const {return bool(cout);}
	fast_ostream() {cout.tie(nullptr);}
} fout;
constexpr int buffer_size = 30;
#if __cplusplus > 201703L
template<typename T>
fast_ostream& operator<<(fast_ostream& os, T n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
fast_ostream & operator<<(fast_ostream& os, T n) {
#endif
	if (!n) {cout.rdbuf()->sputc('0'); return os;}
	if (n < 0) cout.rdbuf()->sputc('-'), n = -n;
	static char buffer[buffer_size];
	int cnt = buffer_size;
	for (; n; n /= 10)
		buffer[--cnt] = n % 10 + '0';
	cout.rdbuf()->sputn(buffer + cnt, buffer_size - cnt);
	return os;
}
fast_ostream& operator<< (fast_ostream& os, const char& n) {
	cout.rdbuf()->sputc(n); return os;
}
}

//sublime autofill keywords:
/*STL: push_back emplace_back pop_back push pop push_front pop_front size assign resize empty*/
/*algorithm: lower_bound upper_bound equal_range next_permutation prev_permutation binary_search*/
/*copy replace for_each fill find unique remove is_sorted min max min_element max_element*/
/*ios: fixed setprecision setw stringstream / numeric: iota accumulate adjacent_difference partial_sum*/
/*utility: move / limits: numeric_limits / iterator: begin end back_inserter front_inserter distance next prev*/

//#define MULTI_TASKCASE
using namespace abb;
using namespace output;
using namespace rit;
using namespace wit;

inline void init() {

}

inline void solve() {

}

//#define FILEIO
main() {
	ios::sync_with_stdio(false);
#ifdef FILEIO
	fstream filein("in.txt", ios::in);
	fstream fileout("out.txt", ios::out);
	cin.rdbuf(filein.rdbuf());
	cout.rdbuf(fileout.rdbuf());
#endif
	init();
	int t = 1;
#ifdef MULTI_TASKCASE
	cin >> t; cin.ignore();
#endif
	while (t--) solve();
	return 0;
}

## 2020/12/18

//Input Output
#include<iostream>
#include<fstream>
#include<sstream>
#include<streambuf>
//C lib
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<cctype>
//Container
#include<array>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<bitset>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
//Others
#include<tuple>
#include<algorithm>
#include<functional>
#include<numeric>
#include<iterator>
#include<limits>
#include<utility>
#include<complex>
#include<type_traits>
#include<initializer_list>

using namespace std;

#if __cplusplus > 201703L
#include<concepts>
#include<ranges>
#include<bit>
#include<numbers>
using namespace numbers;
#include<span>
#endif


#define debug(x) cout << #x << " : " << x << endl

namespace abb {
using ll = long long;
using ull = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using Q = queue<T>;
template<typename T> using DQ = deque<T>;
template<typename T> using V2d = vector<vector<T>>;
template<typename T> using US = unordered_set<T>;
template<typename T, size_t s> using A = array<T, s>;
template<typename T1, typename T2> using UM = unordered_map<T1, T2>;
template<typename T1, typename T2 = T1> using P = pair<T1, T2>;
template<typename T, typename Cmp = less<T>> using S = set<T, Cmp>;
template<typename T, typename Cmp = less<T>> using PQ = priority_queue<T, V<T>, Cmp>;
template<typename T1, typename T2, typename Cmp = less<T1>> using M = map<T1, T2, Cmp>;
}

namespace output {
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for (const auto& i : v) os << i << ' ';
	return os;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
	return os << '(' << p.first << ", " << p.second << ')';
}
template<typename T>
ostream& operator<<(ostream& os, const set<T>& s) {
	for (const auto& i : s) os << i << ' ';
	return os;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const map<T1, T2>& m) {
	for (const auto& i : m) os << i << ' ';
	return os;
}
};

namespace rit {
struct fast_istream {
	operator bool() const {return bool(cin);}
	fast_istream() {cin.tie(nullptr);}
} fin;
#if __cplusplus > 201703L
template<typename T>
fast_istream& operator>>(fast_istream& is, T& n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
fast_istream & operator>>(fast_istream& is, T& n) {
#endif
	while (isspace(cin.rdbuf()->sgetc()))
		cin.rdbuf()->snextc();
	bool sign = false;
	if (cin.rdbuf()->sgetc() == '-')
		sign = true, cin.rdbuf()->snextc();
	for (n = 0; isdigit(cin.rdbuf()->sgetc());)
		n *= 10, n += cin.rdbuf()->sbumpc() - '0';
	n = sign ? -n : n;
	return is;
}
fast_istream& operator>>(fast_istream& is, char& n) {
	while (isspace(cin.rdbuf()->sgetc()))
		cin.rdbuf()->snextc();
	n = cin.rdbuf()->sbumpc();
	return is;
}
}

#define endl '\n'
namespace wit {
struct fast_ostream {
	operator bool() const {return bool(cout);}
	fast_ostream() {cout.tie(nullptr);}
} fout;
constexpr int buffer_size = 30;
#if __cplusplus > 201703L
template<typename T>
fast_ostream& operator<<(fast_ostream& os, T n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
fast_ostream & operator<<(fast_ostream& os, T n) {
#endif
	if (!n) {cout.rdbuf()->sputc('0'); return os;}
	if (n < 0) cout.rdbuf()->sputc('-'), n = -n;
	static char buffer[buffer_size];
	int cnt = buffer_size;
	for (; n; n /= 10)
		buffer[--cnt] = n % 10 + '0';
	cout.rdbuf()->sputn(buffer + cnt, buffer_size - cnt);
	return os;
}
fast_ostream& operator<< (fast_ostream& os, const char& n) {
	cout.rdbuf()->sputc(n); return os;
}
}

//#define MULTI_TASKCASE
using namespace abb;
using namespace output;
using namespace rit;
using namespace wit;

inline void init() {

}

inline void solve() {

}

//#define FILEIO
main() {
	ios::sync_with_stdio(false);
#ifdef FILEIO
	fstream filein("in.txt", ios::in);
	fstream fileout("out.txt", ios::out);
	cin.rdbuf(filein.rdbuf());
	cout.rdbuf(fileout.rdbuf());
#endif
	init();
	int t = 1;
#ifdef MULTI_TASKCASE
	cin >> t;
#endif
	while (t--) solve();
	return 0;
}

## 2020/11/22

//Input Output
#include<iostream>
#include<fstream>
#include<sstream>
#include<streambuf>
//C lib
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<climits>
#include<cctype>
//Container
#include<array>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<bitset>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
//Others
#include<tuple>
#include<algorithm>
#include<functional>
#include<numeric>
#include<iterator>
#include<limits>
#include<utility>
#include<complex>
#include<initializer_list>

#if __cplusplus > 201703L
#include<concepts>
#endif

using namespace std;

#define debug(x) cout << #x << " : " << x << endl

namespace abb {
using ll = long long;
using ull = unsigned long long;
template<typename T> using V = vector<T>;
template<typename T> using Q = queue<T>;
template<typename T> using DQ = deque<T>;
template<typename T> using V2d = vector<vector<T>>;
template<typename T> using S = set<T>;
template<typename T1, typename T2> using M = map<T1, T2>;
template<typename T> using US = unordered_set<T>;
template<typename T1, typename T2> using UM = unordered_map<T1, T2>;
template<typename T1, typename T2 = T1> using P = pair<T1, T2>;
template<typename T, typename C = vector<T>, typename Cmp = less<T>>
using PQ = priority_queue<T, C, Cmp>;
}

namespace output {
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for (const auto& i : v) os << i << ' ';
	return os;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
	return os << '(' << p.first << ", " << p.second << ')';
}
template<typename T>
ostream& operator<<(ostream& os, const set<T>& s) {
	for (const auto& i : s) os << i << ' ';
	return os;
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const map<T1, T2>& m) {
	for (const auto& i : m) os << i << ' ';
	return os;
}
};

namespace rit {
struct fast_istream {
	operator bool() const {return bool(cin);}
	fast_istream() {cin.tie(nullptr);}
} fin;
#if __cplusplus > 201703L
template<typename T>
fast_istream& operator>>(fast_istream& is, T& n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
operator>>(fast_istream& is, T& n) {
#endif
	while (isspace(cin.rdbuf()->sgetc()))
		cin.rdbuf()->snextc();
	bool sign = false;
	if (cin.rdbuf()->sgetc() == '-')
		sign = true, cin.rdbuf()->snextc();
	for (n = 0; isdigit(cin.rdbuf()->sgetc());)
		n *= 10, n += cin.rdbuf()->sbumpc() - '0';
	n = sign ? -n : n;
	return is;
}
}

#define endl '\n'
namespace wit {
struct fast_ostream {
	operator bool() const {return bool(cout);}
	fast_ostream() {cout.tie(nullptr);}
} fout;
constexpr int buffer_size = 30;
#if __cplusplus > 201703L
template<typename T>
fast_ostream& operator<<(fast_ostream& os, T n) requires integral<T> {
#else
template<typename T, class = typename enable_if<is_integral<T>::value>::type>
fast_ostream & operator<<(fast_ostream& os, T n) {
#endif
	if (n < 0) cout.rdbuf()->sputc('-'), n = -n;
	static char buffer[buffer_size];
	int cnt = buffer_size;
	for (; n; n /= 10)
		buffer[--cnt] = n % 10 + '0';
	cout.rdbuf()->sputn(buffer + cnt, buffer_size - cnt);
	return os;
}
fast_ostream& operator<< (fast_ostream& os, const char& n) {
	cout.rdbuf()->sputc(n); return os;
}
}

//#define MULTI_TASKCASE
using namespace abb;
using namespace output;
using namespace rit;
using namespace wit;

inline void init() {

}

inline void solve() {

}

//#define FILEIO
main() {
	ios::sync_with_stdio(false);
#ifdef FILEIO
	fstream filein("in.txt", ios::in);
	fstream fileout("out.txt", ios::out);
	cin.rdbuf(filein.rdbuf());
	cout.rdbuf(fileout.rdbuf());
#endif
	init();
	int t = 1;
#ifdef MULTI_TASKCASE
	cin >> t;
#endif
	while (t--) solve();
	return 0;
}