/**
*
*/
#define ASSERT_LV 1
// header {{{
#ifndef ASSERT_LV
# define ASSERT_LV 1
#endif
#if ASSERT_LV == 0
# define NDEBUG
#endif
#if defined(__GNUC__) && !defined(__clang__)
#include <bits/stdc++.h>
#else
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
//#include <clocale>
#include <cmath>
//#include <csetjmp>
//#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
//#include <cwchar>
//#include <cwctype>
#if __cplusplus >= 201103L
//#include <ccomplex>
#include <cfenv>
#include <cinttypes>
//#include <cstdalign>
//#include <cstdbool>
#include <cstdint>
//#include <ctgmath>
//#include <cuchar>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
//#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
//#include <atomic>
#include <chrono>
//#include <codecvt>
//#include <condition_variable>
#include <forward_list>
//#include <future>
#include <initializer_list>
//#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
//#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#if __cplusplus >= 201402L
//#include <shared_mutex>
#endif
#if __cplusplus >= 201703L
#include <any>
//#include <charconv>
//#include <execution>
//#include <filesystem>
#include <optional>
//#include <memory_resource>
#include <string_view>
#include <variant>
#endif
#endif
using namespace std;
using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
#ifdef __SIZEOF_INT128__
using i128 = __int128;
using u128 = unsigned __int128;
#endif
using f32 = float;
using f64 = double;
using f80 = long double;
template<class T> constexpr T PROCON_INF();
// }}}
using Real = f80;
template<> constexpr i64 PROCON_INF<i64>() { return INT64_C(1'010'000'000'000'000'017); }
template<> constexpr Real PROCON_INF<Real>() { return Real(1e100L); }
constexpr i64 MOD = INT64_C(1'000'000'007);
//constexpr i64 MOD = INT64_C(998'244'353);
constexpr Real EPS = Real(1e-10L);
constexpr int COUT_PREC = 15;
constexpr bool COUT_AUTOFLUSH = false;
// procon {{{
#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y
#define SFINAE(pred...) std::enable_if_t<(pred), std::nullptr_t> = nullptr
#define ASSERT(expr...) assert((expr))
#if defined(PROCON_LOCAL) || ASSERT_LV >= 2
# define ASSERT_LOCAL(expr...) assert((expr))
#else
# define ASSERT_LOCAL(expr...)
#endif
constexpr i64 INF = PROCON_INF<i64>();
constexpr Real FINF = PROCON_INF<Real>();
constexpr Real PI = Real(3.141592653589793238462643383279502884197L);
template<class T, SFINAE(is_signed<T>::value)>
constexpr T ABS(T x) noexcept {
return x < 0 ? -x : x;
}
constexpr bool LT_EPS(Real lhs, Real rhs, Real eps=EPS) { return lhs < rhs-eps; }
constexpr bool GT_EPS(Real lhs, Real rhs, Real eps=EPS) { return lhs > rhs+eps; }
constexpr bool EQ_EPS(Real lhs, Real rhs, Real eps=EPS) { return ABS(lhs-rhs) <= eps; }
constexpr bool EQ_EXACT(Real lhs, Real rhs) {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wfloat-equal"
return lhs == rhs;
#pragma GCC diagnostic pop
}
#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define LOOP(n) REP(CPP_CAT(macro_loop_counter,__COUNTER__), n)
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
#define SLICE(f,c,l,r,...) (([&](decltype((c)) cccc, decltype((l)) llll, decltype((r)) rrrr) {\
auto iiii = llll <= rrrr ? std::begin(cccc)+llll : std::end(cccc);\
auto jjjj = llll <= rrrr ? std::begin(cccc)+rrrr : std::end(cccc);\
return (f)(iiii, jjjj, ## __VA_ARGS__);\
})(c,l,r))
#define LIFT(f) ([](auto&&... args) -> decltype(auto) { return (f)(std::forward<decltype(args)>(args)...); })
template<class C>
constexpr i64 SIZE(const C& c) noexcept { return static_cast<i64>(c.size()); }
template<class T, size_t N>
constexpr i64 SIZE(const T (&)[N]) noexcept { return static_cast<i64>(N); }
constexpr bool is_odd (i64 x) { return x%2 != 0; }
constexpr bool is_even(i64 x) { return x%2 == 0; }
template<class T>
constexpr i64 CMP(T x, T y) noexcept { return (y<x) - (x<y); }
template<class T>
constexpr i64 SGN(T x) noexcept { return CMP(x,T(0)); }
template<class T1, class T2, class Comp=less<>,
SFINAE(
is_integral<T1>::value &&
is_integral<T2>::value &&
is_signed<T1>::value != is_unsigned<T2>::value
)>
constexpr auto MAX(T1 x, T2 y, Comp comp={}) {
return max<common_type_t<T1,T2>>({x,y}, comp);
}
template<class T1, class T2, class Comp=less<>,
SFINAE(
is_floating_point<T1>::value &&
is_floating_point<T2>::value
)>
constexpr auto MAX(T1 x, T2 y, Comp comp={}) {
return max<common_type_t<T1,T2>>({x,y}, comp);
}
template<class T, class Comp=less<>>
constexpr const T& MAX(const T& x, const T& y, Comp comp={}) {
return max(x, y, comp);
}
template<class T, class Comp=less<>>
constexpr T MAX(initializer_list<T> ilist, Comp comp={}) {
return max(ilist, comp);
}
template<class T1, class T2, class Comp=less<>,
SFINAE(
is_integral<T1>::value &&
is_integral<T2>::value &&
is_signed<T1>::value != is_unsigned<T2>::value
)>
constexpr auto MIN(T1 x, T2 y, Comp comp={}) {
return min<common_type_t<T1,T2>>({x,y}, comp);
}
template<class T1, class T2, class Comp=less<>,
SFINAE(
is_floating_point<T1>::value &&
is_floating_point<T2>::value
)>
constexpr auto MIN(T1 x, T2 y, Comp comp={}) {
return min<common_type_t<T1,T2>>({x,y}, comp);
}
template<class T, class Comp=less<>>
constexpr const T& MIN(const T& x, const T& y, Comp comp={}) {
return min(x, y, comp);
}
template<class T, class Comp=less<>>
constexpr T MIN(initializer_list<T> ilist, Comp comp={}) {
return min(ilist, comp);
}
template<class T, class U, class Comp=less<>>
constexpr bool chmax(T& xmax, const U& x, Comp comp={}) noexcept {
if(comp(xmax, x)) {
xmax = x;
return true;
}
return false;
}
template<class T, class U, class Comp=less<>>
constexpr bool chmin(T& xmin, const U& x, Comp comp={}) noexcept {
if(comp(x, xmin)) {
xmin = x;
return true;
}
return false;
}
template<class BinaryFunc, class UnaryFunc>
auto ON(BinaryFunc&& bf, UnaryFunc&& uf) {
return [bf=forward<BinaryFunc>(bf),uf=forward<UnaryFunc>(uf)](const auto& x, const auto& y) {
return bf(uf(x), uf(y));
};
}
template<class F>
auto LT_ON(F&& f) {
return ON(less<>{}, forward<F>(f));
}
template<class F>
auto GT_ON(F&& f) {
return ON(greater<>{}, forward<F>(f));
}
template<class F>
auto NOT_FN(F&& f) {
return [f=forward<F>(f)](auto&&... args) -> bool { return !f(forward<decltype(args)>(args)...); };
}
struct IDENTITY {
using is_transparent = void;
template<class T>
constexpr decltype(auto) operator()(T&& x) const { return forward<T>(x); }
};
// ビット演算 {{{
// 引数は [-INF,INF] のみ想定
constexpr i64 BIT_I(i64 i) {
return 1LL << i;
}
constexpr i64 BIT_I_1(i64 i) {
return BIT_I(i) - 1;
}
constexpr i64 BIT_GET(i64 x, i64 i) {
return x & BIT_I(i);
}
constexpr bool BIT_TEST(i64 x, i64 i) {
return BIT_GET(x,i) != 0;
}
constexpr i64 BIT_SET(i64 x, i64 i) {
return x | BIT_I(i);
}
constexpr i64 BIT_CLEAR(i64 x, i64 i) {
return x & ~BIT_I(i);
}
constexpr i64 BIT_FLIP(i64 x, i64 i) {
return x ^ BIT_I(i);
}
constexpr i64 BIT_ASSIGN(i64 x, i64 i, bool b) {
return b ? BIT_SET(x,i) : BIT_CLEAR(x,i);
}
constexpr i64 BIT_COUNT_LEADING_ZEROS(i64 x) {
if(x == 0) return 64;
return __builtin_clzll(x);
}
constexpr i64 BIT_COUNT_TRAILING_ZEROS(i64 x) {
if(x == 0) return 64;
return __builtin_ctzll(x);
}
constexpr i64 BIT_COUNT_ONES(i64 x) {
return __builtin_popcountll(x);
}
// 1の個数が奇数なら1, 偶数なら0を返す
constexpr i64 BIT_PARITY(i64 x) {
return __builtin_parityll(x);
}
// X ⊆ {0,1,...,n-1}, |X| = k なる部分集合 X を昇順に列挙する
// comb(n,k) 個
//
// ```
// i64 x = BIT_I_1(3);
// do {
// // ...
// } while(BIT_NEXT_SET_SIZED(x, 10));
// ```
constexpr bool BIT_NEXT_SET_SIZED(i64& x, i64 n) {
if(x == 0) return false;
i64 t = (x|(x-1)) + 1;
x = t | ((~t&(t-1)) >> (BIT_COUNT_TRAILING_ZEROS(x)+1));
return x < BIT_I(n);
}
// 集合 Y の部分集合 X を昇順に列挙する
// 2^|Y| 個
//
// ```
// i64 y = 0b10101;
// i64 x = 0;
// do {
// // ...
// } while(BIT_NEXT_SUBSET(x, y));
// ```
constexpr bool BIT_NEXT_SUBSET(i64& x, i64 y) {
if(x == y) return false;
x = (x-y) & y;
return true;
}
// 集合 Y の部分集合 X を降順に列挙する
// 2^|Y| 個
//
// ```
// i64 y = 0b10101;
// i64 x = y;
// do {
// // ...
// } while(BIT_PREV_SUBSET(x, y));
// ```
constexpr bool BIT_PREV_SUBSET(i64& x, i64 y) {
if(x == 0) return false;
x = (x-1) & y;
return true;
}
// 集合 Y を包含する集合 X ⊆ {0,1,...,n-1} を昇順に列挙する
// 2^(n-|Y|) 個
//
// ```
// i64 y = 0b00010101;
// i64 x = y;
// do {
// // ...
// } while(BIT_NEXT_SUPERSET(x, 8, y));
// ```
constexpr bool BIT_NEXT_SUPERSET(i64& x, i64 n, i64 y) {
x = (x+1) | y;
return x < BIT_I(n);
}
// }}}
[[noreturn]] void EXIT() {
cout.flush();
#ifdef PROCON_LOCAL
cerr.flush();
exit(0);
#else
_Exit(0);
#endif
}
// tuple {{{
template<i64 I=0, class F, class... TS, SFINAE(sizeof...(TS) == I)>
void tuple_enumerate(tuple<TS...>&, F&&) {}
template<i64 I=0, class F, class... TS, SFINAE(sizeof...(TS) > I)>
void tuple_enumerate(tuple<TS...>& t, F&& f) {
f(I, get<I>(t));
tuple_enumerate<I+1>(t, forward<F>(f));
}
template<i64 I=0, class F, class... TS, SFINAE(sizeof...(TS) == I)>
void tuple_enumerate(const tuple<TS...>&, F&&) {}
template<i64 I=0, class F, class... TS, SFINAE(sizeof...(TS) > I)>
void tuple_enumerate(const tuple<TS...>& t, F&& f) {
f(I, get<I>(t));
tuple_enumerate<I+1>(t, forward<F>(f));
}
// }}}
// container {{{
template<class T> struct is_container : false_type {};
template<class T, size_t N> struct is_container<array<T,N>> : true_type {};
template<class... Args> struct is_container<vector<Args...>> : true_type {};
template<class... Args> struct is_container<deque<Args...>> : true_type {};
template<class... Args> struct is_container<list<Args...>> : true_type {};
template<class... Args> struct is_container<forward_list<Args...>> : true_type {};
template<class... Args> struct is_container<set<Args...>> : true_type {};
template<class... Args> struct is_container<multiset<Args...>> : true_type {};
template<class... Args> struct is_container<unordered_set<Args...>> : true_type {};
template<class... Args> struct is_container<unordered_multiset<Args...>> : true_type {};
template<class... Args> struct is_container<map<Args...>> : true_type {};
template<class... Args> struct is_container<multimap<Args...>> : true_type {};
template<class... Args> struct is_container<unordered_map<Args...>> : true_type {};
template<class... Args> struct is_container<unordered_multimap<Args...>> : true_type {};
template<class T, class Enable=void>
struct ProconHash {
size_t operator()(const T& x) const noexcept {
return hash<T>{}(x);
}
};
template<class T>
size_t procon_hash_value(const T& x) noexcept {
return ProconHash<T>{}(x);
}
size_t procon_hash_combine(size_t h1, size_t h2) noexcept {
constexpr size_t M = UINT64_C(0xc6a4a7935bd1e995);
constexpr int R = 47;
h2 *= M;
h2 ^= h2 >> R;
h2 *= M;
h1 ^= h2;
h1 *= M;
h1 += 0xe6546b64;
return h1;
}
template<class T1, class T2>
struct ProconHash<pair<T1,T2>> {
size_t operator()(const pair<T1,T2>& p) const noexcept {
size_t h1 = procon_hash_value(p.first);
size_t h2 = procon_hash_value(p.second);
return procon_hash_combine(h1, h2);
}
};
template<class... TS>
struct ProconHash<tuple<TS...>> {
size_t operator()(const tuple<TS...>& t) const noexcept {
size_t h = 0;
tuple_enumerate(t, [&h](i64, const auto& e) {
h = procon_hash_combine(h, procon_hash_value(e));
});
return h;
}
};
template<class C>
struct ProconHash<C,enable_if_t<is_container<C>::value>> {
size_t operator()(const C& c) const noexcept {
size_t h = 0;
for(const auto& e : c)
h = procon_hash_combine(h, procon_hash_value(e));
return h;
}
};
template<class T, class Hash=ProconHash<T>, class Eq=equal_to<T>>
using HashSet = unordered_set<T,Hash,Eq>;
template<class K, class V, class Hash=ProconHash<K>, class Eq=equal_to<K>>
using HashMap = unordered_map<K,V,Hash,Eq>;
template<class T, class Hash=ProconHash<T>, class Eq=equal_to<T>>
using HashMultiset = unordered_multiset<T,Hash,Eq>;
template<class K, class V, class Hash=ProconHash<K>, class Eq=equal_to<K>>
using HashMultimap = unordered_multimap<K,V,Hash,Eq>;
template<class T>
auto vec_make(i64 n, T x) {
return vector<T>(n, x);
}
template<class T, class... Args, SFINAE(sizeof...(Args) >= 2)>
auto vec_make(i64 n, Args... args) {
auto inner = vec_make<T>(args...);
return vector<decltype(inner)>(n, inner);
}
template<class T>
auto vec_reserve(i64 cap) {
vector<T> res;
res.reserve(cap);
return res;
}
template<class T=i64>
auto vec_iota(i64 n, T init={}) {
vector<i64> res(n);
ALL(iota, res, init);
return res;
}
template<class ForwardIt, class BinaryOp>
auto vec_scan(ForwardIt first, ForwardIt last,
typename iterator_traits<ForwardIt>::value_type init,
BinaryOp op)
{
using T = typename iterator_traits<ForwardIt>::value_type;
auto res = vec_reserve<T>(distance(first,last)+1);
res.emplace_back(init);
for(; first != last; ++first) {
init = op(move(init), *first);
res.emplace_back(init);
}
return res;
}
template<class ForwardIt>
auto vec_cum(ForwardIt first, ForwardIt last) {
using T = typename iterator_traits<ForwardIt>::value_type;
return vec_scan(first, last, T{}, plus<>{});
}
template<class T, class Comp, class Cont=vector<T>>
auto priority_queue_make(const Comp& comp, Cont&& cont={}) {
return priority_queue<T,remove_reference_t<Cont>,Comp>(comp, forward<Cont>(cont));
}
template<class T, class Comp>
auto priority_queue_reserve(const Comp& comp, i64 cap) {
return priority_queue<T,vector<T>,Comp>(comp, vec_reserve<T>(cap));
}
template<class T, size_t N, size_t... NS>
struct ArrayType {
using type = array<class ArrayType<T,NS...>::type,N>;
};
template<class T, size_t N>
struct ArrayType<T,N> {
using type = array<T,N>;
};
template<class T, size_t... NS>
using Array = typename ArrayType<T,NS...>::type;
template<class T, size_t N>
T& array_at(Array<T,N>& ary, i64 i) {
return ary[i];
}
template<class T, size_t N, size_t... NS, class... Args>
T& array_at(Array<T,N,NS...>& ary, i64 i, Args... args) {
return array_at<T,NS...>(ary[i], args...);
}
template<class T, size_t N>
const T& array_at(const Array<T,N>& ary, i64 i) {
return ary[i];
}
template<class T, size_t N, size_t... NS, class... Args>
const T& array_at(const Array<T,N,NS...>& ary, i64 i, Args... args) {
return array_at<T,NS...>(ary[i], args...);
}
template<class T, class C>
T POP(stack<T,C>& stk) {
T x = stk.top(); stk.pop();
return x;
}
template<class T, class C>
T POP(queue<T,C>& que) {
T x = que.front(); que.pop();
return x;
}
template<class T, class C, class Comp>
T POP(priority_queue<T,C,Comp>& que) {
T x = que.top(); que.pop();
return x;
}
// }}}
// input {{{
template<class T, class Enable=void>
struct Scan {
static T scan(istream& in) {
T res;
in >> res;
return res;
}
};
template<class T, class Enable=void>
struct Scan1;
template<class T>
struct Scan1<T,enable_if_t<is_integral<T>::value && !is_same<T,bool>::value>> {
static T scan1(istream& in) {
return Scan<T>::scan(in) - 1;
}
};
template<class T1, class T2>
struct Scan<pair<T1,T2>> {
static pair<T1,T2> scan(istream& in) {
T1 x = Scan<T1>::scan(in);
T2 y = Scan<T2>::scan(in);
return {x,y};
}
};
template<class T1, class T2>
struct Scan1<pair<T1,T2>> {
static pair<T1,T2> scan1(istream& in) {
T1 x = Scan1<T1>::scan1(in);
T2 y = Scan1<T2>::scan1(in);
return {x,y};
}
};
template<class T>
tuple<T> tuple_scan_impl(istream& in) {
return make_tuple(Scan<T>::scan(in));
}
template<class T, class... TS, SFINAE(sizeof...(TS) > 0)>
tuple<T,TS...> tuple_scan_impl(istream& in) {
auto head = make_tuple(Scan<T>::scan(in));
return tuple_cat(head, tuple_scan_impl<TS...>(in));
}
template<class... TS>
struct Scan<tuple<TS...>> {
static tuple<TS...> scan(istream& in) {
return tuple_scan_impl<TS...>(in);
}
};
template<class T>
tuple<T> tuple_scan1_impl(istream& in) {
return make_tuple(Scan1<T>::scan1(in));
}
template<class T, class... TS, SFINAE(sizeof...(TS) > 0)>
tuple<T,TS...> tuple_scan1_impl(istream& in) {
auto head = make_tuple(Scan1<T>::scan1(in));
return tuple_cat(head, tuple_scan1_impl<TS...>(in));
}
template<class... TS>
struct Scan1<tuple<TS...>> {
static tuple<TS...> scan1(istream& in) {
return tuple_scan1_impl<TS...>(in);
}
};
template<class T=i64>
T RD() {
return Scan<T>::scan(cin);
}
template<class T=i64>
T RD1() {
return Scan1<T>::scan1(cin);
}
template<class T=i64>
auto RD_VEC(i64 n) {
auto res = vec_reserve<T>(n);
LOOP(n) {
res.emplace_back(RD<T>());
}
return res;
}
template<class T=i64>
auto RD1_VEC(i64 n) {
auto res = vec_reserve<T>(n);
LOOP(n) {
res.emplace_back(RD1<T>());
}
return res;
}
template<class T=i64>
auto RD_VEC2(i64 h, i64 w) {
auto res = vec_reserve<vector<T>>(h);
LOOP(h) {
res.emplace_back(RD_VEC<T>(w));
}
return res;
}
template<class T=i64>
auto RD1_VEC2(i64 h, i64 w) {
auto res = vec_reserve<vector<T>>(h);
LOOP(h) {
res.emplace_back(RD1_VEC<T>(w));
}
return res;
}
// }}}
// output {{{
template<class T, class Enable=void>
struct Fmt {
static void fmt(ostream& out, const T& x) { out << x; }
};
template<class T>
void fmt_write(ostream& out, const T& x) {
Fmt<T>::fmt(out, x);
}
template<class T>
string FMT_STR(const T& x) {
ostringstream out;
fmt_write(out, x);
return out.str();
}
template<class... TS>
struct Fmt<tuple<TS...>> {
static void fmt(ostream& out, const tuple<TS...>& t) {
tuple_enumerate(t, [&out](i64 i, const auto& e) {
if(i != 0) out << ' ';
fmt_write(out, e);
});
}
};
template<class T1, class T2>
struct Fmt<pair<T1,T2>> {
static void fmt(ostream& out, const pair<T1,T2>& p) {
return fmt_write(out, make_tuple(p.first,p.second));
}
};
template<class C>
struct Fmt<C,enable_if_t<is_container<C>::value>> {
static void fmt(ostream& out, const C& c) {
for(auto it = begin(c); it != end(c); ++it) {
if(it != begin(c)) out << ' ';
fmt_write(out, *it);
}
}
};
void PRINT() {}
template<class T, class... TS>
void PRINT(const T& x, const TS&... args) {
fmt_write(cout, x);
if(sizeof...(args) > 0) {
cout << ' ';
PRINT(args...);
}
}
template<class... TS>
void PRINTLN(const TS&... args) {
PRINT(args...);
cout << '\n';
}
// }}}
// debug {{{
template<class T, class Enable=void>
struct Dbg {
static void dbg(ostream& out, const T& x) { out << x; }
};
template<class T>
void dbg_write(ostream& out, const T& x) {
Dbg<T>::dbg(out, x);
}
template<class T>
string DBG_STR(const T& x) {
ostringstream out;
dbg_write(out, x);
return out.str();
}
template<>
struct Dbg<i64> {
static void dbg(ostream& out, i64 x) {
if(x == INF)
out << "INF";
else if(x == -INF)
out << "-INF";
else
out << x;
}
};
template<>
struct Dbg<Real> {
static void dbg(ostream& out, Real x) {
if(EQ_EXACT(x, FINF))
out << "FINF";
else if(EQ_EXACT(x, -FINF))
out << "-FINF";
else
out << x;
}
};
template<class T, size_t N>
struct Dbg<T[N]> {
static void dbg(ostream& out, const T (&ary)[N]) {
out << "[";
REP(i, N) {
if(i != 0) out << ",";
dbg_write(out, ary[i]);
}
out << "]";
}
};
template<size_t N>
struct Dbg<char[N]> {
static void dbg(ostream& out, const char (&s)[N]) {
out << s;
}
};
template<class T>
void DBG_IMPL(i64 line, const char* expr, const T& value) {
cerr << "[L " << line << "]: ";
cerr << expr << " = ";
dbg_write(cerr, value);
cerr << "\n";
}
void DBG_IMPL_HELPER() {}
template<class T, class... TS>
void DBG_IMPL_HELPER(const T& x, const TS&... args) {
dbg_write(cerr, x);
if(sizeof...(args) > 0) {
cerr << ",";
DBG_IMPL_HELPER(args...);
}
}
template<class... TS>
void DBG_IMPL(i64 line, const char* expr, const TS&... value) {
cerr << "[L " << line << "]: ";
cerr << "(" << expr << ") = (";
DBG_IMPL_HELPER(value...);
cerr << ")\n";
}
template<size_t N, class T, SFINAE(rank<T>::value == 0)>
void DBG_DP_IMPL_HELPER(ostream& out, const T& x, const array<i64,N>&, const array<i64,N>&) {
dbg_write(out, x);
}
template<size_t N, class T, SFINAE(rank<T>::value > 0)>
void DBG_DP_IMPL_HELPER(ostream& out, const T& x, const array<i64,N>& sizes, const array<i64,N>& offs) {
i64 k = N - rank<T>::value;
i64 off = offs[k];
i64 siz = sizes[k];
if(siz == 0) siz = extent<T>::value - off;
out << "[";
FOR(i, off, off+siz) {
if(i != off) out << ",";
DBG_DP_IMPL_HELPER(out, x[i], sizes, offs);
}
out << "]";
}
template<class T, SFINAE(rank<T>::value > 0)>
void DBG_DP_IMPL(i64 line, const char* expr, const T& dp,
const array<i64,rank<T>::value>& sizes={},
const array<i64,rank<T>::value>& offs={})
{
cerr << "[L " << line << "]: ";
cerr << expr << " = ";
DBG_DP_IMPL_HELPER<rank<T>::value>(cerr, dp, sizes, offs);
cerr << "\n";
}
template<class T>
void DBG_GRID_IMPL(i64 line, const char* expr, const vector<T>& grid) {
cerr << "[L " << line << "]: ";
cerr << expr << ":\n";
for(const auto& row : grid) {
dbg_write(cerr, row);
cerr << "\n";
}
cerr << "\n";
}
#ifdef PROCON_LOCAL
#define DBG(args...) DBG_IMPL(__LINE__, CPP_STR_I(args), args)
#define DBG_DP(args...) DBG_DP_IMPL(__LINE__, CPP_STR_I(args), args)
#define DBG_GRID(args...) DBG_GRID_IMPL(__LINE__, CPP_STR_I(args), args)
#else
#define DBG(args...)
#define DBG_DP(args...)
#define DBG_GRID(args...)
#endif
// }}}
// init {{{
struct ProconInit {
ProconInit() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cin.exceptions(ios::failbit | ios::badbit);
cout << fixed << setprecision(COUT_PREC);
#ifdef PROCON_LOCAL
cerr << fixed << setprecision(2);
#endif
if(COUT_AUTOFLUSH)
cout << unitbuf;
}
} PROCON_INIT;
// }}}
// }}}
//--------------------------------------------------------------------
constexpr int N = 1'000'000;
//constexpr int N = 10;
vector<char> cs; // cs[v]: ノード v の最後の文字
vector<int> ls; // ls[v]: ノード v の文字列長 (ls[0]==0)
vector<vector<int>> pss; // pss[k][v]: ノード v の 2^k 個上
vector<int> vs; // vs[i]: i 回目の操作終了時のノード (vs[0]==0)
int n_v;
int n_op;
void Init() {
cs.assign(N+1, '$');
ls.assign(N+1, 0);
pss.assign(20,vector<int>(N+1,-1));
vs.assign(N+1, 0);
n_v = 1;
n_op = 0;
}
void TypeLetter(char L) {
//DBG(cs);
//DBG(ls);
//DBG(pss);
//DBG(vs);
//DBG(n_v);
//DBG(n_op);
// 前回のノードに新たな子ノードが加わる
int p = vs[n_op++];
int v = n_v++;
cs[v] = L;
ls[v] = ls[p] + 1;
pss[0][v] = p;
FOR(k, 1, 20) {
int w = pss[k-1][pss[k-1][v]];
if(w == -1) break;
pss[k][v] = w;
}
vs[n_op] = v;
}
void UndoCommands(int U) {
//DBG(cs);
//DBG(ls);
//DBG(pss);
//DBG(vs);
//DBG(n_v);
//DBG(n_op);
// 既存のノードへ戻る
int v = vs[n_op-U];
++n_op;
vs[n_op] = v;
}
char GetLetter(int P) {
//DBG(cs);
//DBG(ls);
//DBG(pss);
//DBG(vs);
//DBG(n_v);
//DBG(n_op);
int v = vs[n_op];
ASSERT(v != 0);
int n_back = ls[v] - (P+1);
REP(k, 20) {
if(n_back & BIT_I(k)) {
v = pss[k][v];
}
}
ASSERT(v != 0);
return cs[v];
}
#ifdef PROCON_LOCAL
signed main() {
Init();
TypeLetter('a');
TypeLetter('b');
ASSERT(GetLetter(1) == 'b');
TypeLetter('d');
UndoCommands(2);
UndoCommands(1);
ASSERT(GetLetter(2) == 'd');
TypeLetter('e');
UndoCommands(1);
UndoCommands(5);
TypeLetter('c');
ASSERT(GetLetter(2) == 'c');
UndoCommands(2);
ASSERT(GetLetter(2) == 'd');
EXIT();
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
63 ms |
87472 KB |
Output is correct |
| 2 |
Correct |
62 ms |
87544 KB |
Output is correct |
| 3 |
Correct |
71 ms |
87600 KB |
Output is correct |
| 4 |
Correct |
61 ms |
87544 KB |
Output is correct |
| 5 |
Correct |
65 ms |
87472 KB |
Output is correct |
| 6 |
Correct |
63 ms |
87472 KB |
Output is correct |
| 7 |
Correct |
64 ms |
87472 KB |
Output is correct |
| 8 |
Correct |
64 ms |
87472 KB |
Output is correct |
| 9 |
Correct |
64 ms |
87544 KB |
Output is correct |
| 10 |
Correct |
64 ms |
87600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
87472 KB |
Output is correct |
| 2 |
Correct |
63 ms |
87544 KB |
Output is correct |
| 3 |
Correct |
61 ms |
87472 KB |
Output is correct |
| 4 |
Correct |
67 ms |
87672 KB |
Output is correct |
| 5 |
Correct |
61 ms |
87544 KB |
Output is correct |
| 6 |
Correct |
60 ms |
87476 KB |
Output is correct |
| 7 |
Correct |
62 ms |
87472 KB |
Output is correct |
| 8 |
Correct |
62 ms |
87544 KB |
Output is correct |
| 9 |
Correct |
61 ms |
87472 KB |
Output is correct |
| 10 |
Correct |
61 ms |
87472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
87472 KB |
Output is correct |
| 2 |
Correct |
64 ms |
87472 KB |
Output is correct |
| 3 |
Correct |
64 ms |
87472 KB |
Output is correct |
| 4 |
Correct |
63 ms |
87472 KB |
Output is correct |
| 5 |
Correct |
63 ms |
87480 KB |
Output is correct |
| 6 |
Correct |
63 ms |
87600 KB |
Output is correct |
| 7 |
Correct |
64 ms |
87600 KB |
Output is correct |
| 8 |
Correct |
62 ms |
87600 KB |
Output is correct |
| 9 |
Correct |
61 ms |
87472 KB |
Output is correct |
| 10 |
Correct |
65 ms |
87472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
310 ms |
91524 KB |
Output is correct |
| 2 |
Correct |
348 ms |
91568 KB |
Output is correct |
| 3 |
Correct |
343 ms |
92696 KB |
Output is correct |
| 4 |
Correct |
369 ms |
94020 KB |
Output is correct |
| 5 |
Correct |
325 ms |
92720 KB |
Output is correct |
| 6 |
Correct |
271 ms |
91824 KB |
Output is correct |
| 7 |
Correct |
343 ms |
93744 KB |
Output is correct |
| 8 |
Correct |
338 ms |
93360 KB |
Output is correct |
| 9 |
Correct |
352 ms |
92208 KB |
Output is correct |
| 10 |
Correct |
267 ms |
91804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
386 ms |
92464 KB |
Output is correct |
| 2 |
Correct |
456 ms |
93748 KB |
Output is correct |
| 3 |
Correct |
352 ms |
93236 KB |
Output is correct |
| 4 |
Correct |
409 ms |
95152 KB |
Output is correct |
| 5 |
Correct |
290 ms |
92464 KB |
Output is correct |
| 6 |
Correct |
301 ms |
92336 KB |
Output is correct |
| 7 |
Correct |
317 ms |
92336 KB |
Output is correct |
| 8 |
Correct |
471 ms |
94000 KB |
Output is correct |
| 9 |
Correct |
475 ms |
93956 KB |
Output is correct |
| 10 |
Correct |
272 ms |
91696 KB |
Output is correct |
