/*
lib:        https://github.com/old-yan/CP-template
author:     oldyan
*/
#include <algorithm>
#include <bit>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <functional>
#include <numeric>
#include <string>
#include <sys/mman.h>
#include <sys/stat.h>
#include <type_traits>
#include <vector>
#ifndef __OY_LINUXIO__
#define __OY_LINUXIO__
#ifdef __unix__
#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{};
            struct stat m_stat;
            char *m_p, *m_c, *m_end;
            InputHelper(FILE *file = stdin) {
#ifdef __unix__
                auto fd = fileno(file);
                fstat(fd, &m_stat);
                m_c = m_p = (char *)mmap(nullptr, m_stat.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
                m_end = m_p + m_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_ADJDIFF__
#define __OY_ADJDIFF__
namespace OY {
    namespace AdjDiff {
        using size_type = uint32_t;
        struct Ignore {};
        template <typename Tp, bool AutoSwitch = true>
        struct Table {
            enum TableState {
                TABLE_ANY = 0,
                TABLE_DIFFERENCE = 1,
                TABLE_VALUE = 2,
                TABLE_PRESUM = 3
            };
            size_type m_size;
            mutable TableState m_state;
            mutable std::vector<Tp> m_sum;
            void _plus(size_type i, const Tp &inc) const { m_sum[i] += inc; }
            void _minus(size_type i, const Tp &inc) const { m_sum[i] -= inc; }
            Tp _get(size_type i) const { return ~i ? m_sum[i] : 0; }
            void _adjacent_difference() const {
                std::adjacent_difference(m_sum.begin(), m_sum.end(), m_sum.begin());
                m_state = TableState(m_state - 1);
            }
            void _partial_sum() const {
                std::partial_sum(m_sum.begin(), m_sum.end(), m_sum.begin());
                m_state = TableState(m_state + 1);
            }
            template <typename InitMapping = Ignore>
            Table(size_type length = 0, InitMapping mapping = InitMapping()) { resize(length, mapping); }
            template <typename Iterator>
            Table(Iterator first, Iterator last) { reset(first, last); }
            template <typename InitMapping = Ignore>
            void resize(size_type length, InitMapping mapping = InitMapping()) {
                if (!(m_size = length)) return;
                m_sum.assign(m_size, {});
                if constexpr (!std::is_same<InitMapping, Ignore>::value) {
                    for (size_type i = 0; i < m_size; i++) m_sum[i] = mapping(i);
                    m_state = TableState::TABLE_VALUE;
                } else
                    m_state = TableState::TABLE_ANY;
            }
            template <typename Iterator>
            void reset(Iterator first, Iterator last) {
                resize(last - first, [&](size_type i) { return *(first + i); });
            }
            void add(size_type i, const Tp &inc) {
                if constexpr (AutoSwitch) switch_to_value();
                _plus(i, inc);
            }
            void modify(size_type i, const Tp &val) {
                if constexpr (AutoSwitch) switch_to_value();
                _plus(i, val - _get(i));
            }
            void add(size_type left, size_type right, const Tp &inc) {
                if constexpr (AutoSwitch) switch_to_difference();
                _plus(left, inc);
                if (right + 1 != m_size) _minus(right + 1, inc);
            }
            Tp query(size_type i) const {
                if constexpr (AutoSwitch) switch_to_value();
                return _get(i);
            }
            Tp query(size_type left, size_type right) const {
                if constexpr (AutoSwitch) switch_to_presum();
                return _get(right) - _get(left - 1);
            }
            Tp query_all() const {
                if constexpr (AutoSwitch) switch_to_presum();
                return _get(m_size - 1);
            }
            void switch_to_difference() const {
                if (m_state == TableState::TABLE_ANY) return (void)(m_state = TableState::TABLE_DIFFERENCE);
                if (m_state == TableState::TABLE_PRESUM) _adjacent_difference();
                if (m_state == TableState::TABLE_VALUE) _adjacent_difference();
            }
            void switch_to_value() const {
                if (m_state == TableState::TABLE_ANY) return (void)(m_state = TableState::TABLE_VALUE);
                if (m_state == TableState::TABLE_DIFFERENCE) _partial_sum();
                if (m_state == TableState::TABLE_PRESUM) _adjacent_difference();
            }
            void switch_to_presum() const {
                if (m_state == TableState::TABLE_ANY) return (void)(m_state = TableState::TABLE_PRESUM);
                if (m_state == TableState::TABLE_DIFFERENCE) _partial_sum();
                if (m_state == TableState::TABLE_VALUE) _partial_sum();
            }
        };
        template <typename Ostream, typename Tp, bool AutoSwitch>
        Ostream &operator<<(Ostream &out, const Table<Tp, AutoSwitch> &x) {
            out << "[";
            for (size_type i = 0; i < x.m_size; i++) {
                if (i) out << ", ";
                out << x.query(i);
            }
            return out << "]";
        };
    }
}
#endif
#ifndef __OY_WAVELET__
#define __OY_WAVELET__
namespace OY {
    namespace WaveLet {
        using size_type = uint32_t;
        using mask_type = uint64_t;
        static constexpr size_type MASK_SIZE = sizeof(mask_type) << 3, MASK_WIDTH = MASK_SIZE / 32 + 4;
        struct BitRank {
            std::vector<mask_type> m_bits;
            std::vector<size_type> m_sum;
            void resize(size_type length) { m_bits.assign((length >> MASK_WIDTH) + 1, 0), m_sum.resize(m_bits.size()); }
            void set(size_type i, mask_type val) { m_bits[i >> MASK_WIDTH] |= val << (i & (MASK_SIZE - 1)); }
            void prepare() {
                for (size_type i = 1; i != m_bits.size(); i++) m_sum[i] = m_sum[i - 1] + std::popcount(m_bits[i - 1]);
            }
            size_type rank1(size_type i) const { return m_sum[i >> MASK_WIDTH] + std::popcount(m_bits[i >> MASK_WIDTH] & ((mask_type(1) << (i & (MASK_SIZE - 1))) - 1)); }
            size_type rank1(size_type l, size_type r) const { return rank1(r) - rank1(l); }
            size_type rank0(size_type i) const { return i - rank1(i); }
            size_type rank0(size_type l, size_type r) const { return rank0(r) - rank0(l); }
        };
        struct VoidTable {
            template <typename Iterator>
            void reset(Iterator first, Iterator last) {}
            size_type query(size_type left, size_type right) const { return right - left + 1; }
        };
        template <typename Tp, typename SumTable = VoidTable>
        struct Table {
            size_type m_size, m_alpha;
            std::vector<BitRank> m_ranks;
            std::vector<size_type> m_pos;
            std::vector<SumTable> m_summer;
            Table() = default;
            template <typename InitMapping>
            Table(size_type length, InitMapping mapping, size_type alpha = 0) { resize(length, mapping, alpha); }
            template <typename Iterator>
            Table(Iterator first, Iterator last, size_type alpha = 0) { reset(first, last, alpha); }
            template <typename InitMapping>
            void resize(size_type length, InitMapping mapping, size_type alpha = 0) {
                static_assert(std::is_unsigned<Tp>::value, "Tp Must Be Unsigned Type");
                if (!(m_size = length)) return;
                std::vector<Tp> numbers(m_size);
                for (size_type i = 0; i != m_size; i++) numbers[i] = mapping(i);
                m_alpha = alpha ? alpha : std::max<uint32_t>(1, std::bit_width(*std::max_element(numbers.begin(), numbers.end())));
                m_ranks.resize(m_alpha), m_pos.resize(m_alpha);
                m_summer.resize(m_alpha);
                for (size_type d = m_alpha - 1; ~d; d--) {
                    m_ranks[d].resize(m_size);
                    for (size_type i = 0; i != m_size; i++) m_ranks[d].set(i, numbers[i] >> d & 1);
                    m_ranks[d].prepare();
                    m_pos[d] = std::stable_partition(numbers.begin(), numbers.end(), [&](size_type val) { return !(val >> d & 1); }) - numbers.begin();
                    m_summer[d].reset(numbers.begin(), numbers.end());
                }
            }
            template <typename Iterator>
            void reset(Iterator first, Iterator last, size_type alpha = 0) {
                resize(
                    last - first, [&](size_type i) { return *(first + i); }, alpha);
            }
            size_type count(size_type left, size_type right, Tp val) const {
                right++;
                for (size_type d = m_alpha - 1; ~d; d--) {
                    size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right);
                    if (!(val >> d & 1))
                        left = zl, right = zr;
                    else
                        left += m_pos[d] - zl, right += m_pos[d] - zr;
                }
                return right - left;
            }
            size_type count(size_type left, size_type right, Tp minimum, Tp maximum) const {
                size_type l1 = left, r1 = right + 1, l2 = left, r2 = right + 1, res = 0;
                for (size_type d = m_alpha - 1; ~d; d--) {
                    size_type zl1 = m_ranks[d].rank0(l1), zr1 = m_ranks[d].rank0(r1), zl2 = m_ranks[d].rank0(l2), zr2 = m_ranks[d].rank0(r2);
                    if (!(minimum >> d & 1))
                        l1 = zl1, r1 = zr1;
                    else
                        res -= zr1 - zl1, l1 += m_pos[d] - zl1, r1 += m_pos[d] - zr1;
                    if (!(maximum >> d & 1))
                        l2 = zl2, r2 = zr2;
                    else
                        res += zr2 - zl2, l2 += m_pos[d] - zl2, r2 += m_pos[d] - zr2;
                }
                return r2 - l2 + res;
            }
            size_type rank(size_type left, size_type right, Tp val) const {
                size_type ans = 0;
                right++;
                for (size_type d = m_alpha - 1; ~d; d--) {
                    size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right);
                    if (!(val >> d & 1))
                        left = zl, right = zr;
                    else
                        left += m_pos[d] - zl, right += m_pos[d] - zr, ans += zr - zl;
                }
                return ans;
            }
            Tp minimum(size_type left, size_type right) const {
                Tp ans = 0;
                right++;
                for (size_type d = m_alpha - 1; ~d; d--) {
                    size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right);
                    if (zl != zr)
                        left = zl, right = zr;
                    else
                        left += m_pos[d] - zl, right += m_pos[d] - zr, ans |= Tp(1) << d;
                }
                return ans;
            }
            Tp maximum(size_type left, size_type right) const {
                Tp ans = 0;
                right++;
                for (size_type d = m_alpha - 1; ~d; d--) {
                    size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right);
                    if (zr - zl == right - left)
                        left = zl, right = zr;
                    else
                        left += m_pos[d] - zl, right += m_pos[d] - zr, ans |= Tp(1) << d;
                }
                return ans;
            }
            Tp quantile(size_type left, size_type right, size_type k) const {
                Tp ans = 0;
                right++;
                for (size_type d = m_alpha - 1; ~d; d--) {
                    size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right), z = zr - zl;
                    if (k < z)
                        left = zl, right = zr;
                    else
                        left += m_pos[d] - zl, right += m_pos[d] - zr, k -= z, ans |= Tp(1) << d;
                }
                return ans;
            }
            Tp max_bitxor(size_type left, size_type right, Tp val) const {
                Tp ans = 0;
                right++;
                for (size_type d = m_alpha - 1; ~d; d--) {
                    size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right), z = zr - zl;
                    if (val >> d & 1)
                        if (z)
                            left = zl, right = zr, ans |= Tp(1) << d;
                        else
                            left += m_pos[d] - zl, right += m_pos[d] - zr;
                    else if (right - left - z)
                        left += m_pos[d] - zl, right += m_pos[d] - zr, ans |= Tp(1) << d;
                    else
                        left = zl, right = zr;
                }
                return ans;
            }
            template <typename Callback>
            void do_for_ksmallest(size_type left, size_type right, size_type k, Callback &&call) const {
                right++;
                for (size_type d = m_alpha - 1; ~d; d--) {
                    size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right), z = zr - zl;
                    if (k < z)
                        left = zl, right = zr;
                    else {
                        left += m_pos[d] - zl, right += m_pos[d] - zr, k -= z;
                        if (z) call(m_summer[d].query(zl, zr - 1));
                    }
                }
                if (k) call(m_summer[0].query(left, left + k - 1));
            }
            template <typename Callback>
            void do_for_klargest(size_type left, size_type right, size_type k, Callback &&call) const {
                right++;
                for (size_type d = m_alpha - 1; ~d; d--) {
                    size_type one_l = m_ranks[d].rank1(left), one_r = m_ranks[d].rank1(right), one = one_r - one_l;
                    if (k < one)
                        left = m_pos[d] + one_l, right = m_pos[d] + one_r;
                    else {
                        left -= one_l, right -= one_r, k -= one;
                        if (one) call(m_summer[d].query(m_pos[d] + one_l, m_pos[d] + one_r - 1));
                    }
                }
                if (k) call(m_summer[0].query(right - k, right - 1));
            }
        };
        template <typename Tp>
        struct Tree {
            Table<size_type, VoidTable> m_table;
            std::vector<Tp> m_discretizer;
            size_type m_size;
            size_type _find(const Tp &val) const { return std::lower_bound(m_discretizer.begin(), m_discretizer.end(), val) - m_discretizer.begin(); }
            Tree() = default;
            template <typename InitMapping>
            Tree(size_type length, InitMapping mapping) { resize(length, mapping); }
            template <typename Iterator>
            Tree(Iterator first, Iterator last) { reset(first, last); }
            template <typename InitMapping>
            void resize(size_type length, InitMapping mapping) {
                if (!(m_size = length)) return;
                std::vector<Tp> items(m_size);
                for (size_type i = 0; i != m_size; i++) items[i] = mapping(i);
                m_discretizer = items;
                std::sort(m_discretizer.begin(), m_discretizer.end());
                m_discretizer.erase(std::unique(m_discretizer.begin(), m_discretizer.end()), m_discretizer.end());
                m_table.resize(
                    m_size, [&](size_type i) { return _find(items[i]); }, std::bit_width(m_discretizer.size()));
            }
            template <typename Iterator>
            void reset(Iterator first, Iterator last) {
                resize(last - first, [&](size_type i) { return *(first + i); });
            }
            size_type count(size_type left, size_type right, const Tp &val) const {
                size_type find = _find(val);
                return find < m_discretizer.size() && m_discretizer[find] == val ? m_table.count(left, right, find) : 0;
            }
            size_type count(size_type left, size_type right, const Tp &minimum, const Tp &maximum) const {
                size_type find1 = _find(minimum);
                if (find1 == m_discretizer.size()) return 0;
                size_type find2 = _find(maximum);
                return find2 < m_discretizer.size() && m_discretizer[find2] == maximum ? m_table.count(left, right, find1, find2) : m_table.count(left, right, find1, find2 - 1);
            }
            size_type rank(size_type left, size_type right, const Tp &val) const { return m_table.rank(left, right, _find(val)); }
            Tp minimum(size_type left, size_type right) const { return m_discretizer[m_table.minimum(left, right)]; }
            Tp maximum(size_type left, size_type right) const { return m_discretizer[m_table.maximum(left, right)]; }
            Tp quantile(size_type left, size_type right, size_type k) const { return m_discretizer[m_table.quantile(left, right, k)]; }
        };
    }
}
#endif
/*
lib code is above
temp code is below
*/
static constexpr uint32_t N = 200000;
struct node {
    uint32_t a, b;
} arr[N];
uint64_t res[N];
void solve_wavelet() {
    uint32_t n;
    cin >> n;
    for (uint32_t i = 0; i < n; i++) cin >> arr[i].a >> arr[i].b;
    std::sort(arr, arr + n, [](auto &x, auto &y) { return x.b < y.b; });
    using AdjTable = OY::AdjDiff::Table<uint64_t, true>;
    OY::WaveLet::Table<uint32_t, AdjTable> S(n, [](uint32_t i) {
        return arr[i].a;
    });
    auto getsum = [&](uint32_t last, uint32_t k) -> uint64_t {
        if (k == 1) return arr[last].a + arr[last].b;
        uint64_t sum{};
        S.do_for_ksmallest(0, last - 1, k - 1, [&](auto val) {
            sum += val;
        });
        return sum + arr[last].a + arr[last].b;
    };
    auto dfs = [&](auto self, uint32_t l, uint32_t lpos, uint32_t r, uint32_t rpos) -> void {
        if (l + 1 >= r) return;
        uint32_t mid = (l + r) >> 1, pos;
        res[mid] = UINT64_MAX / 2;
        for (uint32_t i = std::max(lpos, mid - 1); i <= rpos; i++) {
            auto sum = getsum(i, mid);
            if (sum < res[mid]) res[mid] = sum, pos = i;
        }
        self(self, l, lpos, mid, pos);
        self(self, mid, pos, r, rpos);
    };
    res[1] = getsum(0, 1);
    res[n] = getsum(n - 1, n);
    dfs(dfs, 1, 0, n, n - 1);
    for (uint32_t k = 1; k <= n; k++) cout << res[k] << '\n';
}
int main() {
    solve_wavelet();
}