This documentation is automatically generated by online-judge-tools/verification-helper
#include "template/util.hpp"
#pragma once
#include <bits/stdc++.h>
#include "macros.hpp"
#include "alias.hpp"
template<class F> class RecLambda {
private:
F f;
public:
explicit constexpr RecLambda(F&& f_) : f(std::forward<F>(f_)) {}
template<class... Args>
constexpr auto operator()(Args&&... args)
-> decltype(f(*this, std::forward<Args>(args)...)) {
return f(*this, std::forward<Args>(args)...);
}
};
template<class F> inline constexpr RecLambda<F> rec_lambda(F&& f) {
return RecLambda<F>(std::forward<F>(f));
}
template<class Head, class... Tail> struct multi_dim_vector {
using type = std::vector<typename multi_dim_vector<Tail...>::type>;
};
template<class T> struct multi_dim_vector<T> { using type = T; };
template<class T, class Arg>
constexpr std::vector<T> make_vec(int n, Arg&& arg) {
return std::vector<T>(n, std::forward<Arg>(arg));
}
template<class T, class... Args>
constexpr typename multi_dim_vector<Args..., T>::type make_vec(int n,
Args&&... args) {
return typename multi_dim_vector<Args..., T>::type(
n, make_vec<T>(std::forward<Args>(args)...));
}
template<class T, class Comp = std::less<T>> class compressor {
private:
std::vector<T> dat;
Comp cmp;
bool sorted = false;
public:
compressor() : compressor(Comp()) {}
compressor(const Comp& cmp) : cmp(cmp) {}
compressor(const std::vector<T>& vec, bool f = false,
const Comp& cmp = Comp())
: dat(vec), cmp(cmp) {
if (f) build();
}
compressor(std::vector<T>&& vec, bool f = false, const Comp& cmp = Comp())
: dat(std::move(vec)), cmp(cmp) {
if (f) build();
}
compressor(std::initializer_list<T> il, bool f = false,
const Comp& cmp = Comp())
: dat(all(il)), cmp(cmp) {
if (f) build();
}
void reserve(int n) {
assert(!sorted);
dat.reserve(n);
}
void push_back(const T& v) {
assert(!sorted);
dat.push_back(v);
}
void push_back(T&& v) {
assert(!sorted);
dat.push_back(std::move(v));
}
template<class... Args> void emplace_back(Args&&... args) {
assert(!sorted);
dat.emplace_back(std::forward<Args>(args)...);
}
void push(const std::vector<T>& vec) {
assert(!sorted);
const int n = dat.size();
dat.resize(n + vec.size());
rep (i, vec.size()) dat[n + i] = vec[i];
}
int build() {
assert(!sorted);
sorted = true;
std::sort(all(dat), cmp);
dat.erase(std::unique(all(dat),
[&](const T& a, const T& b) -> bool {
return !cmp(a, b) && !cmp(b, a);
}),
dat.end());
return dat.size();
}
const T& operator[](int k) const& {
assert(sorted);
assert(0 <= k && k < (int)dat.size());
return dat[k];
}
int get(const T& val) const {
assert(sorted);
auto itr = std::lower_bound(all(dat), val, cmp);
assert(itr != dat.end() && !cmp(val, *itr));
return itr - dat.begin();
}
int lower_bound(const T& val) const {
assert(sorted);
auto itr = std::lower_bound(all(dat), val, cmp);
return itr - dat.begin();
}
int upper_bound(const T& val) const {
assert(sorted);
auto itr = std::upper_bound(all(dat), val, cmp);
return itr - dat.begin();
}
bool contains(const T& val) const {
assert(sorted);
return std::binary_search(all(dat), val, cmp);
}
std::vector<int> pressed(const std::vector<T>& vec) const {
assert(sorted);
std::vector<int> res(vec.size());
rep (i, vec.size()) res[i] = get(vec[i]);
return res;
}
void press(std::vector<T>& vec) const {
assert(sorted);
for (auto&& i : vec) i = get(i);
}
int size() const {
assert(sorted);
return dat.size();
}
};
#line 2 "template/util.hpp"
#include <bits/stdc++.h>
#line 2 "template/macros.hpp"
#line 4 "template/macros.hpp"
#ifndef __COUNTER__
#define __COUNTER__ __LINE__
#endif
#define OVERLOAD5(a, b, c, d, e, ...) e
#define REP1_0(b, c) REP1_1(b, c)
#define REP1_1(b, c) \
for (ll REP_COUNTER_##c = 0; REP_COUNTER_##c < (ll)(b); ++REP_COUNTER_##c)
#define REP1(b) REP1_0(b, __COUNTER__)
#define REP2(i, b) for (ll i = 0; i < (ll)(b); ++i)
#define REP3(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define REP4(i, a, b, c) for (ll i = (ll)(a); i < (ll)(b); i += (ll)(c))
#define rep(...) OVERLOAD5(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
#define RREP2(i, a) for (ll i = (ll)(a)-1; i >= 0; --i)
#define RREP3(i, a, b) for (ll i = (ll)(a)-1; i >= (ll)(b); --i)
#define RREP4(i, a, b, c) for (ll i = (ll)(a)-1; i >= (ll)(b); i -= (ll)(c))
#define rrep(...) OVERLOAD5(__VA_ARGS__, RREP4, RREP3, RREP2)(__VA_ARGS__)
#define REPS2(i, b) for (ll i = 1; i <= (ll)(b); ++i)
#define REPS3(i, a, b) for (ll i = (ll)(a) + 1; i <= (ll)(b); ++i)
#define REPS4(i, a, b, c) for (ll i = (ll)(a) + 1; i <= (ll)(b); i += (ll)(c))
#define reps(...) OVERLOAD5(__VA_ARGS__, REPS4, REPS3, REPS2)(__VA_ARGS__)
#define RREPS2(i, a) for (ll i = (ll)(a); i > 0; --i)
#define RREPS3(i, a, b) for (ll i = (ll)(a); i > (ll)(b); --i)
#define RREPS4(i, a, b, c) for (ll i = (ll)(a); i > (ll)(b); i -= (ll)(c))
#define rreps(...) OVERLOAD5(__VA_ARGS__, RREPS4, RREPS3, RREPS2)(__VA_ARGS__)
#define each_for(...) for (auto&& __VA_ARGS__)
#define each_const(...) for (const auto& __VA_ARGS__)
#define all(v) std::begin(v), std::end(v)
#define rall(v) std::rbegin(v), std::rend(v)
#if __cpp_if_constexpr >= 201606L
#define IF_CONSTEXPR constexpr
#else
#define IF_CONSTEXPR
#endif
#define IO_BUFFER_SIZE (1 << 17)
#line 2 "template/alias.hpp"
#line 4 "template/alias.hpp"
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using ld = long double;
using PLL = std::pair<ll, ll>;
template<class T>
using prique = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template<class T> struct infinity {
static constexpr T value = std::numeric_limits<T>::max() / 2;
static constexpr T mvalue = std::numeric_limits<T>::lowest() / 2;
static constexpr T max = std::numeric_limits<T>::max();
static constexpr T min = std::numeric_limits<T>::lowest();
};
#if __cplusplus <= 201402L
template<class T> constexpr T infinity<T>::value;
template<class T> constexpr T infinity<T>::mvalue;
template<class T> constexpr T infinity<T>::max;
template<class T> constexpr T infinity<T>::min;
#endif
#if __cpp_variable_templates >= 201304L
template<class T> constexpr T INF = infinity<T>::value;
#endif
constexpr ll inf = infinity<ll>::value;
constexpr ld EPS = 1e-8;
constexpr ld PI = 3.1415926535897932384626;
#line 6 "template/util.hpp"
template<class F> class RecLambda {
private:
F f;
public:
explicit constexpr RecLambda(F&& f_) : f(std::forward<F>(f_)) {}
template<class... Args>
constexpr auto operator()(Args&&... args)
-> decltype(f(*this, std::forward<Args>(args)...)) {
return f(*this, std::forward<Args>(args)...);
}
};
template<class F> inline constexpr RecLambda<F> rec_lambda(F&& f) {
return RecLambda<F>(std::forward<F>(f));
}
template<class Head, class... Tail> struct multi_dim_vector {
using type = std::vector<typename multi_dim_vector<Tail...>::type>;
};
template<class T> struct multi_dim_vector<T> { using type = T; };
template<class T, class Arg>
constexpr std::vector<T> make_vec(int n, Arg&& arg) {
return std::vector<T>(n, std::forward<Arg>(arg));
}
template<class T, class... Args>
constexpr typename multi_dim_vector<Args..., T>::type make_vec(int n,
Args&&... args) {
return typename multi_dim_vector<Args..., T>::type(
n, make_vec<T>(std::forward<Args>(args)...));
}
template<class T, class Comp = std::less<T>> class compressor {
private:
std::vector<T> dat;
Comp cmp;
bool sorted = false;
public:
compressor() : compressor(Comp()) {}
compressor(const Comp& cmp) : cmp(cmp) {}
compressor(const std::vector<T>& vec, bool f = false,
const Comp& cmp = Comp())
: dat(vec), cmp(cmp) {
if (f) build();
}
compressor(std::vector<T>&& vec, bool f = false, const Comp& cmp = Comp())
: dat(std::move(vec)), cmp(cmp) {
if (f) build();
}
compressor(std::initializer_list<T> il, bool f = false,
const Comp& cmp = Comp())
: dat(all(il)), cmp(cmp) {
if (f) build();
}
void reserve(int n) {
assert(!sorted);
dat.reserve(n);
}
void push_back(const T& v) {
assert(!sorted);
dat.push_back(v);
}
void push_back(T&& v) {
assert(!sorted);
dat.push_back(std::move(v));
}
template<class... Args> void emplace_back(Args&&... args) {
assert(!sorted);
dat.emplace_back(std::forward<Args>(args)...);
}
void push(const std::vector<T>& vec) {
assert(!sorted);
const int n = dat.size();
dat.resize(n + vec.size());
rep (i, vec.size()) dat[n + i] = vec[i];
}
int build() {
assert(!sorted);
sorted = true;
std::sort(all(dat), cmp);
dat.erase(std::unique(all(dat),
[&](const T& a, const T& b) -> bool {
return !cmp(a, b) && !cmp(b, a);
}),
dat.end());
return dat.size();
}
const T& operator[](int k) const& {
assert(sorted);
assert(0 <= k && k < (int)dat.size());
return dat[k];
}
int get(const T& val) const {
assert(sorted);
auto itr = std::lower_bound(all(dat), val, cmp);
assert(itr != dat.end() && !cmp(val, *itr));
return itr - dat.begin();
}
int lower_bound(const T& val) const {
assert(sorted);
auto itr = std::lower_bound(all(dat), val, cmp);
return itr - dat.begin();
}
int upper_bound(const T& val) const {
assert(sorted);
auto itr = std::upper_bound(all(dat), val, cmp);
return itr - dat.begin();
}
bool contains(const T& val) const {
assert(sorted);
return std::binary_search(all(dat), val, cmp);
}
std::vector<int> pressed(const std::vector<T>& vec) const {
assert(sorted);
std::vector<int> res(vec.size());
rep (i, vec.size()) res[i] = get(vec[i]);
return res;
}
void press(std::vector<T>& vec) const {
assert(sorted);
for (auto&& i : vec) i = get(i);
}
int size() const {
assert(sorted);
return dat.size();
}
};