/*
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 <limits>
#include <numeric>
#include <random>
#include <string>
#include <type_traits>
#include <vector>
#ifndef __OY_STATICMODINT32__
#define __OY_STATICMODINT32__
#if __cpp_constexpr >= 201304L
#define CONSTEXPR14 constexpr
#else
#define CONSTEXPR14
#endif
namespace OY {
    template <uint32_t P, bool IsPrime, typename = typename std::enable_if<(P > 1 && P < uint32_t(1) << 31)>::type>
    struct StaticModInt32 {
        using mint = StaticModInt32<P, IsPrime>;
        using mod_type = uint32_t;
        mod_type m_val;
        static constexpr mod_type _reduce_norm(int32_t x) { return x < 0 ? x + mod() : x; }
        static constexpr mod_type _mul(mod_type a, mod_type b) { return uint64_t(a) * b % mod(); }
        constexpr StaticModInt32() = default;
        template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value>::type * = nullptr>
        constexpr StaticModInt32(Tp val) : m_val(_reduce_norm(val % int32_t(mod()))) {}
        template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value>::type * = nullptr>
        constexpr StaticModInt32(Tp val) : m_val(val % mod()) {}
        static CONSTEXPR14 mint raw(mod_type val) {
            mint res{};
            res.m_val = val;
            return res;
        }
        static constexpr mod_type mod() { return P; }
        constexpr mod_type val() const { return m_val; }
        CONSTEXPR14 mint pow(uint64_t n) const {
            mod_type res = 1, b = m_val;
            while (n) {
                if (n & 1) res = _mul(res, b);
                b = _mul(b, b), n >>= 1;
            }
            return raw(res);
        }
        CONSTEXPR14 mint inv() const {
            if constexpr (IsPrime)
                return inv_Fermat();
            else
                return inv_exgcd();
        }
        CONSTEXPR14 mint inv_exgcd() const {
            mod_type x = mod(), y = m_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 raw(m0);
        }
        constexpr mint inv_Fermat() const { return pow(mod() - 2); }
        CONSTEXPR14 mint &operator++() {
            if (++m_val == mod()) m_val = 0;
            return *this;
        }
        CONSTEXPR14 mint &operator--() {
            if (!m_val) m_val = mod();
            m_val--;
            return *this;
        }
        CONSTEXPR14 mint operator++(int) {
            mint old(*this);
            ++*this;
            return old;
        }
        CONSTEXPR14 mint operator--(int) {
            mint old(*this);
            --*this;
            return old;
        }
        CONSTEXPR14 mint &operator+=(const mint &rhs) {
            m_val += rhs.m_val;
            if (m_val >= mod()) m_val -= mod();
            return *this;
        }
        CONSTEXPR14 mint &operator-=(const mint &rhs) {
            m_val += mod() - rhs.m_val;
            if (m_val >= mod()) m_val -= mod();
            return *this;
        }
        CONSTEXPR14 mint &operator*=(const mint &rhs) {
            m_val = _mul(m_val, rhs.m_val);
            return *this;
        }
        CONSTEXPR14 mint &operator/=(const mint &rhs) { return *this *= rhs.inv(); }
        constexpr mint operator+() const { return *this; }
        constexpr mint operator-() const { return raw(m_val ? mod() - m_val : 0); }
        constexpr bool operator==(const mint &rhs) const { return m_val == rhs.m_val; }
        constexpr bool operator!=(const mint &rhs) const { return m_val != rhs.m_val; }
        constexpr bool operator<(const mint &rhs) const { return m_val < rhs.m_val; }
        constexpr bool operator>(const mint &rhs) const { return m_val > rhs.m_val; }
        constexpr bool operator<=(const mint &rhs) const { return m_val <= rhs.m_val; }
        constexpr bool operator>=(const mint &rhs) const { return m_val <= rhs.m_val; }
        template <typename Tp>
        constexpr explicit operator Tp() const { return Tp(m_val); }
        friend CONSTEXPR14 mint operator+(const mint &a, const mint &b) { return mint(a) += b; }
        friend CONSTEXPR14 mint operator-(const mint &a, const mint &b) { return mint(a) -= b; }
        friend CONSTEXPR14 mint operator*(const mint &a, const mint &b) { return mint(a) *= b; }
        friend CONSTEXPR14 mint operator/(const mint &a, const mint &b) { return mint(a) /= b; }
    };
    template <typename Istream, uint32_t P, bool IsPrime>
    Istream &operator>>(Istream &is, StaticModInt32<P, IsPrime> &x) { return is >> x.m_val; }
    template <typename Ostream, uint32_t P, bool IsPrime>
    Ostream &operator<<(Ostream &os, const StaticModInt32<P, IsPrime> &x) { return os << x.val(); }
    using mint998244353 = StaticModInt32<998244353, true>;
    using mint1000000007 = StaticModInt32<1000000007, true>;
}
#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_LINKBUCKET__
#define __OY_LINKBUCKET__
namespace OY {
    namespace LBC {
        using size_type = uint32_t;
        template <bool MaintainSize>
        struct Bucket {
            size_type m_first;
        };
        template <>
        struct Bucket<true> {
            size_type m_first, m_size;
        };
        template <typename Tp, bool MaintainSize = false>
        class Container {
        public:
            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 {
                Container<Tp, MaintainSize> *m_lbc;
                size_type m_buc_id;
                bucket(Container<Tp, MaintainSize> *lbc, size_type buc_id) : m_lbc(lbc), m_buc_id(buc_id) {}
                size_type size() const {
                    static_assert(MaintainSize, "MaintainSize Must Be True");
                    return m_lbc->m_buckets[m_buc_id].m_size;
                }
                bool empty() const { return !~m_lbc->m_buckets[m_buc_id].m_first; }
                Tp &front() { return m_lbc->m_item[m_lbc->m_buckets[m_buc_id].m_first].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_buckets[m_buc_id].m_first;
                    m_lbc->m_buckets[m_buc_id].m_first = m_lbc->m_cursor++;
                    if constexpr (MaintainSize) m_lbc->m_buckets[m_buc_id].m_size++;
                }
                void pop_front() {
                    m_lbc->m_buckets[m_buc_id].m_first = m_lbc->m_item[m_lbc->m_buckets[m_buc_id].m_first].m_next;
                    if constexpr (MaintainSize) m_lbc->m_buckets[m_buc_id].m_size--;
                }
                iterator begin() const { return iterator(m_lbc->m_item.data(), m_lbc->m_buckets[m_buc_id].m_first); }
                iterator end() const { return iterator(m_lbc->m_item.data(), -1); }
            };
        private:
            std::vector<Bucket<MaintainSize>> m_buckets;
            std::vector<node> m_item;
            size_type m_bucket_cnt, m_cursor;
        public:
            Container(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;
                Bucket<MaintainSize> id{};
                id.m_first = -1;
                m_buckets.assign(m_bucket_cnt, id), 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((Container<Tp, MaintainSize> *)this, buc_id); }
            void swap(size_type buc_id1, size_type buc_id2) { std::swap(m_buckets[buc_id1], m_buckets[buc_id2]); }
            void merge(size_type buc_id, size_type rhs) {
                size_type cur = m_buckets[rhs].m_first;
                if (!~cur) return;
                while (~m_item[cur].m_next) cur = m_item[cur].m_next;
                m_item[cur].m_next = m_buckets[buc_id].m_first, m_buckets[buc_id].m_first = m_buckets[rhs].m_first;
                if constexpr (MaintainSize) m_buckets[buc_id].m_size += m_buckets[rhs].m_size, m_buckets[rhs].m_size = 0;
                m_buckets[rhs].m_first = -1;
            }
            iterator bucket_begin(size_type buc_id) { return iterator(m_item, m_buckets[buc_id].m_first); }
            iterator bucket_end(size_type = 0) { return iterator(m_item, -1); }
        };
    }
};
#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::mint1000000007;
    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::Container<uint32_t, true> dsu(n, n);
    std::vector<uint32_t> belong(n);
    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;
    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;
                uint32_t head1 = belong[low], head2 = belong[sum - low];
                if (dsu[head1].size() < dsu[head2].size()) {
                    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);
                } 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);
                }
            }
        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;
                uint32_t head1 = belong[sum - n + 1 + low], head2 = belong[n - 1 - low];
                if (dsu[head1].size() < dsu[head2].size()) {
                    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);
                } 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);
                }
            }
    }
    cout << ans;
}
int main() {
    solve_hash();
}