結果

問題 No.5020 Averaging
ユーザー さはら
提出日時 2024-02-25 17:24:51
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 914 ms / 1,000 ms
コード長 55,648 bytes
コンパイル時間 4,991 ms
コンパイル使用メモリ 260,008 KB
実行使用メモリ 26,676 KB
スコア 29,359,140
最終ジャッジ日時 2024-02-25 17:25:45
合計ジャッジ時間 53,178 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#ifdef ONLINE_JUDGE
#define NDEBUG
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#else
#undef NDEBUG
#endif
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <concepts>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <mutex>
#include <numeric>
#include <optional>
#include <queue>
#include <ranges>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <thread>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
namespace shr {
    namespace basic {
        using namespace std;
        using uchar = unsigned char;
        using uint = unsigned int;
        using ushort = unsigned short;
        using ull = unsigned long long;
        using ll = long long;
        using pii = pair<int, int>;
        using pdi = pair<double, int>;
        template <class T>
        concept printable = requires(T t, ostream& out) { out << t; };
        int len(const string& a) {
            return (int) a.length();
        }
        template <class T>
        int len(const vector<T>& a) {
            return (int) a.size();
        }
        template <class T>
        int len(const set<T>& a) {
            return (int) a.size();
        }
        template <class T>
        int len(const deque<T>& a) {
            return (int) a.size();
        }
        template <class T>
        int len(const priority_queue<T>& a) {
            return (int) a.size();
        }
        template <class T, int N>
        int len(const T (&a)[N]) {
            return N;
        }
        template <class T, int N>
        void clear_with(T (&a)[N], int val) {
            memset(a, val, sizeof(a));
        }
        template <totally_ordered T>
        bool update_min(T candidate, T& current_min) {
            if (candidate < current_min) {
                current_min = candidate;
                return true;
            }
            return false;
        }
        template <totally_ordered T>
        bool update_min_eq(T candidate, T& current_min) {
            if (candidate <= current_min) {
                current_min = candidate;
                return true;
            }
            return false;
        }
        template <totally_ordered T>
        bool update_max(T candidate, T& current_max) {
            if (candidate > current_max) {
                current_max = candidate;
                return true;
            }
            return false;
        }
        template <totally_ordered T>
        bool update_max_eq(T candidate, T& current_max) {
            if (candidate >= current_max) {
                current_max = candidate;
                return true;
            }
            return false;
        }
        template <class T>
        string tos(T a) {
            return to_string(a);
        }
        template <printable T>
        string tos(T a) {
            ostringstream os;
            os << a;
            return os.str();
        }
        constexpr double linearstep(double edge0, double edge1, double t) {
            return clamp((t - edge0) / (edge1 - edge0), 0.0, 1.0);
        }
        constexpr double smoothstep(double edge0, double edge1, double t) {
            t = linearstep(edge0, edge1, t);
            return t * t * (3 - 2 * t);
        }
        double exp_interp(double from, double to, double t) {
            return pow(from, 1 - t) * pow(to, t);
        }
    } // namespace basic
    using namespace basic;
    namespace timer {
        double time_scale = 1.0;
        // return in ms
        int timer(bool reset = false) {
            static auto st = chrono::system_clock::now();
            if (reset) {
                st = chrono::system_clock::now();
                return 0;
            } else {
                auto en = chrono::system_clock::now();
                int elapsed = (int) chrono::duration_cast<chrono::milliseconds>(en - st).count();
                return (int) round(elapsed / time_scale);
            }
        }
    } // namespace timer
    namespace tracer {
        bool debug = true;
        template <class T>
        concept is_pair = requires(T t) {
            t.first;
            t.second;
        };
        template <class T>
        concept has_str = requires(T t) {
            { t.str() } -> convertible_to<string>;
        };
        template <printable T>
        void tracen(T&& t) {
            if (!debug)
                return;
            cerr << t;
        }
        template <class T>
        requires(has_str<T> && !printable<T>)
        void tracen(T&& t) {
            if (!debug)
                return;
            cerr << t.str();
        }
        template <class T, class U>
        void tracen(pair<T, U>& t) { // <- ?????????????????????? need this for trace(<iterable of pairs>)
            if (!debug)
                return;
            cerr << "(";
            tracen(t.first);
            cerr << ", ";
            tracen(t.second);
            cerr << ")";
        }
        template <class T, class U>
        void tracen(pair<T, U>&& t) { // <- ?????????????????????? need this for trace(make_pair(1, 2))
            if (!debug)
                return;
            cerr << "(";
            tracen(t.first);
            cerr << ", ";
            tracen(t.second);
            cerr << ")";
        }
        template <class T>
        requires(!printable<T>)
        void tracen(T&& t) {
            if (!debug)
                return;
            bool first = true;
            auto from = t.begin();
            auto until = t.end();
            cerr << "{";
            while (from != until) {
                if (first) {
                    first = false;
                } else {
                    cerr << ", ";
                }
                tracen(*from);
                from++;
            }
            cerr << "}";
        }
        template <class T, int N>
        requires(!same_as<decay_t<T>, char>)
        void tracen(T (&a)[N]) {
            if (!debug)
                return;
            cerr << "{";
            for (int i = 0; i < N; i++) {
                if (i > 0)
                    cerr << ", ";
                tracen(a[i]);
            }
            cerr << "}";
        }
        template <class T1, class T2, class... Rest>
        void tracen(T1&& t1, T2&& t2, Rest&&... rest) {
            if (!debug)
                return;
            tracen(forward<T1>(t1));
            tracen(forward<T2>(t2), forward<Rest>(rest)...);
        }
        void trace() {
            if (!debug)
                return;
            cerr << endl;
        }
        template <class T, class... Rest>
        void trace(T&& t, Rest&&... rest) {
            if (!debug)
                return;
            tracen(forward<T>(t), forward<Rest>(rest)...);
            cerr << endl;
        }
        template <class T>
        requires(!printable<T>)
        void trace2d(T&& t, int h, int w) {
            if (!debug)
                return;
            bool first = true;
            auto from = t.begin();
            auto until = t.end();
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (j > 0)
                        tracen(" ");
                    tracen(*from);
                    from++;
                    if (j == w - 1)
                        trace();
                }
            }
        }
        template <class T, int N>
        requires(!same_as<decay_t<T>, char>)
        void trace2d(T (&a)[N], int h, int w) {
            if (!debug)
                return;
            int idx = 0;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (j > 0)
                        tracen(" ");
                    tracen(a[idx]);
                    idx++;
                    if (j == w - 1)
                        trace();
                }
            }
        }
    } // namespace tracer
    using namespace tracer;
    namespace random {
        class rngen {
        public:
            rngen() {
            }
            rngen(int s) {
                seed(s);
            }
            ull get_state() {
                return state;
            }
            void set_state(ull state) {
                this->state = state;
            }
            void seed(int s) {
                state = s + INCR;
                next32();
            }
            int next_int() {
                return next31();
            }
            int next_int(int mod) {
                assert(mod > 0);
                return (int) ((ull) next31() * mod >> 31);
            }
            int next_int(int min, int max) {
                return min + next_int(max - min + 1);
            }
            uint next_uint() {
                return next32();
            }
            ull next_ull() {
                return (ull) next32() << 32 | next32();
            }
            double next_float() {
                return (double) next31() / 0x80000000;
            }
            double next_float(double min, double max) {
                return min + next_float() * (max - min);
            }
            double next_normal() {
                return sqrt(-2 * log(next_float())) * cos(6.283185307179586 * next_float());
            }
            double next_normal(double mean, double sigma) {
                return mean + next_normal() * sigma;
            }
        private:
            static constexpr ull MULT = 0x8b46ad15ae59daadull;
            static constexpr ull INCR = 0xf51827be20401689ull;
            ull state = (ull) chrono::duration_cast<chrono::nanoseconds>(
                chrono::system_clock::now().time_since_epoch())
                            .count();
            uint next32() {
                uint r = (uint) (state >> 59);
                state = state * MULT + INCR;
                state ^= state >> 18;
                uint t = (uint) (state >> 27);
                return t >> r | t << (-r & 31);
            }
            int next31() {
                return (int) (next32() & 0x7fffffff);
            }
        };
        void random_permutation(int* a, int n, rngen& rng) {
            assert(n >= 0);
            if (n == 0)
                return;
            a[0] = 0;
            for (int i = 1; i < n; i++) {
                a[i] = i;
                swap(a[i], a[rng.next_int(i + 1)]);
            }
        }
        template <class RandomAccessContainer>
        auto& random_pick(RandomAccessContainer& c, rngen& rng) {
            return c[rng.next_int(len(c))];
        }
        template <class RandomAccessContainer>
        const auto& random_pick(const RandomAccessContainer& c, rngen& rng) {
            return c[rng.next_int(len(c))];
        }
        template <class T, int N>
        T& random_pick(T (&c)[N], rngen& rng) {
            return c[rng.next_int(N)];
        }
        template <class T, int N>
        const T& random_pick(const T (&c)[N], rngen& rng) {
            return c[rng.next_int(N)];
        }
    } // namespace random
    using namespace random;
    namespace ds {
        // random access: O(1)
        // push: O(1)
        // insert: n/a
        // erase by position: O(1)
        // erase by element: n/a
        // max size: fixed
        template <class T, int N>
        class fast_vector {
        private:
            T data[N];
            int num = 0;
        public:
            using iterator = T*;
            using const_iterator = const T*;
            iterator begin() {
                return data;
            }
            iterator end() {
                return data + num;
            }
            const_iterator begin() const {
                return data;
            }
            const_iterator end() const {
                return data + num;
            }
            void push_back(T a) {
                assert(num < N);
                data[num++] = a;
            }
            template <class... Args>
            void emplace_back(Args&&... args) {
                push_back(T(forward<Args>(args)...));
            }
            void erase(iterator where) {
                assert(where >= begin() && where < end());
                *where = data[--num];
            }
            void pop_back() {
                assert(num > 0);
                num--;
            }
            T& operator[](int i) {
                assert(i >= 0 && i < num);
                return data[i];
            }
            const T& operator[](int i) const {
                assert(i >= 0 && i < num);
                return data[i];
            }
            int size() const {
                return num;
            }
        };
        // random access: O(1)
        // push: O(1)
        // insert: n/a
        // erase: n/a
        // reallocation: never
        template <class T, int UnitBits = 20>
        class increasing_vector {
        private:
            static constexpr int UNIT_SIZE = 1 << UnitBits;
            static constexpr int UNIT_MASK = UNIT_SIZE - 1;
            T** packs;
            int num_packs = 0;
            int num_total = 0;
        public:
            increasing_vector(const increasing_vector& vec) = delete;
            increasing_vector& operator=(const increasing_vector& vec) = delete;
            increasing_vector() : packs(new T*[65536]) {
            }
            ~increasing_vector() {
                for (int i = 0; i < num_packs; i++) {
                    delete[] packs[i];
                }
                delete[] packs;
            }
            T* next_pointer() {
                if ((num_total++ & UNIT_MASK) == 0) {
                    packs[num_packs++] = new T[UNIT_SIZE];
                }
                return &(*this)[num_total - 1];
            }
            void push_back(T a) {
                *next_pointer() = a;
            }
            template <class... Args>
            void emplace_back(Args&&... args) {
                push_back(T(forward<Args>(args)...));
            }
            T& operator[](int i) {
                assert(i >= 0 && i < num_total);
                return packs[i >> UnitBits][i & UNIT_MASK];
            }
            const T& operator[](int i) const {
                assert(i >= 0 && i < num_total);
                return packs[i >> UnitBits][i & UNIT_MASK];
            }
            int size() const {
                return num_total;
            }
        };
        // random access: O(1)
        // insert: O(1)
        // erase: O(1)
        // check: O(1)
        // max value: fixed
        template <int N>
        class fast_iset {
        private:
            int data[N];
            int indices[N];
            int num = 0;
        public:
            using iterator = int*;
            using const_iterator = const int*;
            fast_iset() {
                memset(indices, -1, sizeof(indices));
            }
            iterator begin() {
                return data;
            }
            iterator end() {
                return data + num;
            }
            const_iterator begin() const {
                return data;
            }
            const_iterator end() const {
                return data + num;
            }
            bool insert(int a) {
                assert(a >= 0 && a < N);
                if (indices[a] != -1)
                    return false;
                data[num] = a;
                indices[a] = num;
                num++;
                return true;
            }
            bool erase(int a) {
                assert(a >= 0 && a < N);
                int index = indices[a];
                if (index == -1)
                    return false;
                assert(num > 0);
                indices[data[index] = data[--num]] = index;
                indices[a] = -1;
                return true;
            }
            void clear() {
                memset(indices, -1, sizeof(indices));
                num = 0;
            }
            bool contains(int a) const {
                return indices[a] != -1;
            }
            const int& operator[](int i) const {
                assert(i >= 0 && i < num);
                return data[i];
            }
            int size() const {
                return num;
            }
            bool empty() const {
                return num == 0;
            }
        };
        // insert: O(1)
        // get/set: O(1)
        // clear: O(1)
        // erase: n/a
        template <class T, int BucketBits = 20>
        class hash_imap {
        private:
            static constexpr int BUCKET_SIZE = 1 << BucketBits;
            static constexpr int BUCKET_MASK = BUCKET_SIZE - 1;
            ull* keys;
            T* values;
            ushort* access_time;
            ushort time = (ushort) -1;
            int num_elements = 0;
            int last_index = -1;
            ull last_key = -1;
            bool last_found = false;
        public:
            hash_imap()
                : keys(new ull[BUCKET_SIZE]), values(new T[BUCKET_SIZE]),
                  access_time(new ushort[BUCKET_SIZE]) {
            }
            ~hash_imap() {
                delete[] keys;
                delete[] values;
                delete[] access_time;
            }
            hash_imap(const hash_imap& map)
                : keys(new ull[BUCKET_SIZE]), values(new T[BUCKET_SIZE]),
                  access_time(new ushort[BUCKET_SIZE]) {
                memcpy(keys, map.keys, sizeof(ull[BUCKET_SIZE]));
                memcpy(values, map.values, sizeof(T[BUCKET_SIZE])); // can be potentially dangerous?
                memcpy(access_time, map.access_time, sizeof(ushort[BUCKET_SIZE]));
                time = map.time;
                num_elements = map.num_elements;
                last_index = map.last_index;
                last_key = map.last_key;
                last_found = map.last_found;
            }
            hash_imap& operator=(const hash_imap& map) {
                if (this == &map)
                    return *this;
                delete[] keys;
                delete[] values;
                delete[] access_time;
                keys = new ull[BUCKET_SIZE];
                values = new T[BUCKET_SIZE];
                access_time = new ushort[BUCKET_SIZE];
                memcpy(keys, map.keys, sizeof(ull[BUCKET_SIZE]));
                memcpy(values, map.values, sizeof(T[BUCKET_SIZE])); // can be potentially dangerous?
                memcpy(access_time, map.access_time, sizeof(ushort[BUCKET_SIZE]));
                time = map.time;
                num_elements = map.num_elements;
                last_index = map.last_index;
                last_key = map.last_key;
                last_found = map.last_found;
                return *this;
            }
            void clear() {
                num_elements = 0;
                last_found = false;
                last_index = -1;
                if (++time == 0) {
                    memset(access_time, 0, sizeof(ushort[BUCKET_SIZE]));
                    time = 1;
                }
            }
            bool access(ull key) {
                last_key = key;
                last_index = (int) (key & BUCKET_MASK);
                bool debug = false;
                while (true) {
                    if (access_time[last_index] != time) {
                        return last_found = false;
                    } else if (keys[last_index] == key) {
                        return last_found = true;
                    }
                    last_index = (last_index + 1) & BUCKET_MASK;
                }
            }
            T get() const {
                assert(last_found);
                return values[last_index];
            }
            void set(T value) {
                assert(last_index != -1);
                access_time[last_index] = time;
                keys[last_index] = last_key;
                values[last_index] = value;
                num_elements += !last_found;
                assert(("bucket size is too small", num_elements < 0.85 * BUCKET_SIZE));
            }
        };
        // a bitset, but cooler than std::bitset
        template <int Size>
        class rich_bitset {
        private:
            using word = ull;
            static_assert(has_single_bit(sizeof(word)));
            static constexpr int WORD_SHIFT = std::countr_zero(8 * sizeof(word));
            static constexpr int WORD_SIZE = 1 << WORD_SHIFT;
            static constexpr int WORD_MASK = WORD_SIZE - 1;
            static constexpr int NUM_WORDS = (Size + WORD_SIZE - 1) / WORD_SIZE;
            static constexpr int LAST_WORD = NUM_WORDS - 1;
            static constexpr word LAST_WORD_MASK =
                (Size & WORD_MASK) == 0 ? word(-1) : (word(1) << (Size & WORD_MASK)) - 1;
#define REP_WORDS(i) for (int i = 0; i < NUM_WORDS; i++)
#define REP_INNER_WORDS(i) for (int i = 0; i < NUM_WORDS - 1; i++)
#define REP_WORDS_REV(i) for (int i = NUM_WORDS - 1; i >= 0; i--)
#define REP_INNER_WORDS_REV(i) for (int i = NUM_WORDS - 2; i >= 0; i--)
            // [LAST_WORD] [LAST_WORD - 1] [...] [1] [0]
            // <- higher bits              lower bits ->
            word data[NUM_WORDS];
            struct ref {
                rich_bitset<Size>& bs;
                const int pos;
                ref(rich_bitset<Size>& bs, int pos) : bs(bs), pos(pos) {
                }
                ref& operator=(bool val) {
                    bs.set(pos, val);
                    return *this;
                }
                operator bool() const {
                    return bs.test(pos);
                }
            };
            void trim() {
                if constexpr ((Size & WORD_MASK) != 0) {
                    data[LAST_WORD] &= LAST_WORD_MASK;
                }
            }
        public:
            rich_bitset(ull value = 0) {
                constexpr int BITS = sizeof(ull) * 8;
                for (int i = 0; i < (BITS + WORD_SIZE - 1) / WORD_SIZE; i++) {
                    data[i] = value >> i * WORD_SIZE;
                }
                constexpr int OFFSET = (BITS + WORD_SIZE - 1) / WORD_SIZE;
                if constexpr (OFFSET < NUM_WORDS) {
                    memset(data + OFFSET, 0, sizeof(word) * (NUM_WORDS - OFFSET));
                }
            }
            bool all() const {
                bool res = true;
                REP_INNER_WORDS(i) {
                    res &= data[i] == word(-1);
                }
                res &= data[LAST_WORD] == LAST_WORD_MASK;
                return res;
            }
            bool none() const {
                bool res = true;
                REP_WORDS(i) {
                    res &= data[i] == 0;
                }
                return res;
            }
            bool any() const {
                bool res = false;
                REP_WORDS(i) {
                    res |= data[i] != 0;
                }
                return res;
            }
            int count() const {
                int res = 0;
                REP_WORDS(i) {
                    res += popcount(data[i]);
                }
                return res;
            }
            int countr_zero() const {
                if constexpr (LAST_WORD == 0) {
                    return std::countr_zero(word(data[LAST_WORD] | ~LAST_WORD_MASK));
                } else {
                    int res = std::countr_zero(data[0]);
                    int mask = -(res == WORD_SIZE); // continue adding if -1
                    for (int i = 1; i < NUM_WORDS - 1; i++) {
                        int count = std::countr_zero(data[i]);
                        res += count & mask;
                        mask &= -(count == WORD_SIZE);
                    }
                    int count = std::countr_zero(word(data[LAST_WORD] | ~LAST_WORD_MASK));
                    res += count & mask;
                    return res;
                }
            }
            int countl_zero() const {
                constexpr int LAST_WORD_SIZE = popcount(LAST_WORD_MASK);
                int res = std::countl_zero(word(~(~data[LAST_WORD] << (WORD_SIZE - LAST_WORD_SIZE))));
                int mask = -(res == LAST_WORD_SIZE); // continue adding if -1
                for (int i = NUM_WORDS - 2; i >= 0; i--) {
                    int count = std::countl_zero(data[i]);
                    res += count & mask;
                    mask &= -(count == WORD_SIZE);
                }
                return res;
            }
            int countr_one() const {
                if constexpr (LAST_WORD == 0) {
                    return std::countr_one(data[LAST_WORD]);
                } else {
                    int res = std::countr_one(data[0]);
                    int mask = -(res == WORD_SIZE); // continue adding if -1
                    for (int i = 1; i < NUM_WORDS - 1; i++) {
                        int count = std::countr_one(data[i]);
                        res += count & mask;
                        mask &= -(count == WORD_SIZE);
                    }
                    int count = std::countr_one(data[LAST_WORD]);
                    res += count & mask;
                    return res;
                }
            }
            int countl_one() const {
                constexpr int LAST_WORD_SIZE = popcount(LAST_WORD_MASK);
                int res = std::countl_one(word(data[LAST_WORD] << (WORD_SIZE - LAST_WORD_SIZE)));
                int mask = -(res == LAST_WORD_SIZE); // continue adding if -1
                for (int i = NUM_WORDS - 2; i >= 0; i--) {
                    int count = std::countl_one(data[i]);
                    res += count & mask;
                    mask &= -(count == WORD_SIZE);
                }
                return res;
            }
            int size() const {
                return Size;
            }
            bool test(int pos) const {
                assert(pos >= 0 && pos < Size);
                return (data[pos >> WORD_SHIFT] >> (pos & WORD_MASK)) & 1;
            }
            uint to_uint() const {
                constexpr int BITS = sizeof(uint) * 8;
                for (int i = (BITS + WORD_SIZE - 1) / WORD_SIZE; i < NUM_WORDS; i++) {
                    assert(("uint overflow", data[i] == 0));
                }
                if constexpr (WORD_SIZE > BITS) {
                    assert(("uint overflow", (data[0] >> BITS) == 0));
                }
                uint res = (uint) data[0];
                for (int i = 1; i < (BITS + WORD_SIZE - 1) / WORD_SIZE && i < NUM_WORDS; i++) {
                    res |= (uint) data[i] << i * WORD_SIZE;
                }
                return res;
            }
            ull to_ull() const {
                constexpr int BITS = sizeof(ull) * 8;
                for (int i = (BITS + WORD_SIZE - 1) / WORD_SIZE; i < NUM_WORDS; i++) {
                    assert(("ull overflow", data[i] == 0));
                }
                if constexpr (WORD_SIZE > BITS) {
                    assert(("ull overflow", (data[0] >> BITS) == 0));
                }
                ull res = (ull) data[0];
                for (int i = 1; i < (BITS + WORD_SIZE - 1) / WORD_SIZE && i < NUM_WORDS; i++) {
                    res |= (ull) data[i] << i * WORD_SIZE;
                }
                return res;
            }
            rich_bitset& set(int pos, bool val = true) {
                assert(pos >= 0 && pos < Size);
                word bit = word(1) << (pos & WORD_MASK);
                if (val) {
                    data[pos >> WORD_SHIFT] |= bit;
                } else {
                    data[pos >> WORD_SHIFT] &= ~bit;
                }
                return *this;
            }
            rich_bitset& reset(int pos) {
                assert(pos >= 0 && pos < Size);
                return set(pos, false);
            }
            rich_bitset& flip(int pos) {
                assert(pos >= 0 && pos < Size);
                word bit = word(1) << (pos & WORD_MASK);
                data[pos >> WORD_SHIFT] ^= bit;
                return *this;
            }
            rich_bitset& set() {
                clear_with(data, -1);
                trim();
                return *this;
            }
            rich_bitset& reset() {
                clear_with(data, 0);
                return *this;
            }
            rich_bitset& flip() {
                REP_INNER_WORDS(i) {
                    data[i] ^= word(-1);
                }
                data[LAST_WORD] ^= LAST_WORD_MASK;
                return *this;
            }
            rich_bitset& operator&=(const rich_bitset& a) {
                REP_WORDS(i) {
                    data[i] &= a.data[i];
                }
                return *this;
            }
            rich_bitset& operator|=(const rich_bitset& a) {
                REP_WORDS(i) {
                    data[i] |= a.data[i];
                }
                return *this;
            }
            rich_bitset& operator^=(const rich_bitset& a) {
                REP_WORDS(i) {
                    data[i] ^= a.data[i];
                }
                return *this;
            }
            rich_bitset& operator<<=(int amount) {
                assert(amount >= 0 && amount < Size);
                int nw = amount >> WORD_SHIFT;
                if (nw > 0) {
                    REP_WORDS_REV(i) {
                        data[i] = i - nw < 0 ? 0 : data[i - nw];
                    }
                }
                int nb = amount & WORD_MASK;
                if (nb) {
                    for (int i = NUM_WORDS - 1; i > 0; i--) {
                        data[i] = data[i] << nb | data[i - 1] >> (WORD_SIZE - nb);
                    }
                    data[0] <<= nb;
                }
                trim();
                return *this;
            }
            rich_bitset& operator>>=(int amount) {
                assert(amount >= 0 && amount < Size);
                int nw = amount >> WORD_SHIFT;
                if (nw > 0) {
                    REP_WORDS(i) {
                        data[i] = i + nw >= NUM_WORDS ? 0 : data[i + nw];
                    }
                }
                int nb = amount & WORD_MASK;
                if (nb) {
                    REP_INNER_WORDS(i) {
                        data[i] = data[i] >> nb | data[i + 1] << (WORD_SIZE - nb);
                    }
                    data[LAST_WORD] >>= nb;
                }
                return *this;
            }
            rich_bitset& operator+=(const rich_bitset& a) {
                word carry = 0;
                REP_WORDS(i) {
                    word l = data[i];
                    word r = a.data[i];
                    word sum = l + r;
                    data[i] = sum + carry;
                    carry = (sum < l) | (data[i] < sum);
                }
                trim();
                return *this;
            }
            rich_bitset& operator-=(const rich_bitset& a) {
                word carry = 1;
                REP_WORDS(i) {
                    word l = data[i];
                    word r = ~a.data[i];
                    word sum = l + r;
                    data[i] = sum + carry;
                    carry = (sum < l) | (data[i] < sum);
                }
                trim();
                return *this;
            }
            rich_bitset& operator++() {
                word carry = 1;
                REP_WORDS(i) {
                    word l = data[i];
                    data[i] = l + carry;
                    carry = (data[i] < l);
                }
                trim();
                return *this;
            }
            rich_bitset operator++(int) {
                rich_bitset res = *this;
                operator++();
                return res;
            }
            rich_bitset& operator--() {
                word carry = 0;
                REP_WORDS(i) {
                    word l = data[i];
                    data[i] = l - 1 + carry;
                    carry = (l | carry) != 0;
                }
                trim();
                return *this;
            }
            rich_bitset operator--(int) {
                rich_bitset res = *this;
                operator--();
                return res;
            }
            rich_bitset operator~() const {
                rich_bitset res = *this;
                res.flip();
                return res;
            }
            friend rich_bitset operator&(const rich_bitset& a, const rich_bitset& b) {
                rich_bitset res = a;
                res &= b;
                return res;
            }
            friend rich_bitset operator|(const rich_bitset& a, const rich_bitset& b) {
                rich_bitset res = a;
                res |= b;
                return res;
            }
            friend rich_bitset operator^(const rich_bitset& a, const rich_bitset& b) {
                rich_bitset res = a;
                res ^= b;
                return res;
            }
            friend rich_bitset operator<<(const rich_bitset& a, int amount) {
                rich_bitset res = a;
                res <<= amount;
                return res;
            }
            friend rich_bitset operator>>(const rich_bitset& a, int amount) {
                rich_bitset res = a;
                res >>= amount;
                return res;
            }
            friend rich_bitset operator+(const rich_bitset& a, const rich_bitset& b) {
                rich_bitset res = a;
                res += b;
                return res;
            }
            friend rich_bitset operator-(const rich_bitset& a, const rich_bitset& b) {
                rich_bitset res = a;
                res -= b;
                return res;
            }
            friend bool operator==(const rich_bitset& a, const rich_bitset& b) {
                return memcmp(a.data, b.data, sizeof(a.data)) == 0;
            }
            friend bool operator!=(const rich_bitset& a, const rich_bitset& b) {
                return memcmp(a.data, b.data, sizeof(a.data)) != 0;
            }
            friend int operator<=>(const rich_bitset& a, const rich_bitset& b) {
                REP_WORDS_REV(i) {
                    if (a.data[i] != b.data[i])
                        return a.data[i] < b.data[i] ? -1 : 1;
                }
                return 0;
            }
            ref operator[](int pos) {
                return {*this, pos};
            }
            bool operator[](int pos) const {
                return test(pos);
            }
            string str() const {
                ostringstream oss;
                oss << *this;
                return oss.str();
            }
            friend ostream& operator<<(ostream& out, const rich_bitset& bs) {
                for (int i = Size - 1; i >= 0; i--) {
                    out << (bs.test(i) ? '1' : '0');
                }
                return out;
            }
#undef REP_WORDS
#undef REP_INNER_WORDS
#undef REP_WORDS_REV
#undef REP_INNER_WORDS_REV
        };
        template <class T>
        class easy_stack {
        private:
            vector<T> data;
        public:
            auto begin() {
                return data.begin();
            }
            auto end() {
                return data.end();
            }
            auto begin() const {
                return data.begin();
            }
            auto end() const {
                return data.end();
            }
            void push_back(T a) {
                data.push_back(a);
            }
            template <class... Args>
            void emplace(Args&&... args) {
                data.emplace_back(forward<Args>(args)...);
            }
            T pop_back() {
                T res = data.back();
                data.pop_back();
                return res;
            }
            int size() const {
                return (int) data.size();
            }
            bool empty() const {
                return data.empty();
            }
        };
        template <int N>
        int len(const fast_iset<N>& a) {
            return a.size();
        }
        template <class T, int N>
        int len(const fast_vector<T, N>& a) {
            return a.size();
        }
        template <class T, int BucketBits>
        int len(const hash_imap<T, BucketBits>& a) {
            return a.size();
        }
        template <class T>
        int len(const easy_stack<T>& a) {
            return a.size();
        }
    } // namespace ds
    using namespace ds;
    namespace beam_search {
        // (state) -> score
        template <class T, class State, class Score>
        concept get_score =
            totally_ordered<Score> && invocable<T, State&> && same_as<invoke_result_t<T, State&>, Score>;
        // (state, move) -> void
        template <class T, class State, class MoveId>
        concept apply_move =
            invocable<T, State&, MoveId> && same_as<invoke_result_t<T, State&, MoveId>, void>;
        // (state) -> void
        template <class T, class State>
        concept undo_move = invocable<T, State&> && same_as<invoke_result_t<T, State&>, void>;
        // (state) -> void
        // see also: add_candidate
        template <class T, class State>
        concept enumerate_candidates = invocable<T, State&> && same_as<invoke_result_t<T, State&>, void>;
        // (turn) -> void
        // see also: candidates_to_filter
        template <class T>
        concept filter_candidates = invocable<T, int> && same_as<invoke_result_t<T, int>, void>;
        template <class State, totally_ordered Score, class MoveId, MoveId UnusedMoveId, class CandidateData,
            class Direction = greater<Score>, int HashBucketBits = 20>
        class beam_search {
        private:
            struct candidate {
                int index; // index in orig_candidates
                int parent;
                MoveId move_id;
                CandidateData data;
                ull hash;
            };
            struct orig_candidate {
                int parent;
                MoveId move_id;
                bool chosen;
            };
            Direction dir = {};
            int current_parent = 0;
            hash_imap<int, HashBucketBits> best_indices;
            bool enumerating = false;
            bool filtering = false;
            vector<candidate> candidates;
            vector<orig_candidate> orig_candidates;
            void clear_candidates() {
                candidates.clear();
                orig_candidates.clear();
            }
        public:
            Score best_score = 0;
            int max_turn = -1;
            beam_search() {
            }
            beam_search(Direction dir) : dir(dir) {
            }
            void add_candidate(MoveId move_id, CandidateData data, ull hash) {
                assert(("not enumerating now", enumerating));
                candidates.emplace_back((int) candidates.size(), current_parent, move_id, data, hash);
                orig_candidates.emplace_back(current_parent, move_id);
            }
            vector<candidate>& candidates_to_filter() {
                assert(("not filtering now", filtering));
                return candidates;
            }
            // CAUTION: not stable
            template <predicate<candidate&, candidate&> CandidateDirection>
            void remove_duplicates(CandidateDirection candidate_direction) {
                assert(("not filtering now", filtering));
                best_indices.clear();
                int n = (int) candidates.size();
                for (int i = 0; i < n; i++) {
                    candidate& cand = candidates[i];
                    if (best_indices.access(cand.hash)) {
                        int j = best_indices.get();
                        candidate& cand2 = candidates[j];
                        if (candidate_direction(cand, cand2)) {
                            swap(candidates[i], candidates[j]);
                        }
                        swap(candidates[i], candidates[--n]);
                        i--;
                    } else {
                        best_indices.set(i);
                    }
                }
                candidates.resize(n);
            }
            template <get_score<State, Score> GetScore, apply_move<State, MoveId> ApplyMove,
                enumerate_candidates<State> EnumerateCandidates, filter_candidates FilterCandidates>
            vector<MoveId> run(const State& initial_state, GetScore get_score, ApplyMove apply_move,
                EnumerateCandidates enumerate_candidates, FilterCandidates filter_candidates) {
                struct node {
                    State state;
                    int history_index;
                };
                struct history {
                    MoveId move_id;
                    int parent;
                };
                vector<node> src;
                vector<node> dst;
                increasing_vector<history> hs;
                int turn = 0;
                // set initial state
                src.emplace_back(initial_state, -1);
                while (true) {
                    int num_states = (int) src.size();
                    clear_candidates();
                    if (max_turn == -1 || turn < max_turn) {
                        // enumerate candidates
                        enumerating = true;
                        for (int i = 0; i < num_states; i++) {
                            current_parent = i;
                            enumerate_candidates(src[i].state);
                        }
                        enumerating = false;
                        // filer candiadtes
                        filtering = true;
                        filter_candidates(turn);
                        filtering = false;
                    }
                    // check if finished
                    if (candidates.empty()) {
                        assert(("no states at the end", num_states > 0));
                        // pick the best state
                        best_score = get_score(src[0].state);
                        int best_index = 0;
                        for (int i = 1; i < num_states; i++) {
                            Score score = get_score(src[i].state);
                            if (dir(score, best_score)) {
                                best_score = score;
                                best_index = i;
                            }
                        }
                        // restore moves
                        vector<MoveId> res;
                        int history_top = src[best_index].history_index;
                        while (history_top != -1) {
                            history& h = hs[history_top];
                            res.push_back(h.move_id);
                            history_top = h.parent;
                        }
                        reverse(res.begin(), res.end());
                        return res;
                    }
                    // compute next states
                    dst.clear();
                    for (const auto& cand : candidates) {
                        const auto& src_node = src[cand.parent];
                        dst.emplace_back(src_node.state, hs.size());
                        apply_move(dst.back().state, cand.move_id);
                        hs.emplace_back(cand.move_id, src_node.history_index);
                    }
                    src.swap(dst);
                    turn++;
                }
            }
            template <get_score<State, Score> GetScore, apply_move<State, MoveId> ApplyMove,
                undo_move<State> UndoMove, enumerate_candidates<State> EnumerateCandidates,
                filter_candidates FilterCandidates>
            vector<MoveId> run_tree(const State& initial_state, GetScore get_score, ApplyMove apply_move,
                UndoMove undo_move, EnumerateCandidates enumerate_candidates,
                FilterCandidates filter_candidates) {
                constexpr MoveId UNDO = UnusedMoveId;
                struct tour {
                    vector<MoveId> src;
                    vector<MoveId> dst;
                    void move(const MoveId& move_id) {
                        dst.push_back(move_id);
                    }
                    int position() {
                        return (int) dst.size();
                    }
                    void swap() {
                        src.swap(dst);
                        dst.clear();
                    }
                } tour;
                vector<MoveId> global_path;
                vector<MoveId> path;
                vector<orig_candidate> leaves;
                State st = initial_state;
                int turn = 0;
                int level = 0;
                int next_start_pos = 0;
                auto global_move = [&](const MoveId& move_id) {
                    apply_move(st, move_id);
                    global_path.push_back(move_id);
                    level++;
                };
                auto global_undo = [&]() {
                    undo_move(st);
                    global_path.pop_back();
                    level--;
                };
                while (true) {
                    bool has_next_turn = max_turn == -1 || turn < max_turn;
                    // compute the next tour
                    int pos = next_start_pos;
                    int prev_root_level = level;
                    int next_root_level = numeric_limits<int>::max();
                    orig_candidate best_leaf = {-1, MoveId{}, false};
                    enumerating = true;
                    clear_candidates();
                    if (turn == 0) {
                        best_score = get_score(st);
                        best_leaf.chosen = true;
                        if (has_next_turn) {
                            current_parent = tour.position();
                            enumerate_candidates(st);
                        }
                    } else {
                        for (const orig_candidate& leaf : leaves) {
                            int parent_pos = leaf.parent;
                            // visit the parent of the leaf node
                            if (pos < parent_pos) {
                                // visit the LCA
                                path.clear();
                                do {
                                    auto move = tour.src[pos++];
                                    if (move == UNDO) {
                                        if (path.empty()) {
                                            global_undo();
                                            tour.move(UNDO);
                                            next_root_level = min(next_root_level, level);
                                        } else {
                                            path.pop_back();
                                        }
                                    } else {
                                        path.push_back(move);
                                    }
                                } while (pos < parent_pos);
                                // go directly to the parent
                                for (auto move : path) {
                                    global_move(move);
                                    tour.move(move);
                                }
                            } // now we are at the parent of the leaf node
                            // visit the leaf node
                            apply_move(st, leaf.move_id);
                            tour.move(leaf.move_id);
                            Score score = get_score(st);
                            if (!best_leaf.chosen || dir(score, best_score)) {
                                best_score = score;
                                best_leaf = leaf;
                            }
                            if (has_next_turn) {
                                current_parent = tour.position();
                                enumerate_candidates(st);
                            }
                            // leave the leaf node
                            undo_move(st);
                            tour.move(UNDO);
                        }
                    }
                    next_root_level = min(next_root_level, level);
                    enumerating = false;
                    filtering = true;
                    filter_candidates(turn);
                    filtering = false;
                    if (candidates.empty()) {
                        assert(best_leaf.chosen);
                        // undo to the root level
                        while (level > prev_root_level) {
                            global_undo();
                        }
                        // visit the best leaf
                        pos = next_start_pos;
                        while (pos < best_leaf.parent) {
                            auto move = tour.src[pos++];
                            if (move == UNDO) {
                                global_undo();
                            } else {
                                global_move(move);
                            }
                        }
                        if (best_leaf.parent != -1) {
                            global_move(best_leaf.move_id);
                        }
                        return global_path;
                    }
                    // finalize the next tour
                    tour.swap();
                    turn++;
                    // collect the next leaf nodes, in the original order
                    leaves.clear();
                    for (const candidate& cand : candidates) {
                        orig_candidates[cand.index].chosen = true;
                    }
                    for (const orig_candidate& cand : orig_candidates) {
                        if (!cand.chosen)
                            continue;
                        leaves.push_back(cand);
                    }
                    // undo to the next root level
                    while (level > next_root_level) {
                        global_undo();
                    }
                    // adjust the next starting position
                    next_start_pos = next_root_level - prev_root_level;
                }
            }
        };
        class beam_width_manager {
        private:
            double prev_time = 0;
            double moving_average_time = 0;
            vector<double> progress_history;
            vector<double> time_history;
            vector<int> width_history;
            int last_width = 0;
            int count = 0;
        public:
            int window_size = 50;
            int default_width;
            beam_width_manager(int default_width) : default_width(default_width) {
            }
            int next(double progress, double time, double time_limit) {
                progress_history.push_back(progress);
                time_history.push_back(time);
                width_history.push_back(last_width);
                count++;
                if (count <= window_size) {
                    return last_width = default_width;
                }
                int i1 = count - 1 - window_size;
                int i2 = count - 1;
                double progress_sum = progress_history[i2] - progress_history[i1];
                double time_sum = time_history[i2] - time_history[i1];
                if (progress_sum == 0 || time_sum == 0) {
                    // window size is too small
                    window_size *= 2;
                    return last_width = default_width;
                }
                int width_sum = 0;
                for (int i = i1 + 1; i <= i2; i++) {
                    width_sum += width_history[i];
                }
                double progress_per_turn = progress_sum / window_size;
                double time_per_width = time_sum / width_sum;
                double left_time = time_limit - time;
                double left_progress = 1 - progress;
                if (left_time <= 0 || left_progress <= 0)
                    return 1;
                double left_turn = left_progress / progress_per_turn;
                double left_time_per_turn = left_time / left_turn;
                double left_width_per_turn = left_time_per_turn / time_per_width;
                return last_width = round(left_width_per_turn);
            }
            void report(int actual_last_width) {
                last_width = actual_last_width;
            }
        };
    } // namespace beam_search
    namespace simulated_annealing {
        // (state) -> score
        template <class T, class State, class Score>
        concept get_score =
            totally_ordered<Score> && invocable<T, State&> && same_as<invoke_result_t<T, State&>, Score>;
        // (iter) -> progress
        template <class T>
        concept update_progress = invocable<T, int> && same_as<invoke_result_t<T, int>, double>;
        // (state, tolerance) -> accepted
        template <class T, class State>
        concept try_transition =
            invocable<T, State&, double> && same_as<invoke_result_t<T, State&, double>, bool>;
        template <class State, totally_ordered Score, class Direction = greater<Score>>
        class simulated_annealing {
        private:
            Direction dir = {};
        public:
            int clock_interval = 10;
            double t_from = 100;
            double t_to = 0.01;
            double progress = 0;
            int num_iterations = 0;
            int num_acceptances = 0;
            int num_rejections = 0;
            bool use_linear_temp = false;
            Score best_score = 0;
            simulated_annealing() {
            }
            simulated_annealing(Direction dir) : dir(dir) {
            }
            template <get_score<State, Score> GetScore, update_progress UpdateProgress,
                try_transition<State> TryTransition>
            State run(const State& initial_state, rngen& rng, GetScore get_score,
                UpdateProgress update_progress, TryTransition try_transition,
                function<void(State&, Score, int, double)> best_updated = nullptr) {
                State state = initial_state;
                Score score = get_score(state);
                State best_state = state;
                best_score = score;
                num_iterations = 0;
                num_acceptances = 0;
                num_rejections = 0;
                int interval = clock_interval;
                progress = 0;
                double t = t_from;
                while (true) {
                    if (--interval <= 0) {
                        progress = update_progress(num_iterations);
                        if (progress >= 1)
                            break;
                        t = use_linear_temp ? lerp(t_from, t_to, progress)
                                            : exp_interp(t_from, t_to, progress);
                        interval = clock_interval;
                    }
                    double tolerance = t * -log(rng.next_float());
                    if (try_transition(state, tolerance)) {
                        num_acceptances++;
                        score = get_score(state);
                        if (dir(score, best_score)) {
                            best_state = state;
                            best_score = score;
                            if (best_updated) {
                                best_updated(state, score, num_iterations, t);
                            }
                        }
                    } else {
                        num_rejections++;
                    }
                    num_iterations++;
                }
                return best_state;
            }
        };
    } // namespace simulated_annealing
    namespace dijkstra {
        // (vertex) -> index
        template <class T, class Vertex>
        concept get_index = invocable<T, Vertex> && same_as<invoke_result_t<T, Vertex>, int>;
        // (vertex) -> is_goal
        template <class T, class Vertex>
        concept is_goal = invocable<T, Vertex> && same_as<invoke_result_t<T, Vertex>, bool>;
        // (vertex, distance) -> void
        template <class T, class Vertex, class Weight>
        concept visit_adjacent_vertices =
            invocable<T, Vertex, Weight> && same_as<invoke_result_t<T, Vertex, Weight>, void>;
        template <class Vertex, class Weight, Weight Infinity, int MaxVertexIndex>
        requires(integral<Weight> || floating_point<Weight>)
        class dijkstra {
        private:
            using vw = pair<Vertex, Weight>;
            static constexpr int VERTEX_ARRAY_SIZE = MaxVertexIndex + 1;
            vector<vw> toVisit;
            bool visiting = false;
        public:
            array<bool, VERTEX_ARRAY_SIZE> visited;
            array<Weight, VERTEX_ARRAY_SIZE> distance;
            array<optional<Vertex>, VERTEX_ARRAY_SIZE> previous;
            dijkstra() {
            }
            template <get_index<Vertex> GetIndex, is_goal<Vertex> IsGoal,
                visit_adjacent_vertices<Vertex, Weight> VisitAdjacentVertices>
            void run(const vector<Vertex>& starts, GetIndex get_index, IsGoal is_goal,
                VisitAdjacentVertices visit_adjacent_vertices) {
                auto comp = [](vw& a, vw& b) {
                    return a.second > b.second;
                };
                visited.fill(false);
                previous.fill(nullopt);
                distance.fill(Infinity);
                priority_queue<vw, vector<vw>, decltype(comp)> q(comp);
                for (auto& st : starts) {
                    distance[get_index(st)] = Weight(0);
                    q.emplace(st, Weight(0));
                }
                int loop = 0;
                while (!q.empty()) {
                    if (++loop % 10 == 0)
                        trace(loop, " ", timer::timer());
                    auto [from, dist] = q.top();
                    q.pop();
                    int fromi = get_index(from);
                    if (visited[fromi])
                        continue;
                    visited[fromi] = true;
                    if (is_goal(from)) {
                        return;
                    }
                    visiting = true;
                    toVisit.clear();
                    visit_adjacent_vertices(from, dist);
                    visiting = false;
                    for (vw& pair : toVisit) {
                        Vertex to = pair.first;
                        int toi = get_index(to);
                        Weight new_dist = pair.second;
                        if (new_dist < distance[toi]) {
                            distance[toi] = new_dist;
                            previous[toi] = from;
                            q.emplace(to, new_dist);
                        }
                    }
                }
            }
            void visit(Vertex vertex, Weight total_distance) {
                assert(("not visiting now", visiting));
                toVisit.emplace_back(vertex, total_distance);
            }
            template <get_index<Vertex> GetIndex>
            vector<Vertex> restore_path(Vertex goal, GetIndex get_index) {
                assert(("goal not reached", visited[get_index(goal)]));
                vector<Vertex> res;
                Vertex v = goal;
                while (true) {
                    res.push_back(v);
                    if (!previous[get_index(v)])
                        break;
                    v = previous[get_index(v)].value();
                }
                reverse(res.begin(), res.end());
                return res;
            }
        };
    }; // namespace dijkstra
    namespace file {
        string pad4(int n) {
            return (n < 0 || n >= 1000 ? "" : n < 10 ? "000" : n < 100 ? "00" : "0") + tos(n);
        }
        string input_file_name(int seed) {
            return "in/" + pad4(seed) + ".txt";
        }
        string output_file_name(int seed) {
            return "out/" + pad4(seed) + ".txt";
        }
        string movie_file_name(int seed) {
            return "mov/" + pad4(seed) + ".smv";
        }
        bool write_text(string fileName, string text, bool append = false) {
            ofstream fout;
            fout.open(fileName, append ? ios::out | ios::app : ios::out);
            if (!fout)
                return false;
            fout << text;
            fout.close();
            return true;
        }
        pair<string, bool> read_text(string fileName) {
            ifstream fin;
            fin.open(fileName, ios::in);
            if (!fin)
                return make_pair("", false);
            string res;
            string line;
            while (getline(fin, line)) {
                res += line;
                res += "\n";
            }
            return make_pair(res, true);
        }
        void write_text_assert(string fileName, string text, bool append = false) {
            auto res = write_text(fileName, text, append);
            assert(res);
        }
        string read_text_assert(string fileName) {
            auto res = read_text(fileName);
            assert(res.second);
            return res.first;
        }
    } // namespace file
} // namespace shr
using namespace shr::basic;
using namespace shr::ds;
using namespace shr::beam_search;
using namespace shr::simulated_annealing;
using namespace shr::dijkstra;
using namespace shr::random;
using namespace shr::timer;
using namespace shr::tracer;
using namespace shr::file;
//
// --- macros ---
//
#define rep(i, from, until) for (int i = (from); i < (until); i++)
#define repr(i, from, until) for (int i = (until) -1; i >= (from); i--)
#define rep0(i, until) rep(i, 0, until)
#define rep0r(i, until) repr(i, 0, until)
//
// --- movie lib ---
//
class movie {
private:
    bool is_open = false;
    string file_name;
    ofstream out;
#ifdef ONLINE_JUDGE
    void write_instruction(const string& it, const vector<double>& argf, const vector<string>& args) {
    }
#else
    void write_instruction(const string& it, const vector<double>& argf, const vector<string>& args) {
        assert(("file name is not set", file_name != ""));
        if (!is_open) {
            is_open = true;
            out = ofstream(file_name, ios_base::out | ios_base::binary);
            out.write("smv", 3);
        }
        write_string(it);
        for (double f : argf) {
            write_float(f);
        }
        for (auto& s : args) {
            write_string(s);
        }
        if (it == "n") {
            out.flush(); // flush at the end of each frame
        }
    }
    void write_float(double a) {
        float f = (float) a;
        out.write((char*) &f, 4);
    }
    void write_string(const string& str) {
        out.write(str.c_str(), str.length() + 1);
    }
#endif
public:
    static constexpr int LEFT = 0;
    static constexpr int CENTER = 1;
    static constexpr int RIGHT = 2;
    movie() {
    }
    void set_file(string file) {
        assert(!is_open);
        file_name = file;
    }
    void close_file() {
        if (!is_open)
            return;
        is_open = false;
        out.close();
    }
    void fill(double rgb, double a = 1.0) {
        fill(rgb, rgb, rgb, a);
    }
    void fill(double r, double g, double b, double a = 1.0) {
        write_instruction("f", {r, g, b, a}, {});
    }
    void stroke(double rgb, double a = 1.0) {
        stroke(rgb, rgb, rgb, a);
    }
    void stroke(double r, double g, double b, double a = 1.0) {
        write_instruction("s", {r, g, b, a}, {});
    }
    void no_fill() {
        write_instruction("nf", {}, {});
    }
    void no_stroke() {
        write_instruction("ns", {}, {});
    }
    void comment(string text) {
        write_instruction("cm", {}, {text});
    }
    void tooltip(string text) {
        write_instruction("tt", {}, {text});
    }
    void no_tooltip() {
        write_instruction("nt", {}, {});
    }
    void stroke_weight(double weight) {
        write_instruction("sw", {weight}, {});
    }
    void text_size(double size) {
        write_instruction("ts", {size}, {});
    }
    void text_align(int align) {
        write_instruction("ta", {(double) align}, {});
    }
    void rect(double x, double y, double w, double h) {
        write_instruction("r", {x, y, w, h}, {});
    }
    void circle(double x, double y, double r) {
        write_instruction("c", {x, y, r}, {});
    }
    void ellipse(double x, double y, double rx, double ry) {
        write_instruction("e", {x, y, rx, ry}, {});
    }
    void line(double x1, double y1, double x2, double y2) {
        write_instruction("l", {x1, y1, x2, y2}, {});
    }
    void text(string str, double x, double y) {
        write_instruction("t", {x, y}, {str});
    }
    void transform(double e00, double e01, double e10, double e11) {
        write_instruction("tf", {e00, e01, e10, e11}, {});
    }
    void translate(double tx, double ty) {
        write_instruction("tr", {tx, ty}, {});
    }
    void rotate(double ang) {
        write_instruction("ro", {ang}, {});
    }
    void scale(double s) {
        scale(s, s);
    }
    void scale(double sx, double sy) {
        write_instruction("sc", {sx, sy}, {});
    }
    void push() {
        write_instruction("pu", {}, {});
    }
    void pop() {
        write_instruction("po", {}, {});
    }
    void end_frame() {
        write_instruction("n", {}, {});
    }
    void target(string name) {
        write_instruction("tg", {}, {name});
    }
};
movie mov;
// --------------------------------------------------
// main part
// --------------------------------------------------
bool isLocal = false;
bool render = false;
// define N and stuff here
constexpr int N = 45;
constexpr int N2 = N * 2;
constexpr int M = 50;
#define repn(i) rep0(i, N)
#define repm(i) rep0(i, M)
class Problem {
private:
public:
    array<array<ll, 2>, N> vs;
    void load(istream& in) {
        // read input here
        int n;
        in >> n;
        assert(n == N);
        repn(i) {
            in >> vs[i][0] >> vs[i][1];
        }
    }
};
struct SolverResult {
    ll score = 0;
};
class Solver {
public:
    int seed;
    rngen rng;
    SolverResult result;
    Problem p;
    Solver() : rng() {
    }
    void load(istream& in, int seed = -1) {
        p.load(in);
        mov.set_file(movie_file_name(seed));
        init();
    }
    void load(int seed) {
        this->seed = seed;
        istringstream in(read_text_assert(input_file_name(seed)));
        isLocal = true;
        load(in, seed);
    }
    void solve() {
        if (isLocal) {
            ostringstream out;
            solveMain(out);
            mov.close_file();
            write_text(output_file_name(seed), out.str());
        } else {
            solveMain(cout);
        }
    }
private:
    void init() {
    }
    void solveMain(ostream& out) { // write answer to out
        constexpr ll TARGET = (ll) (5e17);
        array<ll, N2> cs;
        repn(i) {
            cs[i << 1] = p.vs[i][0];
            cs[i << 1 | 1] = p.vs[i][1];
        }
        auto op = [&](int i, int j) {
            return make_pair(cs[i << 1] + cs[j << 1] >> 1, cs[i << 1 | 1] + cs[j << 1 | 1] >> 1);
        };
        auto getScore = [&](ll a, ll b) {
            return 20000000 - 100000 * log10(max(abs(a - TARGET), abs(b - TARGET)) + 1);
        };
        // vector<pii> ops;
        // repm(iter) {
        //  double score = getScore(cs[0], cs[1]);
        //  double bestScore = score;
        //  int bestI = -1;
        //  rep(i, 1, N) {
        //      auto [a, b] = op(0, i);
        //      double score = getScore(a, b);
        //      if (update_max(score, bestScore)) {
        //          bestI = i;
        //      }
        //  }
        //  if (bestI == -1)
        //      break;
        //  auto [a, b] = op(0, bestI);
        //  cs[0] = a;
        //  cs[1] = b;
        //  cs[bestI << 1 | 0] = a;
        //  cs[bestI << 1 | 1] = b;
        //  trace(bestI, " ", log10(max(abs(a - TARGET), abs(b - TARGET))), " ", bestScore, " ", iter);
        // }
        // out << len(ops) << endl;
        // for (auto [a, b] : ops) {
        //  out << a + 1 << " " << b + 1 << endl;
        // }
        struct State {
            ll cs[N2];
            ll hist[M * 4];
            int ihist[M * 2];
            int turn = 0;
        };
        auto diff = [&](ll cs[N2], int i) {
            return max(abs(cs[i << 1] - TARGET), abs(cs[i << 1 | 1] - TARGET));
        };
        auto apply = [&](State& st, short move) {
            int i = move >> 8 & 0xff;
            int j = move & 0xff;
            ll ai = st.cs[i << 1];
            ll bi = st.cs[i << 1 | 1];
            ll aj = st.cs[j << 1];
            ll bj = st.cs[j << 1 | 1];
            ll a = ai + aj >> 1;
            ll b = bi + bj >> 1;
            st.hist[st.turn << 2 | 0] = ai;
            st.hist[st.turn << 2 | 1] = bi;
            st.hist[st.turn << 2 | 2] = aj;
            st.hist[st.turn << 2 | 3] = bj;
            st.ihist[st.turn << 1 | 0] = i;
            st.ihist[st.turn << 1 | 1] = j;
            st.cs[i << 1] = a;
            st.cs[i << 1 | 1] = b;
            st.cs[j << 1] = a;
            st.cs[j << 1 | 1] = b;
            st.turn++;
        };
        auto undo = [&](State& st) {
            st.turn--;
            int i = st.ihist[st.turn << 1 | 0];
            int j = st.ihist[st.turn << 1 | 1];
            ll ai = st.hist[st.turn << 2 | 0];
            ll bi = st.hist[st.turn << 2 | 1];
            ll aj = st.hist[st.turn << 2 | 2];
            ll bj = st.hist[st.turn << 2 | 3];
            ll a = st.cs[i << 1];
            ll b = st.cs[i << 1 | 1];
            st.cs[i << 1] = ai;
            st.cs[i << 1 | 1] = bi;
            st.cs[j << 1] = aj;
            st.cs[j << 1 | 1] = bj;
        };
        beam_search<State, ll, short, -1, ll, less<ll>, 24> bs;
        bs.max_turn = M;
        State st;
        repn(i) {
            st.cs[i << 1] = cs[i << 1];
            st.cs[i << 1 | 1] = cs[i << 1 | 1];
        }
        auto res = bs.run_tree(
            st,
            [&](State& st) {
                return max(abs(st.cs[0] - TARGET), abs(st.cs[1] - TARGET));
            },
            apply, undo,
            [&](State& st) {
                auto getScore = [&]() {
                    ll res = diff(st.cs, 0);
                    res += diff(st.cs, 1) >> 1;
                    res += diff(st.cs, 2) >> 2;
                    res += diff(st.cs, 3) >> 3;
                    res += diff(st.cs, 4) >> 4;
                    res += diff(st.cs, 5) >> 5;
                    return res;
                };
                ll cscore = getScore();
                bs.add_candidate(0, cscore, 0);
                rep0(i, N - 1) {
                    rep(j, i + 1, N) {
                        apply(st, i << 8 | j);
                        ll score = getScore();
                        undo(st);
                        bs.add_candidate(i << 8 | j, score, 0);
                    }
                }
            },
            [&](int turn) {
                auto& cands = bs.candidates_to_filter();
                int bw = 300;
                auto better = [&](auto& a, auto& b) {
                    return a.data < b.data;
                };
                trace(turn, " ", len(cands));
                static hash_imap<int> counts;
                counts.clear();
                if (len(cands) > bw) {
                    ranges::sort(cands, better);
                    erase_if(cands, [&](auto& a) {
                        if (counts.access(a.parent)) {
                            int num = counts.get();
                            if (num > 10)
                                return true;
                            counts.set(num + 1);
                        } else {
                            counts.set(1);
                        }
                        return false;
                    });
                    if (len(cands) > bw) {
                        nth_element(cands.begin(), cands.begin() + bw, cands.end(), better);
                        cands.resize(bw);
                    }
                }
            });
        erase_if(res, [&](auto move) {
            return move == 0;
        });
        trace(round(2e6 - 1e5 * log10(bs.best_score)) * 50);
        out << len(res) << endl;
        for (short move : res) {
            out << (move >> 8 & 0xff) + 1 << " " << (move & 0xff) + 1 << endl;
            // trace(move >> 8 & 0xff, " ", move & 0xff);
        }
    }
};
int main() {
#if 0 || ONLINE_JUDGE
    isLocal = false;
    render = false;
    timer(true);
    Solver sol;
    sol.load(cin);
    sol.solve();
#elif 0
    compareScores("cut", "nocut");
    // compareScores("new6", "new10");
#elif 0
    // for local and remote testers
    debug = false;
    render = false;
    int seed;
    cin >> seed;
    cin >> time_scale;
    timer(true);
    Solver sol;
    sol.load(seed);
    cout << sol.result.score << endl;
#elif 1
    // single-threaded test, handy but slow
    time_scale = 1.0;
    int num = 50;
    int from = 0;
    int stride = 1;
    int single = 0;
    debug = true;
    render = false;
    struct TestCase {
        int seed;
        int time;
        ll score;
    };
    vector<TestCase> cases;
    vector<int> seedList = {};
    if (seedList.empty()) {
        if (single == -1) {
            rep0(t, num) {
                seedList.push_back(from + t * stride);
            }
        } else {
            seedList.push_back(single);
        }
    }
    bool doTrace = debug;
    debug = true;
    for (int seed : seedList) {
        timer(true);
        trace("------------ SOLVING SEED ", seed, " ------------");
        debug = doTrace;
        Solver s;
        s.load(seed);
        s.solve();
        debug = true;
        int time = timer();
        trace("score: ", s.result.score, " (time ", time, " ms)\n");
        if (s.result.score != -1)
            cases.emplace_back(seed, time, s.result.score);
    }
    auto print = [&](const TestCase& c) {
        int seed = c.seed;
        string space = seed < 10 ? "   " : seed < 100 ? "  " : seed < 1000 ? " " : "";
        trace("  seed ", space, seed, ": ", c.score, " (time ", c.time, " ms)");
    };
    if (len(cases) > 1) {
        trace("------------ summary ------------");
        trace("sort by seed:");
        sort(cases.begin(), cases.end(), [&](auto a, auto b) {
            return a.seed < b.seed;
        });
        for (auto& c : cases)
            print(c);
        trace("sort by score:");
        sort(cases.begin(), cases.end(), [&](auto a, auto b) {
            return a.score > b.score;
        });
        for (auto& c : cases)
            print(c);
        ll scoreSum = 0;
        double logScoreSum = 0;
        for (auto& c : cases) {
            scoreSum += c.score;
            logScoreSum += log(c.score);
        }
        double invDenom = 1.0 / len(cases);
        trace("total score: ", scoreSum, ", mean: ", (ll) (scoreSum * invDenom * 100 + 0.5) / 100.0,
            ", mean(log2): ", (ll) (logScoreSum * invDenom * 1000 + 0.5) / 1000.0);
    }
#endif
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0