/*
lib: https://github.com/old-yan/CP-template
author: oldyan
*/
#include <algorithm>
#include <bit>
#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstring>
#include <functional>
#include <immintrin.h>
#include <limits>
#include <numeric>
#include <random>
#include <string>
#include <type_traits>
#include <vector>
#ifndef __OY_STATICMONTGOMERYMODINT64__
#define __OY_STATICMONTGOMERYMODINT64__
#ifdef _MSC_VER
#endif
namespace OY {
template <uint64_t P, bool IsPrime, typename = typename std::enable_if<(P % 2 && P > 1 && P < uint64_t(1) << 62)>::type>
struct StaticMontgomeryModInt64 {
using mint = StaticMontgomeryModInt64<P, IsPrime>;
using mod_type = uint64_t;
using fast_type = mod_type;
#ifndef _MSC_VER
using long_type = __uint128_t;
#endif
static constexpr mod_type _conv(mod_type x) { return x * (mod_type(2) - P * x); }
static constexpr mod_type _shift1(mod_type x) { return x * 2 % P; }
static constexpr mod_type _shift4(mod_type x) { return _shift1(_shift1(_shift1(_shift1(x)))); }
static constexpr mod_type _shift16(mod_type x) { return _shift4(_shift4(_shift4(_shift4(x)))); }
static constexpr mod_type _shift64(mod_type x) { return _shift16(_shift16(_shift16(_shift16(x)))); }
static constexpr mod_type pinv = -_conv(_conv(_conv(_conv(_conv(P)))));
static constexpr mod_type ninv = _shift64(_shift64(1));
fast_type m_val;
static mod_type _mod(uint64_t val) { return val % mod(); }
static fast_type _init(mod_type val) { return _raw_init(_mod(val)); }
static fast_type _raw_init(mod_type val) { return _mul(val, ninv); }
#ifdef _MSC_VER
static fast_type _reduce(mod_type high, mod_type low) {
uint64_t _, res, low2 = _umul128(_umul128(low, pinv, &_), mod(), &res);
if (low2 > -low || (low2 == -low && low)) ++res;
return res + high;
#else
static fast_type _reduce(long_type val) {
return (val + long_type(mod_type(val) * pinv) * mod()) >> 64;
#endif
}
static constexpr fast_type _reduce_zero(mod_type x) { return x == mod() ? 0 : x; }
static constexpr fast_type _strict_reduce(fast_type val) { return val >= mod() ? val - mod() : val; }
static fast_type _mul(fast_type a, fast_type b) {
#ifdef _MSC_VER
mod_type high, low;
low = _umul128(a, b, &high);
return _reduce(high, low);
#else
return _reduce(long_type(a) * b);
#endif
}
StaticMontgomeryModInt64() = default;
template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value>::type * = nullptr>
StaticMontgomeryModInt64(Tp val) {
auto x = val % int64_t(mod());
if (x < 0) x += mod();
m_val = _raw_init(x);
}
template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value>::type * = nullptr>
StaticMontgomeryModInt64(Tp val) : m_val{_init(val)} {}
static mint _raw(fast_type val) {
mint res;
res.m_val = val;
return res;
}
static mint raw(mod_type val) { return _raw(_raw_init(val)); }
static constexpr mod_type mod() { return P; }
mod_type val() const {
#ifdef _MSC_VER
mod_type res = _reduce(0, m_val);
#else
mod_type res = _reduce(m_val);
#endif
return _reduce_zero(res);
}
mint pow(uint64_t n) const {
fast_type res = _raw_init(1), b = m_val;
while (n) {
if (n & 1) res = _mul(res, b);
b = _mul(b, b), n >>= 1;
}
return _raw(res);
}
mint inv() const {
if constexpr (IsPrime)
return inv_Fermat();
else
return inv_exgcd();
}
mint inv_exgcd() const {
mod_type x = mod(), y = val(), m0 = 0, m1 = 1;
while (y) {
mod_type z = x / y;
x -= y * z, m0 -= m1 * z, std::swap(x, y), std::swap(m0, m1);
}
if (m0 >= mod()) m0 += mod() / x;
return m0;
}
mint inv_Fermat() const { return pow(mod() - 2); }
mint &operator++() {
(*this) += raw(1);
return *this;
}
mint &operator--() {
(*this) += raw(mod() - 1);
return *this;
}
mint operator++(int) {
mint old(*this);
++*this;
return old;
}
mint operator--(int) {
mint old(*this);
--*this;
return old;
}
mint &operator+=(const mint &rhs) {
fast_type val1 = m_val + rhs.m_val, val2 = val1 - mod() * 2;
m_val = int64_t(val2) < 0 ? val1 : val2;
return *this;
}
mint &operator-=(const mint &rhs) {
fast_type val1 = m_val - rhs.m_val, val2 = val1 + mod() * 2;
m_val = int64_t(val1) < 0 ? val2 : val1;
return *this;
}
mint &operator*=(const mint &rhs) {
m_val = _mul(m_val, rhs.m_val);
return *this;
}
mint &operator/=(const mint &rhs) { return *this *= rhs.inv(); }
mint operator+() const { return *this; }
mint operator-() const { return _raw(m_val ? mod() * 2 - m_val : 0); }
bool operator==(const mint &rhs) const { return _strict_reduce(m_val) == _strict_reduce(rhs.m_val); }
bool operator!=(const mint &rhs) const { return _strict_reduce(m_val) != _strict_reduce(rhs.m_val); }
bool operator<(const mint &rhs) const { return _strict_reduce(m_val) < _strict_reduce(rhs.m_val); }
bool operator>(const mint &rhs) const { return _strict_reduce(m_val) > _strict_reduce(rhs.m_val); }
bool operator<=(const mint &rhs) const { return _strict_reduce(m_val) <= _strict_reduce(rhs.m_val); }
bool operator>=(const mint &rhs) const { return _strict_reduce(m_val) >= _strict_reduce(rhs.m_val); }
template <typename Tp>
explicit operator Tp() const { return Tp(val()); }
friend mint operator+(const mint &a, const mint &b) { return mint(a) += b; }
friend mint operator-(const mint &a, const mint &b) { return mint(a) -= b; }
friend mint operator*(const mint &a, const mint &b) { return mint(a) *= b; }
friend mint operator/(const mint &a, const mint &b) { return mint(a) /= b; }
};
template <typename Istream, uint64_t P, bool IsPrime>
Istream &operator>>(Istream &is, StaticMontgomeryModInt64<P, IsPrime> &x) {
uint64_t val;
is >> val;
x.m_val = StaticMontgomeryModInt64<P, IsPrime>::_raw_init(val);
return is;
}
template <typename Ostream, uint64_t P, bool IsPrime>
Ostream &operator<<(Ostream &os, const StaticMontgomeryModInt64<P, IsPrime> &x) { return os << x.val(); }
using mgint4611686018427387847 = StaticMontgomeryModInt64<4611686018427387847, true>;
}
#endif
#ifndef __OY_LINKBUCKET__
#define __OY_LINKBUCKET__
namespace OY {
namespace LBC {
using size_type = uint32_t;
template <typename Tp>
class LinkBucket {
struct node {
Tp m_value;
size_type m_next;
};
struct iterator {
node *m_item;
size_type m_id;
iterator(node *item, size_type id) : m_item(item), m_id(id) {}
iterator &operator++() {
m_id = m_item[m_id].m_next;
return *this;
}
iterator operator++(int) {
iterator old(*this);
m_id = m_item[m_id].m_next;
return old;
}
Tp &operator*() const { return m_item[m_id].m_value; }
bool operator==(const iterator &rhs) const { return m_id == rhs.m_id; }
bool operator!=(const iterator &rhs) const { return m_id != rhs.m_id; }
};
struct Bucket {
LinkBucket *m_lbc;
size_type m_buc_id;
Bucket(LinkBucket *lbc, size_type buc_id) : m_lbc(lbc), m_buc_id(buc_id) {}
bool empty() const { return !~m_lbc->m_bucket[m_buc_id]; }
Tp &front() { return m_lbc->m_item[m_lbc->m_bucket[m_buc_id]].m_value; }
void push_front(const Tp &val) {
m_lbc->m_item[m_lbc->m_cursor].m_value = val;
m_lbc->m_item[m_lbc->m_cursor].m_next = m_lbc->m_bucket[m_buc_id];
m_lbc->m_bucket[m_buc_id] = m_lbc->m_cursor++;
}
void pop_front() { m_lbc->m_bucket[m_buc_id] = m_lbc->m_item[m_lbc->m_bucket[m_buc_id]].m_next; }
iterator begin() const { return iterator(m_lbc->m_item.data(), m_lbc->m_bucket[m_buc_id]); }
iterator end() const { return iterator(m_lbc->m_item.data(), -1); }
};
std::vector<size_type> m_bucket;
std::vector<node> m_item;
size_type m_bucket_cnt, m_cursor;
public:
LinkBucket(size_type bucket_cnt = 0, size_type item_cnt = 0) { resize(bucket_cnt, item_cnt); }
void resize(size_type bucket_cnt, size_type item_cnt) {
if (!(m_bucket_cnt = bucket_cnt)) return;
m_bucket.assign(m_bucket_cnt, -1), m_item.resize(item_cnt), m_cursor = 0;
}
Bucket operator[](size_type buc_id) { return Bucket(this, buc_id); }
Bucket operator[](size_type buc_id) const { return Bucket((LinkBucket<Tp> *)this, buc_id); }
void swap(size_type buc_id1, size_type buc_id2) { std::swap(m_bucket[buc_id1], m_bucket[buc_id2]); }
void merge(size_type buc_id, size_type rhs) {
size_type cur = m_bucket[rhs];
if (!~cur) return;
while (~m_item[cur].m_next) cur = m_item[cur].m_next;
m_item[cur].m_next = m_bucket[buc_id], m_bucket[buc_id] = m_bucket[rhs], m_bucket[rhs] = 0;
}
iterator bucket_begin(size_type buc_id) { return iterator(m_item, m_bucket[buc_id]); }
iterator bucket_end(size_type = 0) { return iterator(m_item, -1); }
};
}
};
#endif
#ifndef __OY_LINUXIO__
#define __OY_LINUXIO__
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <string>
#include <vector>
#ifdef __unix__
#include <sys/mman.h>
#include <sys/stat.h>
#endif
#if __cpp_constexpr >= 201907L
#define CONSTEXPR20 constexpr
#define INLINE20 constexpr
#else
#define CONSTEXPR20
#define INLINE20 inline
#endif
#define cin OY::LinuxIO::InputHelper<>::get_instance()
#define cout OY::LinuxIO::OutputHelper::get_instance()
#define endl '\n'
#ifndef INPUT_FILE
#define INPUT_FILE "in.txt"
#endif
#ifndef OUTPUT_FILE
#define OUTPUT_FILE "out.txt"
#endif
namespace OY {
namespace LinuxIO {
static constexpr size_t INPUT_BUFFER_SIZE = 1 << 26, OUTPUT_BUFFER_SIZE = 1 << 20;
#ifdef OY_LOCAL
static constexpr char input_file[] = INPUT_FILE, output_file[] = OUTPUT_FILE;
#else
static constexpr char input_file[] = "", output_file[] = "";
#endif
template <typename U, size_t E>
struct TenPow {
static constexpr U value = TenPow<U, E - 1>::value * 10;
};
template <typename U>
struct TenPow<U, 0> {
static constexpr U value = 1;
};
struct InputPre {
uint32_t m_data[0x10000];
CONSTEXPR20 InputPre() {
std::fill(m_data, m_data + 0x10000, -1);
for (size_t i = 0, val = 0; i != 10; i++)
for (size_t j = 0; j != 10; j++) m_data[0x3030 + i + (j << 8)] = val++;
}
};
struct OutputPre {
uint32_t m_data[10000];
CONSTEXPR20 OutputPre() {
uint32_t *c = m_data;
for (size_t i = 0; i != 10; i++)
for (size_t j = 0; j != 10; j++)
for (size_t k = 0; k != 10; k++)
for (size_t l = 0; l != 10; l++) *c++ = i + (j << 8) + (k << 16) + (l << 24) + 0x30303030;
}
};
template <size_t MMAP_SIZE = 1 << 30>
struct InputHelper {
static INLINE20 InputPre pre{};
char *m_p, *m_c, *m_end;
InputHelper(FILE *file = stdin) {
#ifdef __unix__
struct stat _stat;
auto fd = fileno(file);
fstat(fd, &_stat);
m_c = m_p = (char *)mmap(nullptr, _stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
m_end = m_p + _stat.st_size;
#else
uint32_t size = fread(m_c = m_p = new char[INPUT_BUFFER_SIZE], 1, INPUT_BUFFER_SIZE, file);
m_end = m_p + size;
#endif
}
static InputHelper<MMAP_SIZE> &get_instance() {
static InputHelper<MMAP_SIZE> s_obj(*input_file ? fopen(input_file, "rt") : stdin);
return s_obj;
}
template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &x) {
x = 0;
while (!isdigit(*m_c)) m_c++;
x = *m_c++ ^ '0';
while (~pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)]) x = x * 100 + pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)++];
if (isdigit(*m_c)) x = x * 10 + (*m_c++ ^ '0');
return *this;
}
template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &x) {
typename std::make_unsigned<Tp>::type t{};
bool sign{};
while (!isdigit(*m_c)) sign = (*m_c++ == '-');
t = *m_c++ ^ '0';
while (~pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)]) t = t * 100 + pre.m_data[*reinterpret_cast<uint16_t *&>(m_c)++];
if (isdigit(*m_c)) t = t * 10 + (*m_c++ ^ '0');
x = sign ? -t : t;
return *this;
}
InputHelper &operator>>(char &x) {
while (*m_c <= ' ') m_c++;
x = *m_c++;
return *this;
}
InputHelper &operator>>(std::string &x) {
while (*m_c <= ' ') m_c++;
char *c = m_c;
while (*c > ' ') c++;
x.assign(m_c, c - m_c), m_c = c;
return *this;
}
InputHelper &operator>>(std::string_view &x) {
while (*m_c <= ' ') m_c++;
char *c = m_c;
while (*c > ' ') c++;
x = std::string_view(m_c, c - m_c), m_c = c;
return *this;
}
};
struct OutputHelper {
static INLINE20 OutputPre pre{};
FILE *m_file;
char m_p[OUTPUT_BUFFER_SIZE], *m_c, *m_end;
OutputHelper(FILE *file = stdout) {
m_file = file;
m_c = m_p, m_end = m_p + OUTPUT_BUFFER_SIZE;
}
~OutputHelper() { flush(); }
static OutputHelper &get_instance() {
static OutputHelper s_obj(*output_file ? fopen(output_file, "wt") : stdout);
return s_obj;
}
void flush() { fwrite(m_p, 1, m_c - m_p, m_file), m_c = m_p; }
OutputHelper &operator<<(char x) {
if (m_end - m_c < 20) flush();
*m_c++ = x;
return *this;
}
OutputHelper &operator<<(std::string_view s) {
if (m_end - m_c < s.size()) flush();
memcpy(m_c, s.data(), s.size()), m_c += s.size();
return *this;
}
OutputHelper &operator<<(uint64_t x) {
if (m_end - m_c < 20) flush();
#define CASEW(w) \
case TenPow<uint64_t, w - 1>::value... TenPow<uint64_t, w>::value - 1: \
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint64_t, w - 4>::value]; \
m_c += 4, x %= TenPow<uint64_t, w - 4>::value;
switch (x) {
CASEW(19);
CASEW(15);
CASEW(11);
CASEW(7);
case 100 ... 999:
*(uint32_t *)m_c = pre.m_data[x * 10];
m_c += 3;
break;
CASEW(18);
CASEW(14);
CASEW(10);
CASEW(6);
case 10 ... 99:
*(uint32_t *)m_c = pre.m_data[x * 100];
m_c += 2;
break;
CASEW(17);
CASEW(13);
CASEW(9);
CASEW(5);
case 0 ... 9:
*m_c++ = '0' + x;
break;
default:
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint64_t, 16>::value];
m_c += 4;
x %= TenPow<uint64_t, 16>::value;
CASEW(16);
CASEW(12);
CASEW(8);
case 1000 ... 9999:
*(uint32_t *)m_c = pre.m_data[x];
m_c += 4;
break;
}
#undef CASEW
return *this;
}
OutputHelper &operator<<(uint32_t x) {
if (m_end - m_c < 20) flush();
#define CASEW(w) \
case TenPow<uint32_t, w - 1>::value... TenPow<uint32_t, w>::value - 1: \
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint32_t, w - 4>::value]; \
m_c += 4, x %= TenPow<uint32_t, w - 4>::value;
switch (x) {
default:
*(uint32_t *)m_c = pre.m_data[x / TenPow<uint32_t, 6>::value];
m_c += 4;
x %= TenPow<uint32_t, 6>::value;
CASEW(6);
case 10 ... 99:
*(uint32_t *)m_c = pre.m_data[x * 100];
m_c += 2;
break;
CASEW(9);
CASEW(5);
case 0 ... 9:
*m_c++ = '0' + x;
break;
CASEW(8);
case 1000 ... 9999:
*(uint32_t *)m_c = pre.m_data[x];
m_c += 4;
break;
CASEW(7);
case 100 ... 999:
*(uint32_t *)m_c = pre.m_data[x * 10];
m_c += 3;
break;
}
#undef CASEW
return *this;
}
OutputHelper &operator<<(int64_t x) {
if (x >= 0)
return (*this) << uint64_t(x);
else
return (*this) << '-' << uint64_t(-x);
}
OutputHelper &operator<<(int32_t x) {
if (x >= 0)
return (*this) << uint32_t(x);
else
return (*this) << '-' << uint32_t(-x);
}
};
}
}
#endif
#ifndef __OY_SEQUENCEHASH__
#define __OY_SEQUENCEHASH__
namespace OY {
namespace SEQHASH {
using size_type = uint32_t;
struct BaseMap {
template <typename Tp>
Tp operator()(const Tp &x) const { return x; }
};
template <typename... Tps>
struct SeqHashInfo;
template <typename Tp>
struct SeqHashInfo<Tp> {
using value_type = Tp;
using mod_type = typename Tp::mod_type;
mod_type m_base;
Tp *m_u{}, *m_ui{}, *m_de{};
Tp _get_base() const { return Tp::raw(m_base); }
void set_base(mod_type base) { m_base = base; }
void set_random_base(mod_type min_base = 128) {
mod_type low = min_base, high = Tp::mod();
set_base(low + std::chrono::steady_clock::now().time_since_epoch().count() * 11995408973635179863ULL % (high - low));
}
void set_random_base_and_prepare(size_type length, mod_type min_base = 128) { set_random_base(min_base), prepare(length); }
void prepare(size_type length) {
prepare_unit(length), prepare_unit_inv(length), prepare_de(length);
}
void prepare_unit(size_type length) {
if (m_u) delete[] m_u;
m_u = new Tp[length + 1];
m_u[0] = Tp::raw(1);
Tp u = Tp::raw(m_base);
for (size_type i = 0; i != length; i++) m_u[i + 1] = m_u[i] * u;
}
void prepare_unit_inv(size_type length) {
if (m_ui) delete[] m_ui;
m_ui = new Tp[length + 1];
m_ui[0] = Tp::raw(1);
Tp ui = Tp::raw(m_base).inv();
for (size_type i = 0; i != length; i++) m_ui[i + 1] = m_ui[i] * ui;
}
void prepare_de(size_type length) {
if (m_de) delete[] m_de;
m_de = new Tp[length + 1];
m_de[0] = Tp::raw(1);
Tp u = Tp::raw(m_base), one = Tp::raw(1), s = one;
for (size_type i = 0; i != length; i++) s *= u, m_de[i + 1] = s - one;
for (size_type i = length - 1; i; i--) m_de[i] *= m_de[i + 1];
Tp inv = m_de[1].inv();
s = one;
for (size_type i = 1; i != length; i++) s *= u, m_de[i] = inv * m_de[i + 1], inv *= s - one;
}
};
template <typename... Tps>
struct SeqHash {
using hash_type = SeqHash<Tps...>;
using info_type = SeqHashInfo<Tps...>;
using Tp = typename info_type::value_type;
static info_type s_info;
size_type m_len;
Tp m_val;
static hash_type single(typename Tp::mod_type val) { return {1, Tp::raw(val)}; }
static hash_type zero(size_type len) { return {len, Tp::raw(0)}; }
static Tp combine(Tp val1, size_type len1, Tp val2, size_type len2) { return val1 + val2 * unit_of(len1); }
static Tp unit_of(size_type i) { return s_info.m_u[i]; }
static Tp unit_inv_of(size_type i) { return s_info.m_ui[i]; }
static Tp unit_de_inv_of(size_type i) { return s_info.m_de[i]; }
SeqHash() = default;
SeqHash(size_type len, Tp val) : m_len(len), m_val(val) {}
template <typename Iterator, typename Mapping = BaseMap>
SeqHash(Iterator first, Iterator last, Mapping &&map = Mapping()) {
m_len = last - first, m_val = 0;
for (size_type i = 0; i != m_len; i++) m_val += Tp::raw(map(*(first + i))) * unit_of(i);
}
template <typename Mapping = BaseMap>
SeqHash(const std::string &s, Mapping &&map = Mapping()) : SeqHash(s.begin(), s.end(), map) {}
template <typename ValueType, typename Mapping = BaseMap>
SeqHash(const std::vector<ValueType> &v, Mapping &&map = Mapping()) : SeqHash(v.begin(), v.end(), map) {}
hash_type append_left(const hash_type &lhs) const { return {lhs.m_len + m_len, lhs.m_val + m_val * unit_of(lhs.m_len)}; }
hash_type append_right(const hash_type &rhs) const { return {m_len + rhs.m_len, m_val + rhs.m_val * unit_of(m_len)}; }
hash_type remove_prefix(const hash_type &pre) const { return {m_len - pre.m_len, (m_val - pre.m_val) * unit_inv_of(pre.m_len)}; }
hash_type remove_suffix(const hash_type &suf) const { return {m_len - suf.m_len, m_val - suf.m_val * unit_of(m_len - suf.m_len)}; }
hash_type repeat_for(size_type times) const { return {m_len * times, m_val * (unit_of(m_len * times) - Tp::raw(1)) * unit_de_inv_of(m_len)}; }
bool operator==(const hash_type &rhs) const { return m_len == rhs.m_len && m_val == rhs.m_val; }
bool operator!=(const hash_type &rhs) const { return m_len != rhs.m_len || m_val != rhs.m_val; }
bool operator<(const hash_type &rhs) const { return m_len < rhs.m_len || (m_len == rhs.m_len && m_val < rhs.m_val); }
bool operator<=(const hash_type &rhs) const { return m_len < rhs.m_len || (m_len == rhs.m_len && m_val <= rhs.m_val); }
bool operator>(const hash_type &rhs) const { return m_len > rhs.m_len || (m_len == rhs.m_len && m_val > rhs.m_val); }
bool operator>=(const hash_type &rhs) const { return m_len > rhs.m_len || (m_len == rhs.m_len && m_val >= rhs.m_val); }
friend hash_type operator+(const hash_type &lhs, const hash_type &rhs) { return {lhs.m_len, lhs.m_val + rhs.m_val}; }
friend hash_type operator-(const hash_type &lhs, const hash_type &rhs) { return {lhs.m_len, lhs.m_val - rhs.m_val}; }
friend hash_type operator+(const hash_type &lhs, Tp rhs) { return {lhs.m_len, lhs.m_val + rhs}; }
friend hash_type operator-(const hash_type &lhs, Tp rhs) { return {lhs.m_len, lhs.m_val - rhs}; }
};
template <typename... Tps>
typename SeqHash<Tps...>::info_type SeqHash<Tps...>::s_info;
template <typename... Tps>
struct SeqHashPresumTable {
using table_type = SeqHashPresumTable<Tps...>;
using hash_type = SeqHash<Tps...>;
using Tp = typename hash_type::Tp;
struct SubSeqHashValue {
size_type m_left;
Tp m_val;
friend bool operator==(const SubSeqHashValue &lhs, const Tp &rhs) { return lhs.m_val == rhs * hash_type::unit_of(lhs.m_left); }
friend bool operator!=(const SubSeqHashValue &lhs, const Tp &rhs) { return lhs.m_val != rhs * hash_type::unit_of(lhs.m_left); }
friend bool operator==(const Tp &lhs, const SubSeqHashValue &rhs) { return lhs * hash_type::unit_of(rhs.m_left) == rhs.m_val; }
friend bool operator!=(const Tp &lhs, const SubSeqHashValue &rhs) { return lhs * hash_type::unit_of(rhs.m_left) != rhs.m_val; }
friend bool operator==(const SubSeqHashValue &lhs, const SubSeqHashValue &rhs) { return lhs.m_val * hash_type::unit_of(rhs.m_left) == rhs.m_val * hash_type::unit_of(lhs.m_left); }
friend bool operator!=(const SubSeqHashValue &lhs, const SubSeqHashValue &rhs) { return lhs.m_val * hash_type::unit_of(rhs.m_left) != rhs.m_val * hash_type::unit_of(lhs.m_left); }
operator Tp() const { return m_val * hash_type::unit_inv_of(m_left); }
};
std::vector<Tp> m_presum;
Tp _raw_dif(size_type left, size_type right) const { return m_presum[right + 1] - m_presum[left]; }
static size_type lcp(const table_type &t1, size_type i1, const table_type &t2, size_type i2, size_type limit) {
if (i1 > i2) return lcp(t2, i2, t1, i1, limit);
size_type low = 0, high = limit, d = i2 - i1;
while (low < high) {
size_type mid = (low + high + 1) / 2;
if (t1._raw_dif(i1, i1 + mid - 1) * hash_type::unit_of(d) == t2._raw_dif(i2, i2 + mid - 1))
low = mid;
else
high = mid - 1;
}
return low;
}
static size_type lcp(const table_type &t1, size_type i1, const table_type &t2, size_type i2) { return lcp(t1, i1, t2, i2, std::min<size_type>(t1.m_presum.size() - 1 - i1, t2.m_presum.size() - 1 - i2)); }
static int compare(const table_type &t1, size_type l1, size_type r1, const table_type &t2, size_type l2, size_type r2) {
size_type len1 = r1 - l1 + 1, len2 = r2 - l2 + 1, len = lcp(t1, l1, t2, l2, std::min(len1, len2));
if (len == len1)
return len == len2 ? 0 : -1;
else if (len == len2)
return 1;
else
return Tp(t1.query_value(l1 + len, l1 + len)) < Tp(t2.query_value(l2 + len, l2 + len)) ? -1 : 1;
}
SeqHashPresumTable() = default;
template <typename InitMapping>
SeqHashPresumTable(size_type length, InitMapping mapping) { resize(length, mapping); }
template <typename Iterator, typename Mapping = BaseMap>
SeqHashPresumTable(Iterator first, Iterator last, Mapping &&map = Mapping()) { reset(first, last, map); }
template <typename Mapping = BaseMap>
SeqHashPresumTable(const std::string &s, Mapping &&map = Mapping()) : SeqHashPresumTable(s.begin(), s.end(), map) {}
template <typename ValueType, typename Mapping = BaseMap>
SeqHashPresumTable(const std::vector<ValueType> &v, Mapping &&map = Mapping()) : SeqHashPresumTable(v.begin(), v.end(), map) {}
template <typename InitMapping>
void resize(size_type length, InitMapping mapping) {
m_presum.resize(length + 1);
const auto u = hash_type::s_info._get_base();
for (size_type i = 0; i != length; i++) m_presum[i + 1] = m_presum[i] + Tp::raw(mapping(i)) * hash_type::unit_of(i);
}
template <typename Iterator, typename Mapping = BaseMap>
void reset(Iterator first, Iterator last, Mapping &&map = Mapping()) {
resize(last - first, [&](size_type i) { return map(*(first + i)); });
}
void reserve(size_type length) { m_presum.clear(), m_presum.reserve(length + 1), m_presum.push_back({}); }
void resize(size_type length) { m_presum.resize(length + 1); }
void clear() { m_presum.clear(), m_presum.push_back({}); }
void push_back(typename Tp::mod_type elem) { m_presum.push_back(m_presum.back() + Tp::raw(elem) * hash_type::unit_of(m_presum.size() - 1)); }
void pop_back() { m_presum.pop_back(); }
SubSeqHashValue query_value(size_type left, size_type right) const { return {left, _raw_dif(left, right)}; }
hash_type query_hash(size_type left, size_type right) const { return {right - left + 1, _raw_dif(left, right) * hash_type::unit_inv_of(left)}; }
};
}
}
#endif
#ifndef __OY_MONOZKWTREE__
#define __OY_MONOZKWTREE__
namespace OY {
namespace MONOZKW {
using size_type = uint32_t;
template <typename Tp, Tp Identity, typename Operation>
struct BaseMonoid {
using value_type = Tp;
static constexpr Tp identity() { return Identity; }
static value_type op(const value_type &x, const value_type &y) { return Operation()(x, y); }
};
template <typename Tp, typename Compare>
struct ChoiceByCompare {
Tp operator()(const Tp &x, const Tp &y) const { return Compare()(x, y) ? y : x; }
};
template <typename Tp, Tp (*Fp)(Tp, Tp)>
struct FpTransfer {
Tp operator()(const Tp &x, const Tp &y) const { return Fp(x, y); }
};
#ifdef __cpp_lib_void_t
template <typename... Tp>
using void_t = std::void_t<Tp...>;
#else
template <typename... Tp>
struct make_void {
using type = void;
};
template <typename... Tp>
using void_t = typename make_void<Tp...>::type;
#endif
template <typename Tp, typename = void>
struct Has_Not_Equal : std::false_type {};
template <typename Tp>
struct Has_Not_Equal<Tp, void_t<decltype(std::declval<Tp>() != std::declval<Tp>())>> : std::true_type {};
template <typename Monoid>
class Tree {
public:
using group = Monoid;
using value_type = typename group::value_type;
private:
size_type m_size, m_cap;
std::vector<value_type> m_sub;
static bool _check_pushup(value_type &old, value_type val) {
if constexpr (Has_Not_Equal<value_type>::value)
return old != val ? old = val, true : false;
else
return old = val, true;
}
public:
Tree(size_type length = 0) { resize(length); }
template <typename InitMapping>
Tree(size_type length, InitMapping mapping) { resize(length, mapping); }
template <typename Iterator>
Tree(Iterator first, Iterator last) { reset(first, last); }
size_type size() const { return m_size; }
void resize(size_type length) {
if (!(m_size = length)) return;
m_cap = 1 << std::max<size_type>(1, std::bit_width(m_size - 1));
m_sub.assign(m_cap * 2, group::identity());
}
template <typename InitMapping>
void resize(size_type length, InitMapping mapping) {
if (!(m_size = length)) return;
m_cap = 1 << std::max<size_type>(1, std::bit_width(m_size - 1));
m_sub.resize(m_cap * 2);
auto sub = m_sub.data();
for (size_type i = 0; i != m_size; i++) sub[m_cap + i] = mapping(i);
std::fill_n(sub + m_cap + m_size, m_cap - m_size, group::identity());
for (size_type len = m_cap / 2, w = 2; len; len >>= 1, w <<= 1)
for (size_type i = len; i != len << 1; i++) sub[i] = group::op(sub[i * 2], sub[i * 2 + 1]);
}
template <typename Iterator>
void reset(Iterator first, Iterator last) {
resize(last - first, [&](size_type i) { return *(first + i); });
}
void modify(size_type i, value_type val) {
auto sub = m_sub.data();
sub[i += m_cap] = val;
while ((i >>= 1) && _check_pushup(sub[i], group::op(sub[i * 2], sub[i * 2 + 1]))) {}
}
void add(size_type i, value_type inc) { modify(i, group::op(inc, query(i))); }
value_type query(size_type i) const { return m_sub[m_cap + i]; }
value_type query(size_type left, size_type right) const {
if (left == right) return query(left);
auto sub = m_sub.data();
value_type res = group::identity();
right++;
if (left)
while (true) {
size_type j = std::countr_zero(left), left2 = left + (size_type(1) << j);
if (left2 > right) break;
res = group::op(res, sub[(m_cap + left) >> j]);
left = left2;
}
while (left < right) {
size_type j = std::bit_width(left ^ right), left2 = left + (size_type(1) << (j - 1));
res = group::op(res, sub[(m_cap + left) >> (j - 1)]);
left = left2;
}
return res;
}
value_type query_all() const { return m_sub[1]; }
template <typename Judger>
size_type max_right(size_type left, Judger &&judge) const {
auto sub = m_sub.data();
value_type val = group::identity();
size_type cur = left, j = -1;
if (cur)
while (true) {
j = std::countr_zero(cur);
size_type next = cur + (size_type(1) << j);
if (next > m_size) break;
value_type a = group::op(val, sub[(m_cap + cur) >> j]);
if (!judge(a)) break;
val = a, cur = next;
}
if (cur != m_size) {
j = std::min<size_type>(j, std::bit_width(m_size - cur));
while (~--j) {
size_type next = cur + (size_type(1) << j);
if (next > m_size) continue;
value_type a = group::op(val, sub[(m_cap + cur) >> j]);
if (!judge(a)) continue;
val = a, cur = next;
}
}
return cur - 1;
}
template <typename Judger>
size_type min_left(size_type right, Judger &&judge) const {
auto sub = m_sub.data();
value_type val = group::identity();
size_type cur = right, j = -1;
do {
j = std::countr_zero(~cur);
size_type next = cur - (1 << j);
value_type a = group::op(sub[(m_cap + cur) >> j], val);
if (!judge(a)) break;
val = a, cur = next;
} while (~cur);
if (~cur) {
j = std::min<size_type>(j, std::bit_width(cur + 1));
while (~--j) {
size_type next = cur - (1 << j);
value_type a = group::op(sub[(m_cap + cur) >> j], val);
if (!judge(a)) continue;
val = a, cur = next;
}
}
return cur + 1;
}
};
template <typename Ostream, typename Monoid>
Ostream &operator<<(Ostream &out, const Tree<Monoid> &x) {
out << "[";
for (size_type i = 0; i != x.size(); i++) {
if (i) out << ", ";
out << x.query(i);
}
return out << "]";
}
}
template <typename Tp, Tp Identity, typename Operation, typename InitMapping, typename TreeType = MONOZKW::Tree<MONOZKW::BaseMonoid<Tp, Identity, Operation>>>
auto make_MonoZkw(MONOZKW::size_type length, Operation op, InitMapping mapping) -> TreeType { return TreeType(length, mapping); }
template <typename Tp, Tp Minimum = std::numeric_limits<Tp>::min()>
using MonoMaxTree = MONOZKW::Tree<MONOZKW::BaseMonoid<Tp, Minimum, MONOZKW::ChoiceByCompare<Tp, std::less<Tp>>>>;
template <typename Tp, Tp Maximum = std::numeric_limits<Tp>::max()>
using MonoMinTree = MONOZKW::Tree<MONOZKW::BaseMonoid<Tp, Maximum, MONOZKW::ChoiceByCompare<Tp, std::greater<Tp>>>>;
template <typename Tp>
using MonoGcdTree = MONOZKW::Tree<MONOZKW::BaseMonoid<Tp, 0, MONOZKW::FpTransfer<Tp, std::gcd<Tp>>>>;
template <typename Tp>
using MonoLcmTree = MONOZKW::Tree<MONOZKW::BaseMonoid<Tp, 1, MONOZKW::FpTransfer<Tp, std::lcm<Tp>>>>;
template <typename Tp, Tp OneMask = Tp(-1)>
using MonoBitAndTree = MONOZKW::Tree<MONOZKW::BaseMonoid<Tp, OneMask, std::bit_and<Tp>>>;
template <typename Tp, Tp ZeroMask = 0>
using MonoBitOrTree = MONOZKW::Tree<MONOZKW::BaseMonoid<Tp, ZeroMask, std::bit_or<Tp>>>;
template <typename Tp, Tp ZeroMask = 0>
using MonoBitXorTree = MONOZKW::Tree<MONOZKW::BaseMonoid<Tp, ZeroMask, std::bit_xor<Tp>>>;
template <typename Tp, Tp Zero = Tp()>
using MonoSumTree = MONOZKW::Tree<MONOZKW::BaseMonoid<Tp, Zero, std::plus<Tp>>>;
}
#endif
/*
lib code is above
temp code is below
*/
void solve_hash() {
using mint = OY::mint4611686018427387847;
using table_type = OY::SEQHASH::SeqHashPresumTable<mint>;
using hash_type = table_type::hash_type;
uint32_t n;
cin >> n;
hash_type::s_info.set_random_base(n);
hash_type::s_info.prepare_unit(std::bit_ceil(n));
hash_type::s_info.prepare_unit_inv(std::bit_ceil(n));
std::vector<std::pair<uint32_t, uint32_t>> ps(n * 2 - 3);
for (uint32_t i = 0; auto &[val, sum] : ps) {
cin >> val;
sum = ++i;
}
std::ranges::sort(ps);
OY::LBC::LinkBucket<uint32_t> dsu(n, n);
std::vector<uint32_t> belong(n), sz(n, 1);
for (uint32_t i = 0; i != n; i++) belong[i] = i, dsu[i].push_front(i);
struct monoid {
using value_type = hash_type;
static value_type identity() { return {}; }
static value_type op(const value_type &x, const value_type &y) { return x.append_right(y); }
};
OY::MONOZKW::Tree<monoid> pre(n, [&](uint32_t i) { return hash_type::single(i); });
OY::MONOZKW::Tree<monoid> suf(n, [&](uint32_t i) { return hash_type::single(n - 1 - i); });
uint64_t ans = 0;
std::vector<std::pair<int, int>> es;
for (auto [val, sum] : ps) {
if (sum < n)
while (true) {
uint32_t low = 0, high = sum + 1;
while (low < high) {
auto mid = (low + high) >> 1;
if (pre.query(0, mid) == suf.query(n - sum - 1, n - sum - 1 + mid))
low = mid + 1;
else
high = mid;
}
if (low > sum) break;
ans += val;
es.emplace_back(low, sum - low);
uint32_t head1 = belong[low], head2 = belong[sum - low];
if (sz[head1] < sz[head2]) {
for (auto x : dsu[head1]) belong[x] = head2, pre.modify(x, hash_type::single(head2)), suf.modify(n - 1 - x, hash_type::single(head2));
dsu.merge(head2, head1), sz[head2] += sz[head1];
} else {
for (auto x : dsu[head2]) belong[x] = head1, pre.modify(x, hash_type::single(head1)), suf.modify(n - 1 - x, hash_type::single(head1));
dsu.merge(head1, head2), sz[head1] += sz[head2];
}
}
else
while (true) {
uint32_t low = 0, high = n * 2 - 1 - sum;
while (low < high) {
auto mid = (low + high) >> 1;
if (pre.query(sum - n + 1, sum - n + 1 + mid) == suf.query(0, mid))
low = mid + 1;
else
high = mid;
}
if (low == n * 2 - 1 - sum) break;
ans += val;
es.emplace_back(sum - n + 1 + low, n - 1 - low);
uint32_t head1 = belong[sum - n + 1 + low], head2 = belong[n - 1 - low];
if (sz[head1] < sz[head2]) {
for (auto x : dsu[head1]) belong[x] = head2, pre.modify(x, hash_type::single(head2)), suf.modify(n - 1 - x, hash_type::single(head2));
dsu.merge(head2, head1), sz[head2] += sz[head1];
} else {
for (auto x : dsu[head2]) belong[x] = head1, pre.modify(x, hash_type::single(head1)), suf.modify(n - 1 - x, hash_type::single(head1));
dsu.merge(head1, head2), sz[head1] += sz[head2];
}
}
}
cout << ans;
}
int main() {
solve_hash();
}