#line 2 "misc/all.hpp"
#line 2 "misc/fastio.hpp"
#include <cstdio>
#include <cstring>
#include <string>
#include <type_traits>
#include <utility>
using namespace std;
#line 2 "internal/internal-type-traits.hpp"
#line 4 "internal/internal-type-traits.hpp"
using namespace std;
namespace internal {
template <typename T>
using is_broadly_integral =
typename conditional_t<is_integral_v<T> || is_same_v<T, __int128_t> ||
is_same_v<T, __uint128_t>,
true_type, false_type>::type;
template <typename T>
using is_broadly_signed =
typename conditional_t<is_signed_v<T> || is_same_v<T, __int128_t>,
true_type, false_type>::type;
template <typename T>
using is_broadly_unsigned =
typename conditional_t<is_unsigned_v<T> || is_same_v<T, __uint128_t>,
true_type, false_type>::type;
#define ENABLE_VALUE(x) \
template <typename T> \
constexpr bool x##_v = x<T>::value;
ENABLE_VALUE(is_broadly_integral);
ENABLE_VALUE(is_broadly_signed);
ENABLE_VALUE(is_broadly_unsigned);
#undef ENABLE_VALUE
#define ENABLE_HAS_TYPE(var) \
template <class, class = void> \
struct has_##var : false_type {}; \
template <class T> \
struct has_##var<T, void_t<typename T::var>> : true_type {}; \
template <class T> \
constexpr auto has_##var##_v = has_##var<T>::value;
#define ENABLE_HAS_VAR(var) \
template <class, class = void> \
struct has_##var : false_type {}; \
template <class T> \
struct has_##var<T, void_t<decltype(T::var)>> : true_type {}; \
template <class T> \
constexpr auto has_##var##_v = has_##var<T>::value;
} // namespace internal
#line 12 "misc/fastio.hpp"
namespace fastio {
static constexpr int SZ = 1 << 17;
static constexpr int offset = 64;
char inbuf[SZ], outbuf[SZ];
int in_left = 0, in_right = 0, out_right = 0;
struct Pre {
char num[40000];
constexpr Pre() : num() {
for (int i = 0; i < 10000; i++) {
int n = i;
for (int j = 3; j >= 0; j--) {
num[i * 4 + j] = n % 10 + '0';
n /= 10;
}
}
}
} constexpr pre;
void load() {
int len = in_right - in_left;
memmove(inbuf, inbuf + in_left, len);
in_right = len + fread(inbuf + len, 1, SZ - len, stdin);
in_left = 0;
}
void flush() {
fwrite(outbuf, 1, out_right, stdout);
out_right = 0;
}
void skip_space() {
if (in_left + offset > in_right) load();
while (inbuf[in_left] <= ' ') in_left++;
}
void single_read(char& c) {
if (in_left + offset > in_right) load();
skip_space();
c = inbuf[in_left++];
}
void single_read(string& S) {
skip_space();
while (true) {
if (in_left == in_right) load();
int i = in_left;
for (; i != in_right; i++) {
if (inbuf[i] <= ' ') break;
}
copy(inbuf + in_left, inbuf + i, back_inserter(S));
in_left = i;
if (i != in_right) break;
}
}
template <typename T,
enable_if_t<internal::is_broadly_integral_v<T>>* = nullptr>
void single_read(T& x) {
if (in_left + offset > in_right) load();
skip_space();
char c = inbuf[in_left++];
[[maybe_unused]] bool minus = false;
if constexpr (internal::is_broadly_signed_v<T>) {
if (c == '-') minus = true, c = inbuf[in_left++];
}
x = 0;
while (c >= '0') {
x = x * 10 + (c & 15);
c = inbuf[in_left++];
}
if constexpr (internal::is_broadly_signed_v<T>) {
if (minus) x = -x;
}
}
void rd() {}
template <typename Head, typename... Tail>
void rd(Head& head, Tail&... tail) {
single_read(head);
rd(tail...);
}
void single_write(const char& c) {
if (out_right > SZ - offset) flush();
outbuf[out_right++] = c;
}
void single_write(const bool& b) {
if (out_right > SZ - offset) flush();
outbuf[out_right++] = b ? '1' : '0';
}
void single_write(const string& S) {
flush(), fwrite(S.data(), 1, S.size(), stdout);
}
void single_write(const char* p) { flush(), fwrite(p, 1, strlen(p), stdout); }
template <typename T,
enable_if_t<internal::is_broadly_integral_v<T>>* = nullptr>
void single_write(const T& _x) {
if (out_right > SZ - offset) flush();
if (_x == 0) {
outbuf[out_right++] = '0';
return;
}
T x = _x;
if constexpr (internal::is_broadly_signed_v<T>) {
if (x < 0) outbuf[out_right++] = '-', x = -x;
}
constexpr int buffer_size = sizeof(T) * 10 / 4;
char buf[buffer_size];
int i = buffer_size;
while (x >= 10000) {
i -= 4;
memcpy(buf + i, pre.num + (x % 10000) * 4, 4);
x /= 10000;
}
if (x < 100) {
if (x < 10) {
outbuf[out_right] = '0' + x;
++out_right;
} else {
uint32_t q = (uint32_t(x) * 205) >> 11;
uint32_t r = uint32_t(x) - q * 10;
outbuf[out_right] = '0' + q;
outbuf[out_right + 1] = '0' + r;
out_right += 2;
}
} else {
if (x < 1000) {
memcpy(outbuf + out_right, pre.num + (x << 2) + 1, 3);
out_right += 3;
} else {
memcpy(outbuf + out_right, pre.num + (x << 2), 4);
out_right += 4;
}
}
memcpy(outbuf + out_right, buf + i, buffer_size - i);
out_right += buffer_size - i;
}
void wt() {}
template <typename Head, typename... Tail>
void wt(const Head& head, const Tail&... tail) {
single_write(head);
wt(forward<const Tail>(tail)...);
}
template <typename... Args>
void wtn(const Args&... x) {
wt(forward<const Args>(x)...);
wt('\n');
}
struct Dummy {
Dummy() { atexit(flush); }
} dummy;
} // namespace fastio
using fastio::rd;
using fastio::skip_space;
using fastio::wt;
using fastio::wtn;
#line 2 "misc/rng.hpp"
#line 2 "internal/internal-seed.hpp"
#include <chrono>
using namespace std;
namespace internal {
unsigned long long non_deterministic_seed() {
unsigned long long m =
chrono::duration_cast<chrono::nanoseconds>(
chrono::high_resolution_clock::now().time_since_epoch())
.count();
m ^= 9845834732710364265uLL;
m ^= m << 24, m ^= m >> 31, m ^= m << 35;
return m;
}
unsigned long long deterministic_seed() { return 88172645463325252UL; }
// 64 bit の seed 値を生成 (手元では seed 固定)
// 連続で呼び出すと同じ値が何度も返ってくるので注意
// #define RANDOMIZED_SEED するとシードがランダムになる
unsigned long long seed() {
#if defined(NyaanLocal) && !defined(RANDOMIZED_SEED)
return deterministic_seed();
#else
return non_deterministic_seed();
#endif
}
} // namespace internal
#line 4 "misc/rng.hpp"
namespace my_rand {
using i64 = long long;
using u64 = unsigned long long;
// [0, 2^64 - 1)
u64 rng() {
static u64 _x = internal::seed();
return _x ^= _x << 7, _x ^= _x >> 9;
}
// [l, r]
i64 rng(i64 l, i64 r) {
assert(l <= r);
return l + rng() % u64(r - l + 1);
}
// [l, r)
i64 randint(i64 l, i64 r) {
assert(l < r);
return l + rng() % u64(r - l);
}
// choose n numbers from [l, r) without overlapping
vector<i64> randset(i64 l, i64 r, i64 n) {
assert(l <= r && n <= r - l);
unordered_set<i64> s;
for (i64 i = n; i; --i) {
i64 m = randint(l, r + 1 - i);
if (s.find(m) != s.end()) m = r - i;
s.insert(m);
}
vector<i64> ret;
for (auto& x : s) ret.push_back(x);
return ret;
}
// [0.0, 1.0)
double rnd() { return rng() * 5.42101086242752217004e-20; }
// [l, r)
double rnd(double l, double r) {
assert(l < r);
return l + rnd() * (r - l);
}
template <typename T>
void randshf(vector<T>& v) {
int n = v.size();
for (int i = 1; i < n; i++) swap(v[i], v[randint(0, i + 1)]);
}
} // namespace my_rand
using my_rand::randint;
using my_rand::randset;
using my_rand::randshf;
using my_rand::rnd;
using my_rand::rng;
#line 2 "misc/timer.hpp"
#line 4 "misc/timer.hpp"
using namespace std;
struct Timer {
chrono::high_resolution_clock::time_point st;
Timer() { reset(); }
void reset() { st = chrono::high_resolution_clock::now(); }
long long elapsed() {
auto ed = chrono::high_resolution_clock::now();
return chrono::duration_cast<chrono::milliseconds>(ed - st).count();
}
long long operator()() { return elapsed(); }
};
#line 6 "misc/all.hpp"
misc/all.hpp