Submission #67648099

---

Source Code Expand

// #undef YOSUPO_LOCAL

#if 0 and !defined(__clang__)
#include <vector>
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("Ofast")
#endif


#include <array>
#include <cassert>
#include <initializer_list>
#include <string>


#include <cstddef>
#include <ranges>
#include <utility>

namespace yosupo {

struct Coord {
  public:
    constexpr Coord() : d{0, 0} {}
    constexpr Coord(int _r, int _c) : d{_r, _c} {}
    constexpr Coord(const std::pair<int, int>& p) : d{p.first, p.second} {}

    bool operator==(const Coord& other) const { return d == other.d; }

    Coord& operator+=(const Coord& other) {
        d[0] += other.d[0];
        d[1] += other.d[1];
        return *this;
    }
    Coord operator+(const Coord& other) const {
        Coord result = *this;
        result += other;
        return result;
    }

    Coord& operator-=(const Coord& other) {
        d[0] -= other.d[0];
        d[1] -= other.d[1];
        return *this;
    }
    Coord operator-(const Coord& other) const {
        Coord result = *this;
        result -= other;
        return result;
    }

    int& r() { return d[0]; }
    int& c() { return d[1]; }
    const int& r() const { return d[0]; }
    const int& c() const { return d[1]; }

    int& operator[](int index) {
        if (index == 0) return d[0];
        if (index == 1) return d[1];
        assert(false);
    }
    const int& operator[](int index) const {
        if (index == 0) return d[0];
        if (index == 1) return d[1];
        assert(false);
    }

    operator std::pair<int, int>() const { return std::make_pair(d[0], d[1]); }

    std::string dump() const {
        return "(" + std::to_string(d[0]) + ", " + std::to_string(d[1]) + ")";
    }

    Coord move4(int dir) const {
        static constexpr std::array<Coord, 4> d4 = {Coord(0, 1), Coord(1, 0),
                                                    Coord(0, -1), Coord(-1, 0)};
        return *this + d4[dir];
    }

    auto move4() const {
        return std::views::iota(0, 4) | std::views::transform([this](int dir) {
                   return this->move4(dir);
               });
    }

    Coord move8(int dir) const {
        static constexpr std::array<Coord, 8> d8 = {
            Coord(0, 1),  Coord(1, 1),   Coord(1, 0),  Coord(1, -1),
            Coord(0, -1), Coord(-1, -1), Coord(-1, 0), Coord(-1, 1)};
        assert(0 <= dir && dir < 8);
        return *this + d8[dir];
    }

    auto move8() const {
        return std::views::iota(0, 8) | std::views::transform([this](int dir) {
                   return this->move8(dir);
               });
    }

    bool contains(const Coord& t) const {
        return 0 <= t.r() && t.r() < r() && 0 <= t.c() && t.c() < c();
    }

    struct CellsRangeView {
        struct Iterator {
            using value_type = Coord;
            using difference_type = std::ptrdiff_t;

            int h, w, r, c;

            value_type operator*() const { return Coord{r, c}; }

            Iterator& operator++() {
                if (++c == w) {
                    c = 0;
                    ++r;
                }
                return *this;
            }
            Iterator operator++(int) {
                Iterator tmp = *this;
                ++(*this);
                return tmp;
            }

            bool operator==(const Iterator& other) const {
                return r == other.r && c == other.c;
            }
        };

        Iterator begin() const { return Iterator{h, w, 0, 0}; }
        Iterator end() const { return Iterator{h, w, h, 0}; }
        int h, w;
    };
    CellsRangeView cells() const { return CellsRangeView{r(), c()}; }

  private:
    std::array<int, 2> d;
};

}  // namespace yosupo

#include <algorithm>
#include <concepts>
#include <map>
#include <set>
#include <tuple>
#include <vector>


#include <cstdint>

namespace yosupo {

using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using i128 = __int128;
using u128 = unsigned __int128;

using f32 = float;
using f64 = double;

}  // namespace yosupo

namespace yosupo {

inline std::string dump(const std::string& t) { return t; }
inline std::string dump(const char* t) { return t; }

template <std::integral T> std::string dump(T t) { return std::to_string(t); }

inline std::string dump(const u128& t) {
    if (t == 0) {
        return "0";
    }

    std::string s;
    u128 x = t;
    while (x) {
        s += char(x % 10 + '0');
        x /= 10;
    }
    std::ranges::reverse(s);
    return s;
}

inline std::string dump(const i128& t) {
    if (t < 0) {
        return "-" + dump((u128)(-t));
    } else {
        return dump((u128)(t));
    }
}

template <std::floating_point T> std::string dump(T t) {
    return std::to_string(t);
}

template <class T>
    requires requires(T t) { t.dump(); }
std::string dump(T t);
template <class T>
    requires(!requires(T t) { t.dump(); }) && (requires(T t) { t.val(); })
std::string dump(T t);

template <class T, std::size_t N> std::string dump(const std::array<T, N>&);
template <class T> std::string dump(const std::vector<T>&);
template <class T1, class T2> std::string dump(const std::pair<T1, T2>&);
template <class K, class V> std::string dump(const std::map<K, V>&);
template <class T> std::string dump(const std::set<T>&);
template <class... Ts> std::string dump(const std::tuple<Ts...>& t);

template <class T>
    requires requires(T t) { t.dump(); }
std::string dump(T t) {
    return dump(t.dump());
}

template <class T>
    requires(!requires(T t) { t.dump(); }) && (requires(T t) { t.val(); })
std::string dump(T t) {
    return dump(t.val());
}

template <class T, std::size_t N> std::string dump(const std::array<T, N>& a) {
    std::string s = "[";
    for (size_t i = 0; i < N; i++) {
        if (i) {
            s += ", ";
        }
        s += dump(a[i]);
    }
    s += "]";
    return s;
}

template <class T> std::string dump(const std::vector<T>& v) {
    std::string s = "[";
    for (std::size_t i = 0; i < v.size(); ++i) {
        s += dump(v[i]);
        if (i + 1 != v.size()) {
            s += ", ";
        }
    }
    s += "]";
    return s;
}

template <class T1, class T2> std::string dump(const std::pair<T1, T2>& p) {
    std::string s = "(";
    s += dump(p.first);
    s += ", ";
    s += dump(p.second);
    s += ")";
    return s;
}

template <class K, class V> std::string dump(const std::map<K, V>& m) {
    std::string s = "{";
    for (auto it = m.begin(); it != m.end(); ++it) {
        if (it != m.begin()) {
            s += ", ";
        }
        s += dump(it->first);
        s += ": ";
        s += dump(it->second);
    }
    s += "}";
    return s;
}

template <class T> std::string dump(const std::set<T>& s) {
    std::string str = "{";
    for (auto it = s.begin(); it != s.end(); ++it) {
        if (it != s.begin()) {
            str += ", ";
        }
        str += dump(*it);
    }
    str += "}";
    return str;
}

template <class... Ts> std::string dump(const std::tuple<Ts...>& t) {
    std::string s = "(";
    [&]<std::size_t... I>(std::index_sequence<I...>) {
        ((s += dump(std::get<I>(t)) + ((I < sizeof...(Ts) - 1) ? ", " : "")),
         ...);
    }(std::make_index_sequence<sizeof...(Ts)>());
    s += ")";
    return s;
}

}  // namespace yosupo

namespace yosupo {

template <class T, int H, int W> struct Array2D {
    static_assert(H >= 0 && W >= 0);
    std::array<T, H * W> d;

    Array2D() : d{} {}
    Array2D(const T& val) { d.fill(val); }

    Array2D(std::initializer_list<std::initializer_list<T>> list) {
        assert(static_cast<int>(list.size()) == H);
        int i = 0;
        for (const auto& inner_list : list) {
            assert(static_cast<int>(inner_list.size()) == W);
            std::copy_n(inner_list.begin(), W, d.data() + i * W);
            i++;
        }
    }

    T& operator[](const Coord& idx) {
        assert(0 <= idx.r() && idx.r() < H);
        assert(0 <= idx.c() && idx.c() < W);
        return d[idx.r() * W + idx.c()];
    }
    const T& operator[](const Coord& idx) const {
        assert(0 <= idx.r() && idx.r() < H);
        assert(0 <= idx.c() && idx.c() < W);
        return d[idx.r() * W + idx.c()];
    }

    static Array2D e() {
        static_assert(H == W);
        Array2D mat;
        for (int i = 0; i < H; i++) {
            mat[{i, i}] = T(1);
        }
        return mat;
    }

    Array2D& operator+=(const Array2D& rhs) {
        for (int i = 0; i < H * W; i++) {
            d[i] += rhs.d[i];
        }
        return *this;
    }

    Array2D& operator-=(const Array2D& rhs) {
        for (int i = 0; i < H * W; i++) {
            d[i] -= rhs.d[i];
        }
        return *this;
    }

    friend Array2D operator+(const Array2D& lhs, const Array2D& rhs) {
        return Array2D(lhs) += rhs;
    }
    friend Array2D operator-(const Array2D& lhs, const Array2D& rhs) {
        return Array2D(lhs) -= rhs;
    }

    template <int K>
    friend Array2D<T, H, K> operator*(const Array2D& lhs,
                                      const Array2D<T, W, K>& rhs) {
        Array2D<T, H, K> res;
        Array2D<T, K, W> rhs_t = rhs.transpose();
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < K; j++) {
                for (int k = 0; k < W; k++) {
                    res[{i, j}] += lhs[{i, k}] * rhs_t[{j, k}];
                }
            }
        }
        return res;
    }

    Array2D& operator*=(const Array2D& r) {
        static_assert(H == W);
        return *this = *this * r;
    }

    Array2D<T, W, H> transpose() const {
        Array2D<T, W, H> res;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                res[{j, i}] = (*this)[{i, j}];
            }
        }
        return res;
    }

    Array2D pow(long long n) const {
        static_assert(H == W);
        Array2D x = *this, r = e();
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }

    std::string dump() const {
        std::string res;
        for (int i = 0; i < H; i++) {
            if (i) res += "\n";
            for (int j = 0; j < W; j++) {
                if (j) res += " ";
                res += yosupo::dump((*this)[{i, j}]);
            }
        }
        return res;
    }

    constexpr int height() const { return H; }
    constexpr int width() const { return W; }
};

}  // namespace yosupo

#include <stdio.h>
#include <unistd.h>

#include <bit>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <type_traits>



namespace yosupo {

namespace internal {

template <class T>
using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value ||
                                  std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value ||
                                  std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;

template <class T>
using is_integral =
    typename std::conditional<std::is_integral<T>::value ||
                                  internal::is_signed_int128<T>::value ||
                                  internal::is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<(is_integral<T>::value &&
                               std::is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename std::conditional<std::is_signed<T>::value,
                              std::make_unsigned<T>,
                              std::common_type<T>>::type>::type;

template <class T>
using is_integral_t = std::enable_if_t<is_integral<T>::value>;

template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

}  // namespace internal

}  // namespace yosupo

namespace yosupo {

struct Scanner {
  public:
    Scanner(const Scanner&) = delete;
    Scanner& operator=(const Scanner&) = delete;

    Scanner(FILE* fp) : fd(fileno(fp)) { line[0] = 127; }

    void read() {}
    template <class H, class... T> void read(H& h, T&... t) {
        bool f = read_single(h);
        assert(f);
        read(t...);
    }

    int read_unsafe() { return 0; }
    template <class H, class... T> int read_unsafe(H& h, T&... t) {
        bool f = read_single(h);
        if (!f) return 0;
        return 1 + read_unsafe(t...);
    }

    int close() { return ::close(fd); }

  private:
    static constexpr int SIZE = 1 << 15;

    int fd = -1;
    std::array<char, SIZE + 1> line;
    int st = 0, ed = 0;
    bool eof = false;

    bool read_single(std::string& ref) {
        if (!skip_space()) return false;
        ref = "";
        while (true) {
            char c = top();
            if (c <= ' ') break;
            ref += c;
            st++;
        }
        return true;
    }
    bool read_single(double& ref) {
        std::string s;
        if (!read_single(s)) return false;
        ref = std::stod(s);
        return true;
    }

    template <class T,
              std::enable_if_t<std::is_same<T, char>::value>* = nullptr>
    bool read_single(T& ref) {
        if (!skip_space<50>()) return false;
        ref = top();
        st++;
        return true;
    }

    template <class T,
              internal::is_signed_int_t<T>* = nullptr,
              std::enable_if_t<!std::is_same<T, char>::value>* = nullptr>
    bool read_single(T& sref) {
        using U = internal::to_unsigned_t<T>;
        if (!skip_space<50>()) return false;
        bool neg = false;
        if (line[st] == '-') {
            neg = true;
            st++;
        }
        U ref = 0;
        do {
            ref = 10 * ref + (line[st++] & 0x0f);
        } while (line[st] >= '0');
        sref = neg ? -ref : ref;
        return true;
    }
    template <class U,
              internal::is_unsigned_int_t<U>* = nullptr,
              std::enable_if_t<!std::is_same<U, char>::value>* = nullptr>
    bool read_single(U& ref) {
        if (!skip_space<50>()) return false;
        ref = 0;
        do {
            ref = 10 * ref + (line[st++] & 0x0f);
        } while (line[st] >= '0');
        return true;
    }

    bool reread() {
        if (ed - st >= 50) return true;
        if (st > SIZE / 2) {
            std::memmove(line.data(), line.data() + st, ed - st);
            ed -= st;
            st = 0;
        }
        if (eof) return false;
        auto u = ::read(fd, line.data() + ed, SIZE - ed);
        if (u == 0) {
            eof = true;
            line[ed] = '\0';
            u = 1;
        }
        ed += int(u);
        line[ed] = char(127);
        return true;
    }

    char top() {
        if (st == ed) {
            bool f = reread();
            assert(f);
        }
        return line[st];
    }

    template <int TOKEN_LEN = 0> bool skip_space() {
        while (true) {
            while (line[st] <= ' ') st++;
            if (ed - st > TOKEN_LEN) return true;
            if (st > ed) st = ed;
            for (auto i = st; i < ed; i++) {
                if (line[i] <= ' ') return true;
            }
            if (!reread()) return false;
        }
    }
};

struct Printer {
  public:
    template <char sep = ' ', bool F = false> void write() {}
    template <char sep = ' ', bool F = false, class H, class... T>
    void write(const H& h, const T&... t) {
        if (F) write_single(sep);
        write_single(h);
        write<true>(t...);
    }
    template <char sep = ' ', class... T> void writeln(const T&... t) {
        write<sep>(t...);
        write_single('\n');
    }

    Printer(FILE* _fp) : fd(fileno(_fp)) {}
    ~Printer() { flush(); }

    int close() {
        flush();
        return ::close(fd);
    }

    void flush() {
        if (pos) {
            auto res = ::write(fd, line.data(), pos);
            assert(res != -1);
            pos = 0;
        }
    }

  private:
    static std::array<std::array<char, 2>, 100> small;
    static std::array<unsigned long long, 20> tens;

    static constexpr size_t SIZE = 1 << 15;
    int fd;
    std::array<char, SIZE> line;
    size_t pos = 0;
    std::stringstream ss;

    template <class T,
              std::enable_if_t<std::is_same<char, T>::value>* = nullptr>
    void write_single(const T& val) {
        if (pos == SIZE) flush();
        line[pos++] = val;
    }

    template <class T,
              internal::is_signed_int_t<T>* = nullptr,
              std::enable_if_t<!std::is_same<char, T>::value>* = nullptr>
    void write_single(const T& val) {
        using U = internal::to_unsigned_t<T>;
        if (val == 0) {
            write_single('0');
            return;
        }
        if (pos > SIZE - 50) flush();
        U uval = val;
        if (val < 0) {
            write_single('-');
            uval = -uval;
        }
        write_unsigned(uval);
    }

    template <class U,
              internal::is_unsigned_int_t<U>* = nullptr,
              std::enable_if_t<!std::is_same<char, U>::value>* = nullptr>
    void write_single(U uval) {
        if (uval == 0) {
            write_single('0');
            return;
        }
        if (pos > SIZE - 50) flush();

        write_unsigned(uval);
    }

    static int calc_len(uint64_t x) {
        int i = ((63 - std::countl_zero(x)) * 3 + 3) / 10;
        if (x < tens[i])
            return i;
        else
            return i + 1;
    }

    template <class U,
              internal::is_unsigned_int_t<U>* = nullptr,
              std::enable_if_t<2 >= sizeof(U)>* = nullptr>
    void write_unsigned(U uval) {
        size_t len = calc_len(uval);
        pos += len;

        char* ptr = line.data() + pos;
        while (uval >= 100) {
            ptr -= 2;
            memcpy(ptr, small[uval % 100].data(), 2);
            uval /= 100;
        }
        if (uval >= 10) {
            memcpy(ptr - 2, small[uval].data(), 2);
        } else {
            *(ptr - 1) = char('0' + uval);
        }
    }

    template <class U,
              internal::is_unsigned_int_t<U>* = nullptr,
              std::enable_if_t<4 == sizeof(U)>* = nullptr>
    void write_unsigned(U uval) {
        std::array<char, 8> buf;
        memcpy(buf.data() + 6, small[uval % 100].data(), 2);
        memcpy(buf.data() + 4, small[uval / 100 % 100].data(), 2);
        memcpy(buf.data() + 2, small[uval / 10000 % 100].data(), 2);
        memcpy(buf.data() + 0, small[uval / 1000000 % 100].data(), 2);

        if (uval >= 100000000) {
            if (uval >= 1000000000) {
                memcpy(line.data() + pos, small[uval / 100000000 % 100].data(),
                       2);
                pos += 2;
            } else {
                line[pos] = char('0' + uval / 100000000);
                pos++;
            }
            memcpy(line.data() + pos, buf.data(), 8);
            pos += 8;
        } else {
            size_t len = calc_len(uval);
            memcpy(line.data() + pos, buf.data() + (8 - len), len);
            pos += len;
        }
    }

    template <class U,
              internal::is_unsigned_int_t<U>* = nullptr,
              std::enable_if_t<8 == sizeof(U)>* = nullptr>
    void write_unsigned(U uval) {
        size_t len = calc_len(uval);
        pos += len;

        char* ptr = line.data() + pos;
        while (uval >= 100) {
            ptr -= 2;
            memcpy(ptr, small[uval % 100].data(), 2);
            uval /= 100;
        }
        if (uval >= 10) {
            memcpy(ptr - 2, small[uval].data(), 2);
        } else {
            *(ptr - 1) = char('0' + uval);
        }
    }

    template <
        class U,
        std::enable_if_t<internal::is_unsigned_int128<U>::value>* = nullptr>
    void write_unsigned(U uval) {
        static std::array<char, 50> buf;
        size_t len = 0;
        while (uval > 0) {
            buf[len++] = char((uval % 10) + '0');
            uval /= 10;
        }
        std::reverse(buf.begin(), buf.begin() + len);
        memcpy(line.data() + pos, buf.data(), len);
        pos += len;
    }

    void write_single(const std::string& s) {
        for (char c : s) write_single(c);
    }
    void write_single(const char* s) {
        size_t len = strlen(s);
        for (size_t i = 0; i < len; i++) write_single(s[i]);
    }
    template <class T> void write_single(const std::vector<T>& val) {
        auto n = val.size();
        for (size_t i = 0; i < n; i++) {
            if (i) write_single(' ');
            write_single(val[i]);
        }
    }
};

inline std::array<std::array<char, 2>, 100> Printer::small = [] {
    std::array<std::array<char, 2>, 100> table;
    for (int i = 0; i <= 99; i++) {
        table[i][1] = char('0' + (i % 10));
        table[i][0] = char('0' + (i / 10 % 10));
    }
    return table;
}();
inline std::array<unsigned long long, 20> Printer::tens = [] {
    std::array<unsigned long long, 20> table;
    for (int i = 0; i < 20; i++) {
        table[i] = 1;
        for (int j = 0; j < i; j++) {
            table[i] *= 10;
        }
    }
    return table;
}();

}  // namespace yosupo

#include <cmath>
#include <limits>
#include <random>


namespace yosupo {

struct Xoshiro256StarStar {
  public:
    using result_type = u64;
    Xoshiro256StarStar() : Xoshiro256StarStar(0) {}
    explicit Xoshiro256StarStar(u64 seed) {
        // use splitmix64
        // Reference: http://xoshiro.di.unimi.it/splitmix64.c
        for (int i = 0; i < 4; i++) {
            u64 z = (seed += 0x9e3779b97f4a7c15);
            z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
            z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
            s[i] = z ^ (z >> 31);
        }
    }

    static constexpr result_type min() { return 0; }
    static constexpr result_type max() { return -1; }

    result_type operator()() {
        const u64 result_starstar = rotl(s[1] * 5, 7) * 9;

        const u64 t = s[1] << 17;

        s[2] ^= s[0];
        s[3] ^= s[1];
        s[1] ^= s[2];
        s[0] ^= s[3];

        s[2] ^= t;

        s[3] = rotl(s[3], 45);

        return result_starstar;
    }

  private:
    // Use xoshiro256**
    // Refereces: http://xoshiro.di.unimi.it/xoshiro256starstar.c
    static u64 rotl(const u64 x, int k) { return (x << k) | (x >> (64 - k)); }

    std::array<u64, 4> s;
};

// https://github.com/wangyi-fudan/wyhash
struct WYRand {
  public:
    using result_type = u64;
    explicit WYRand(u64 seed) : s(seed) {}

    static constexpr result_type min() { return 0; }
    static constexpr result_type max() { return -1; }

    result_type operator()() {
        s += 0x2d358dccaa6c78a5;
        auto x = (u128)s * (s ^ 0x8bb84b93962eacc9);
        return (u64)(x ^ (x >> 64));
    }

  private:
    uint64_t s;
};
using Random = WYRand;
inline Random get_random() { return Random(std::random_device()()); }

namespace internal {
inline Random global_gen = get_random();
}
inline Random& global_gen() { return internal::global_gen; }

template <class G>
concept random_64 = std::uniform_random_bit_generator<G> &&
                    std::same_as<u64, std::invoke_result_t<G&>> &&
                    G::min() == u64(0) && G::max() == u64(-1);

namespace internal {

// random choice from [0, upper]
template <random_64 G> u64 uniform_u64(u64 upper, G& gen) {
    if (upper == 0) return 0;
    u64 mask = (std::bit_floor(upper) << 1) - 1;
    while (true) {
        u64 r = gen() & mask;
        if (r <= upper) return r;
    }
}

// random choice from [0, upper], faster than uniform_u64
template <random_64 G> u64 random_u64(u64 upper, G& gen) {
    return (u64)(((u128)(upper) + 1) * gen() >> 64);
}

}  // namespace internal

template <class T, random_64 G> T uniform(T lower, T upper, G& gen) {
    return T(lower + internal::uniform_u64(u64(upper) - u64(lower), gen));
}
template <class T> T uniform(T lower, T upper) {
    return uniform(lower, upper, global_gen());
}

template <std::unsigned_integral T, random_64 G> T uniform(G& gen) {
    return T(gen());
}
template <std::signed_integral T, random_64 G> T uniform(G& gen) {
    return T(gen() + (u64)std::numeric_limits<T>::min());
}
template <class T, random_64 G>
    requires requires {
        { T::mod() } -> std::integral;
    }
T uniform(G& gen) {
    return T(uniform(0, T::mod() - 1, gen));
}
template <class T> T uniform() { return uniform<T>(global_gen()); }

template <class T, random_64 G> T random(T lower, T upper, G& gen) {
    return T(lower + internal::random_u64(u64(upper) - u64(lower), gen));
}
template <class T> T random(T lower, T upper) {
    return random(lower, upper, global_gen());
}

template <random_64 G> bool uniform_bool(G& gen) { return gen() & 1; }
inline bool uniform_bool() { return uniform_bool(global_gen()); }

// select 2 elements from [lower, uppper]
template <class T, random_64 G>
std::pair<T, T> uniform_pair(T lower, T upper, G& gen) {
    assert(upper - lower >= 1);
    T a, b;
    do {
        a = uniform(lower, upper, gen);
        b = uniform(lower, upper, gen);
    } while (a == b);
    if (a > b) std::swap(a, b);
    return {a, b};
}
template <class T> std::pair<T, T> uniform_pair(T lower, T upper) {
    return uniform_pair(lower, upper, global_gen());
}

// random 0.0 <= X < 1.0
template <class G> inline double random_01(G& gen) {
    constexpr double inv = 1.0 / ((double)(u64(1) << 63) * 2);
    return double(gen()) * inv;
}
inline double random_01() { return random_01(global_gen()); }

}  // namespace yosupo

#include <chrono>

namespace yosupo {

struct StopWatch {
    std::chrono::steady_clock::time_point begin;

    StopWatch() : begin(std::chrono::steady_clock::now()) {}

    int msecs() {
        auto now = std::chrono::steady_clock::now();
        return int(
            duration_cast<std::chrono::milliseconds>(now - begin).count());
    }
};

}  // namespace yosupo



#include <bitset>
#include <iostream>
#include <queue>


#include <functional>
#include <span>

namespace yosupo {

template <class T> bool chmin(T& a, const T& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T> bool chmax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <class T> T floor_div(T x, T y) {
    auto d = x / y;
    auto r = x % y;
    if (r == 0) return d;
    if ((r > 0) == (y > 0)) return d;
    return d - 1;
}
template <class T> T ceil_div(T x, T y) {
    auto d = x / y;
    auto r = x % y;
    if (r == 0) return d;
    if ((r > 0) == (y > 0)) return d + 1;
    return d;
}

template <std::ranges::input_range R>
std::vector<std::ranges::range_value_t<R>> to_vec(R&& r) {
    auto common = r | std::views::common;
    return std::vector(common.begin(), common.end());
}

template <class T, class Comp = std::equal_to<>>
void dedup(std::vector<T>& v, Comp comp = Comp{}) {
    auto it = std::ranges::unique(v, comp);
    v.erase(it.begin(), it.end());
}

template <size_t N, class T> std::span<T, N> subspan(std::span<T> a, int idx) {
    return a.subspan(idx).template first<N>();
}

inline auto rep(int l, int r) {
    if (l > r) return std::views::iota(l, l);
    return std::views::iota(l, r);
}

}  // namespace yosupo
using namespace yosupo;

using std::abs, std::pow, std::sqrt;
using std::array, std::vector, std::string, std::queue, std::deque;
using std::countl_zero, std::countl_one, std::countr_zero, std::countr_one;
using std::istream, std::ostream, std::cerr, std::endl;
using std::min, std::max, std::swap;
using std::pair, std::tuple, std::bitset;
using std::popcount;
using std::priority_queue, std::set, std::multiset, std::map;
using std::views::iota, std::views::reverse;

namespace ranges = std::ranges;
using ranges::sort, ranges::copy_n;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

#ifdef YOSUPO_LOCAL

struct PrettyOS {
    ostream& os;
    bool first;

    template <class T> auto operator<<(T&& x) {
        if (!first) os << ", ";
        first = false;
        os << yosupo::dump(x);
        return *this;
    }
};
template <class... T> void dbg0(T&&... t) {
    (PrettyOS{cerr, true} << ... << t);
}
#define dbg(...)                                            \
    do {                                                    \
        cerr << __LINE__ << " : " << #__VA_ARGS__ << " = "; \
        dbg0(__VA_ARGS__);                                  \
        cerr << endl;                                       \
    } while (false);
#else
#define dbg(...)
#endif




static inline Scanner sc = Scanner(stdin);

const int N = 30;
const Coord BOARD_SIZE = Coord(N, N);  // Board size
const int M = []() {                   // # of robots
    int m;
    sc.read(m, m);  // skip N
    return m;
}();
const auto [ROBOTS, GOALS] = []() {
    V<Coord> robots(M), goals(M);
    for (int i : iota(0, M)) {
        int r, c, gr, gc;
        sc.read(r, c, gr, gc);
        robots[i] = Coord(r, c);
        goals[i] = Coord(gr, gc);
    }
    return make_pair(robots, goals);
}();

using Wall = Array2D<bool, 2 * N - 1, 2 * N - 1>;

const Wall WALL = []() {
    Wall wall;
    for (int r : iota(0, N)) {
        string s;
        sc.read(s);
        for (int c : iota(0, N - 1)) {
            wall[{2 * r, 2 * c + 1}] = (s[c] == '1');
        }
    }
    for (int r : iota(0, N - 1)) {
        string s;
        sc.read(s);
        for (int c : iota(0, N)) {
            wall[{2 * r + 1, 2 * c}] = (s[c] == '1');
        }
    }
    return wall;
}();

// Check if a robot can move from coord in the given direction
static inline bool can_move(Coord coord, const Wall& wall, int dir) {
    Coord next_coord = coord.move4(dir);

    // Check bounds
    if (!BOARD_SIZE.contains(next_coord)) {
        return false;
    }

    // Check wall between coord and next_coord
    bool has_wall = false;
    if (dir == 0) {  // right
        has_wall = wall[{2 * coord.r(), 2 * coord.c() + 1}];
    } else if (dir == 1) {  // down
        has_wall = wall[{2 * coord.r() + 1, 2 * coord.c()}];
    } else if (dir == 2) {  // left
        has_wall = wall[{2 * next_coord.r(), 2 * next_coord.c() + 1}];
    } else {  // up
        has_wall = wall[{2 * next_coord.r() + 1, 2 * next_coord.c()}];
    }

    return !has_wall;
}

// Function to calculate distance to goal for each robot given a wall
// configuration
static inline V<Array2D<int, N, N>> calc_distances_to_goals(const Wall& wall) {
    V<Array2D<int, N, N>> dist_arrays(M);

    for (int robot_id = 0; robot_id < M; robot_id++) {
        Coord goal = GOALS[robot_id];
        Array2D<int, N, N>& dist = dist_arrays[robot_id];

        // Initialize distances to 10000 (unreachable)
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                dist[{r, c}] = 10000;
            }
        }

        // BFS from goal
        queue<Coord> q;
        q.push(goal);
        dist[goal] = 0;

        while (!q.empty()) {
            Coord cur = q.front();
            q.pop();

            for (int d = 0; d < 4; d++) {
                Coord nxt = cur.move4(d);

                // Check if move is valid using can_move function
                if (!can_move(cur, wall, d)) continue;

                // Check if already visited
                if (dist[nxt] != 10000) continue;

                // Valid move
                dist[nxt] = dist[cur] + 1;
                q.push(nxt);
            }
        }
    }

    return dist_arrays;
}


// Direction mapping: 0=right, 1=down, 2=left, 3=up
static inline Printer pr = Printer(stdout);

struct OP {
    bool is_group;  // true: group operation, false: single operation
    int id;         // group id or robot id
    int dir;        // 0: right, 1: down, 2: left, 3: up

    static OP single(int robot_id, int dir) { return {false, robot_id, dir}; }
    static OP group(int group_id, int dir) { return {true, group_id, dir}; }
};

using Group = VV<int>; 

struct Board {
    Wall wall;                           // additional wall
    Group group;                         // robot grouping information
    V<Array2D<int, N, N>> dist_to_goal;  // distance arrays for each robot

    Board() = default;

    Board(const Wall& wall, const VV<int>& group) : wall(wall), group(group) {
        // Validate that original walls are preserved
        for (auto r : iota(0, 2 * N - 1)) {
            for (auto c : iota(0, 2 * N - 1)) {
                if (WALL[{r, c}]) {
                    bool has_wall = wall[{r, c}];
                    assert(has_wall);
                }
            }
        }

        dist_to_goal = calc_distances_to_goals(wall);
    }
};

struct Answer {
    Board board;
    V<OP> ops;
};

static inline void print_answer(const Answer& answer) {
    // Print vertical walls
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N - 1; c++) {
            bool original_wall = WALL[{2 * r, 2 * c + 1}];
            bool additional_wall = answer.board.wall[{2 * r, 2 * c + 1}];
            bool has_wall = additional_wall || original_wall;

            // Assert: if original wall exists, we must output 1
            if (original_wall) {
                assert(has_wall && "Original wall position must output 1");
            }

            pr.write(has_wall ? '1' : '0');
        }
        pr.writeln();
    }

    // Print horizontal walls
    for (int r = 0; r < N - 1; r++) {
        for (int c = 0; c < N; c++) {
            bool original_wall = WALL[{2 * r + 1, 2 * c}];
            bool additional_wall = answer.board.wall[{2 * r + 1, 2 * c}];
            bool has_wall = additional_wall || original_wall;

            // Assert: if original wall exists, we must output 1
            if (original_wall) {
                assert(has_wall && "Original wall position must output 1");
            }

            pr.write(has_wall ? '1' : '0');
        }
        pr.writeln();
    }

    V<int> group_id(M);
    int K = int(answer.board.group.size());
    for (int i : iota(0, K)) {
        for (int j : answer.board.group[i]) {
            group_id[j] = i;
        }
    }
    for (int i = 0; i < M; i++) {
        if (i > 0) pr.write(' ');
        pr.write(group_id[i]);
    }
    pr.writeln();

    // Print operations
    for (const auto& op : answer.ops) {
        pr.write(op.is_group ? 'g' : 'i');
        pr.write(' ');
        if (op.is_group) {
            // Use compressed group ID for group operations
            pr.write(op.id);
        } else {
            // Robot ID remains the same
            pr.write(op.id);
        }
        pr.write(' ');

        // Convert direction: 0=right, 1=down, 2=left, 3=up
        const char dir_chars[] = {'R', 'D', 'L', 'U'};
        pr.write(dir_chars[op.dir]);
        pr.writeln();
    }
}

class State {
  public:
    V<Coord> positions;
    array<u32, N> occupied;

    State() : positions(M) {
        // Initialize occupied grid
        for (int r = 0; r < N; r++) {
            occupied[r] = 0;
        }
    }

    State(const V<Coord>& pos) : positions(pos) {
        // Initialize occupied grid
        for (int r = 0; r < N; r++) {
            occupied[r] = 0;
        }

        // Mark occupied positions
        for (const auto& coord : positions) {
            occupied[coord.r()] |= (1u << coord.c());
        }
    }

    // Move robot and update occupied grid
    void move_robot(int robot_id, Coord new_pos) {
        // Clear old position
        occupied[positions[robot_id].r()] &= ~(1u << positions[robot_id].c());
        // Set new position
        positions[robot_id] = new_pos;
        occupied[new_pos.r()] |= (1u << new_pos.c());
    }

    // Check if position is occupied
    bool is_occupied(Coord pos) const {
        return (occupied[pos.r()] >> pos.c()) & 1;
    }

    // Equality operator for comparison
    bool operator==(const State& other) const {
        return positions == other.positions;
    }
};

// Apply an operation to a state (modifies state in-place)
static inline void next_state(const Board& board, State& state, const OP& op) {
    if (op.is_group) {
        // Group operation: move all robots in the group sequentially
        // starting from the one furthest in the specified direction

        // Get robots in this group (much faster lookup)
        const V<int>& group_robots = board.group[op.id];

        // Sort robots by position based on movement direction
        V<int> sorted_robots =
            group_robots;   // Make a copy since group_robots is const
        if (op.dir == 0) {  // right - start from rightmost
            ranges::sort(sorted_robots, [&](int a, int b) {
                return state.positions[a].c() > state.positions[b].c();
            });
        } else if (op.dir == 1) {  // down - start from bottommost
            ranges::sort(sorted_robots, [&](int a, int b) {
                return state.positions[a].r() > state.positions[b].r();
            });
        } else if (op.dir == 2) {  // left - start from leftmost
            ranges::sort(sorted_robots, [&](int a, int b) {
                return state.positions[a].c() < state.positions[b].c();
            });
        } else {  // up - start from topmost
            ranges::sort(sorted_robots, [&](int a, int b) {
                return state.positions[a].r() < state.positions[b].r();
            });
        }

        // Move each robot in the sorted order
        for (int robot_id : sorted_robots) {
            // Check if move is valid using can_move function
            if (!can_move(state.positions[robot_id], board.wall, op.dir)) {
                continue;
            }

            Coord new_pos = state.positions[robot_id].move4(op.dir);

            // Check collision with other robots using faster occupied grid
            if (state.is_occupied(new_pos)) continue;

            // Valid move - update immediately so next robot sees the new
            // position
            state.move_robot(robot_id, new_pos);
        }
    } else {
        // Individual operation
        int robot_id = op.id;
        Coord new_pos = state.positions[robot_id].move4(op.dir);

        // Check if move is valid using can_move function
        if (can_move(state.positions[robot_id], board.wall, op.dir) &&
            !state.is_occupied(new_pos)) {
            state.move_robot(robot_id, new_pos);
        }
    }
}

static inline int calc_score(const Answer& answer) {
    // Simulate the answer and calculate score
    State positions(ROBOTS);

    for (const auto& op : answer.ops) {
        next_state(answer.board, positions, op);
    }

    // Calculate final score
    int T = static_cast<int>(answer.ops.size());
    int total_distance = 0;
    for (int i = 0; i < M; i++) {
        int dist = abs(positions.positions[i].r() - GOALS[i].r()) +
                   abs(positions.positions[i].c() - GOALS[i].c());
        total_distance += dist;
    }

    return T + 100 * total_distance;
}

const int TL = 2000;

Random gen = Random(12345);
StopWatch global_sw = StopWatch();

// BFS to find path from start to goal
V<int> bfs_find_path(Coord start,
                     Coord goal,
                     const State& state,
                     const Wall& wall) {
    if (start == goal) return {};

    static Array2D<Coord, N, N> parent;
    static Array2D<int, N, N> dir_taken;

    array<u32, N> visited = {};

    static V<Coord> st;
    st.clear();

    st.push_back(start);
    parent[start] = start;
    visited[start.r()] |= (1u << start.c());

    int pos = 0;
    while (pos < int(st.size())) {
        Coord cur = st[pos++];

        for (int d = 0; d < 4; d++) {
            Coord nxt = cur.move4(d);

            // Check bounds
            if (!BOARD_SIZE.contains(nxt)) {
                continue;
            }

            // Check if move is valid using can_move function
            if (!can_move(cur, wall, d)) continue;
            // Occupied
            if (state.is_occupied(nxt)) continue;

            // If not visited
            if (visited[nxt.r()] & (1u << nxt.c())) continue;
            visited[nxt.r()] |= (1u << nxt.c());

            parent[nxt] = cur;
            dir_taken[nxt] = d;
            st.push_back(nxt);

            if (nxt == goal) {
                // Reconstruct path
                V<int> path;
                Coord p = goal;
                while (p != start) {
                    path.push_back(dir_taken[p]);
                    p = parent[p];
                }
                ranges::reverse(path);
                return path;
            }
        }
    }

    return {};  // No path found
}

// Greedy strategy: find reachable robots and move them to goals
V<OP> greedy(const Board& board, State state) {
    V<OP> ops;

    while (true) {
        bool moved = false;

        // Try to move each robot to its goal
        for (int i = 0; i < M; i++) {
            if (state.positions[i] == GOALS[i]) continue;

            // Try to find path to goal
            V<int> path =
                bfs_find_path(state.positions[i], GOALS[i], state, board.wall);
            if (int(path.size()) !=
                board.dist_to_goal[i][{state.positions[i]}]) {
                // If path length doesn't match expected distance, skip
                continue;
            }
            if (!path.empty()) {
                // Move robot along the path
                for (int dir : path) {
                    OP op = OP::single(i, dir);
                    ops.push_back(op);

                    // Update position using next_state
                    next_state(board, state, op);
                }

                assert(state.positions[i] == GOALS[i]);
                moved = true;
                break;
            }
        }

        // If no robot could move, we're stuck
        if (moved) continue;

        // Try to move each robot to its goal
        for (int i = 0; i < M; i++) {
            if (state.positions[i] == GOALS[i]) continue;

            // Try to find path to goal
            V<int> path =
                bfs_find_path(state.positions[i], GOALS[i], state, board.wall);
            if (!path.empty()) {
                // Move robot along the path
                for (int dir : path) {
                    OP op = OP::single(i, dir);
                    ops.push_back(op);

                    // Update position using next_state
                    next_state(board, state, op);
                }

                // If we reached the goal, break
                assert(state.positions[i] == GOALS[i]);
                moved = true;
                break;
            }
        }

        if (moved) continue;
        // stucked
        break;
    }
    return ops;
}

// Evaluation function: sum of Manhattan distances to goals
int evaluate_state(const Board& board, const State& state) {
    int total_distance = 0;
    for (int i = 0; i < M; i++) {
        total_distance += board.dist_to_goal[i][{state.positions[i]}];
    }
    return total_distance;
}

// Calculate score difference without copying state
// Returns the improvement (positive means better)
int calculate_group_move_delta(const Board& board,
                               const State& state,
                               int gid,
                               int dir,
                               const V<int>& group_robots) {
    int delta = 0;

    auto temp_occupied_mask = state.occupied;

    // Calculate delta for each robot that can move
    for (int robot_id : group_robots) {
        // 現在の位置は元のstateから取得
        Coord cur_pos = state.positions[robot_id];
        Coord new_pos = cur_pos.move4(dir);

        // temp_state.is_occupied(new_pos) の代わりに、
        // コピーしたビットマスクで占有判定を行う
        bool is_new_pos_occupied =
            (temp_occupied_mask[new_pos.r()] >> new_pos.c()) & 1u;

        if (can_move(cur_pos, board.wall, dir) &&
            BOARD_SIZE.contains(new_pos) && !is_new_pos_occupied) {
            // This robot can move
            delta += board.dist_to_goal[robot_id][{cur_pos}] -
                     board.dist_to_goal[robot_id][{new_pos}];

            // Update temp mask for next robot check
            // temp_state.move_robot(robot_id, new_pos) の代わりに、
            // ビットマスクを直接操作する
            temp_occupied_mask[cur_pos.r()] &= ~(1u << cur_pos.c());
            temp_occupied_mask[new_pos.r()] |= (1u << new_pos.c());
        }
    }

    return delta;
}

int calculate_move_delta(const Board& board, const State& state, OP op) {
    int delta = 0;

    if (!op.is_group) {
        // Single robot move (変更なし)
        int robot_id = op.id;
        Coord cur_pos = state.positions[robot_id];
        Coord new_pos = cur_pos.move4(op.dir);

        // Check if move is valid
        if (!can_move(cur_pos, board.wall, op.dir) ||
            !BOARD_SIZE.contains(new_pos) || state.is_occupied(new_pos)) {
            return 0;  // No improvement if move is invalid
        }

        // Calculate distance change
        delta = board.dist_to_goal[robot_id][{cur_pos}] -
                board.dist_to_goal[robot_id][{new_pos}];
    } else {
        // Group move
        V<int> group_robots = board.group[op.id];  // Make a copy for sorting

        // Sort robots based on movement direction (変更なし)
        if (op.dir == 0) {  // Right
            sort(group_robots.begin(), group_robots.end(), [&](int a, int b) {
                return state.positions[a].c() > state.positions[b].c();
            });
        } else if (op.dir == 1) {  // Down
            sort(group_robots.begin(), group_robots.end(), [&](int a, int b) {
                return state.positions[a].r() > state.positions[b].r();
            });
        } else if (op.dir == 2) {  // Left
            sort(group_robots.begin(), group_robots.end(), [&](int a, int b) {
                return state.positions[a].c() < state.positions[b].c();
            });
        } else {  // Up
            sort(group_robots.begin(), group_robots.end(), [&](int a, int b) {
                return state.positions[a].r() < state.positions[b].r();
            });
        }

        // --- ここからが最適化のポイント ---
        // State全体ではなく、occupied_maskのみをコピーする
        auto temp_occupied_mask = state.occupied;

        // Calculate delta for each robot that can move
        for (int robot_id : group_robots) {
            // 現在の位置は元のstateから取得
            Coord cur_pos = state.positions[robot_id];
            Coord new_pos = cur_pos.move4(op.dir);

            // temp_state.is_occupied(new_pos) の代わりに、
            // コピーしたビットマスクで占有判定を行う
            bool is_new_pos_occupied =
                (temp_occupied_mask[new_pos.r()] >> new_pos.c()) & 1u;

            if (can_move(cur_pos, board.wall, op.dir) &&
                BOARD_SIZE.contains(new_pos) && !is_new_pos_occupied) {
                // This robot can move
                delta += board.dist_to_goal[robot_id][{cur_pos}] -
                         board.dist_to_goal[robot_id][{new_pos}];

                // Update temp mask for next robot check
                // temp_state.move_robot(robot_id, new_pos) の代わりに、
                // ビットマスクを直接操作する
                temp_occupied_mask[cur_pos.r()] &= ~(1u << cur_pos.c());
                temp_occupied_mask[new_pos.r()] |= (1u << new_pos.c());
            }
        }
    }

    return delta;
}
/*
// Calculate score difference without copying state
// Returns the improvement (positive means better)
int calculate_move_delta(const Board& board, const State& state, OP op) {
    int delta = 0;

    if (!op.is_group) {
        // Single robot move
        int robot_id = op.id;
        Coord cur_pos = state.positions[robot_id];
        Coord new_pos = cur_pos.move4(op.dir);

        // Check if move is valid
        if (!can_move(cur_pos, board.wall, op.dir) ||
            !BOARD_SIZE.contains(new_pos) ||
            state.is_occupied(new_pos)) {
            return 0; // No improvement if move is invalid
        }

        // Calculate distance change
        delta = board.dist_to_goal[robot_id][{cur_pos}] -
                board.dist_to_goal[robot_id][{new_pos}];
    } else {
        // Group move
        V<int> group_robots = board.group[op.id];  // Make a copy for sorting

        // Sort robots based on movement direction
        if (op.dir == 0) { // Right
            sort(group_robots.begin(), group_robots.end(), [&](int a, int b) {
                return state.positions[a].c() > state.positions[b].c();
            });
        } else if (op.dir == 1) { // Down
            sort(group_robots.begin(), group_robots.end(), [&](int a, int b) {
                return state.positions[a].r() > state.positions[b].r();
            });
        } else if (op.dir == 2) { // Left
            sort(group_robots.begin(), group_robots.end(), [&](int a, int b) {
                return state.positions[a].c() < state.positions[b].c();
            });
        } else { // Up
            sort(group_robots.begin(), group_robots.end(), [&](int a, int b) {
                return state.positions[a].r() < state.positions[b].r();
            });
        }

        // Track which positions will be occupied after moves
        State temp_state = state;

        // Calculate delta for each robot that can move
        for (int robot_id : group_robots) {
            Coord cur_pos = temp_state.positions[robot_id];
            Coord new_pos = cur_pos.move4(op.dir);

            if (can_move(cur_pos, board.wall, op.dir) &&
                BOARD_SIZE.contains(new_pos) &&
                !temp_state.is_occupied(new_pos)) {
                // This robot can move
                delta += board.dist_to_goal[robot_id][{cur_pos}] -
                         board.dist_to_goal[robot_id][{new_pos}];

                // Update temp state for next robot check
                temp_state.move_robot(robot_id, new_pos);
            }
        }
    }

    return delta;
}*/

struct OPBlock {
    int gid;  // group ID
    int dir;
};

struct ANNState {
    Board board;
    V<OPBlock> blocks;
};

int score_ann_state(const ANNState& ann_state) {
    State state(ROBOTS);
    int current_eval = evaluate_state(ann_state.board, state);

    int ops_count = 0;

    // Execute op blocks
    for (const auto& block : ann_state.blocks) {
        // Group move
        V<int> group_robots =
            ann_state.board.group[block.gid];  // Make a copy for sorting

        // Sort robots based on movement direction (変更なし)
        if (block.dir == 0) {  // Right
            sort(group_robots.begin(), group_robots.end(), [&](int a, int b) {
                return state.positions[a].c() > state.positions[b].c();
            });
        } else if (block.dir == 1) {  // Down
            sort(group_robots.begin(), group_robots.end(), [&](int a, int b) {
                return state.positions[a].r() > state.positions[b].r();
            });
        } else if (block.dir == 2) {  // Left
            sort(group_robots.begin(), group_robots.end(), [&](int a, int b) {
                return state.positions[a].c() < state.positions[b].c();
            });
        } else {  // Up
            sort(group_robots.begin(), group_robots.end(), [&](int a, int b) {
                return state.positions[a].r() < state.positions[b].r();
            });
        }

        while (true) {
            // Calculate improvement without state copy

            int improvement = calculate_group_move_delta(
                ann_state.board, state, block.gid, block.dir, group_robots);

            if (improvement >= 1) {
                OP candidate_op = OP::group(block.gid, block.dir);
                next_state(ann_state.board, state, candidate_op);
                current_eval -= improvement;
                ops_count++;
            } else {
                break;
            }
        }
    }

    return ops_count + current_eval;
}

ANNState good_ann_state(int tl) {
    StopWatch sw = StopWatch();

    // Start with all robots in separate groups (each robot is its own group)
    ANNState cur_state = [&]() {
        VV<int> cur_groups;
        for (int i = 0; i < M; i++) {
            cur_groups.push_back({i});
        }
        V<OPBlock> cur_blocks;
        for (int i : iota(0, M)) {
            for (int d : iota(0, 4)) {
                cur_blocks.push_back({i, d});
            }
        }
        return ANNState(Board(WALL, cur_groups), cur_blocks);
    }();
    int cur_score = score_ann_state(cur_state);

    int try_count = 0;
    int best_score = cur_score;
    ANNState best_state = cur_state;

    dbg(cur_score);

    const double START_TEMP = 8.0;
    const double END_TEMP = 0.01;

    // Simulated annealing
    while (true) {
        // remove empty vectors from cur_state
        for (auto& g : cur_state.board.group) {
            assert(!g.empty());
        }

        int msecs = sw.msecs();
        if (msecs > tl) {
            break;
        }
        double t = (double)msecs / tl;
        double temperature = std::lerp(START_TEMP, END_TEMP, t);

        try_count++;
        if (try_count % 100 == 0) {
            dbg(try_count, temperature, best_score, cur_score);
        }

        int K = int(cur_state.board.group.size());

        // Randomly decide transition type
        int type = random(0, 99, gen);

        auto try_apply = [&]() {
            int new_score = score_ann_state(cur_state);
            // Simulated annealing acceptance
            int delta = new_score - cur_score;
            if (delta <= 0 || random_01(gen) < exp(-delta / temperature)) {
                cur_score = new_score;

                // Update best if we found a better solution
                if (new_score < best_score) {
                    best_score = new_score;
                    best_state = cur_state;
                    dbg(best_score);
                }
                return true;
            } else {
                return false;
            }
        };

        if (type < 20) {
            if (K < 2) {
                continue;  // Cannot merge if only one group
            }
            // Group transition: move element

            // Pick two different groups
            int from_group =
                random(0, (int)cur_state.board.group.size() - 1, gen);
            int to_group =
                random(0, (int)cur_state.board.group.size() - 1, gen);
            if (from_group == to_group) continue;  // No move needed

            auto pre_group = cur_state.board.group;
            auto pre_blocks = cur_state.blocks;

            // Move one element from from_group to to_group
            int idx = random(
                0, (int)cur_state.board.group[from_group].size() - 1, gen);
            int robot_id = cur_state.board.group[from_group][idx];

            cur_state.board.group[from_group].erase(
                cur_state.board.group[from_group].begin() + idx);
            cur_state.board.group[to_group].push_back(robot_id);

            // If from_group becomes empty, remove it and adjust OPBlock gids
            if (cur_state.board.group[from_group].empty()) {
                cur_state.board.group.erase(cur_state.board.group.begin() +
                                            from_group);

                // Adjust all OPBlock gids
                for (auto& block : cur_state.blocks) {
                    if (block.gid > from_group) {
                        block.gid--;
                    } else if (block.gid == from_group) {
                        // Mark for deletion
                        block.gid = -1;
                    }
                }

                // Remove blocks with invalid gid
                std::erase_if(cur_state.blocks, [](const OPBlock& block) {
                    return block.gid < 0;
                });
            }

            if (!try_apply()) {
                // Revert if not accepted
                cur_state.board.group = pre_group;
                cur_state.blocks = pre_blocks;
            }
        } else if (type < 40) {
            if (K == 1) continue;

            // Group transition: swap elements

            // Pick two different groups
            int group1 = random(0, (int)cur_state.board.group.size() - 1, gen);
            int group2 = random(0, (int)cur_state.board.group.size() - 1, gen);
            if (group1 == group2) continue;  // No swap needed
            auto pre_group = cur_state.board.group;

            // Swap one element from each group
            int idx1 =
                random(0, (int)cur_state.board.group[group1].size() - 1, gen);
            int idx2 =
                random(0, (int)cur_state.board.group[group2].size() - 1, gen);

            swap(cur_state.board.group[group1][idx1],
                 cur_state.board.group[group2][idx2]);

            if (!try_apply()) {
                // Revert if not accepted
                cur_state.board.group = pre_group;
            }
        } else if (type < 55) {
            if (K == 0) continue;

            int group_idx = random(0, K - 1, gen);
            if (cur_state.board.group[group_idx].size() <= 1) {
                // If the group has only one element, skip
                continue;
            }

            auto pre_group = cur_state.board.group;
            auto pre_blocks = cur_state.blocks;

            int elem_idx = random(
                0, (int)cur_state.board.group[group_idx].size() - 1, gen);

            int robot_id = cur_state.board.group[group_idx][elem_idx];
            cur_state.board.group[group_idx].erase(
                cur_state.board.group[group_idx].begin() + elem_idx);
            cur_state.board.group.push_back({robot_id});

            if (!try_apply()) {
                // Revert if not accepted
                cur_state.board.group = pre_group;
                cur_state.blocks = pre_blocks;
            }
        } else if (type < 70) {
            auto pre_blocks = cur_state.blocks;

            // Op block transition: add op block

            // Pick random group and direction
            int gid = random(0, (int)K - 1, gen);
            int dir = random(0, 3, gen);

            // Insert at random position
            int pos = random(0, (int)cur_state.blocks.size(), gen);
            cur_state.blocks.insert(cur_state.blocks.begin() + pos, {gid, dir});

            if (!try_apply()) {
                // Revert if not accepted
                cur_state.blocks = pre_blocks;
            }
        } else if (type < 80) {  // 遷移の確率を10%割り当てる
            if (cur_state.blocks.size() < 2) continue;
            auto pre_blocks = cur_state.blocks;

            // OPブロックリストからランダムに2つ選んで入れ替える
            int pos1 = random(0, (int)cur_state.blocks.size() - 2, gen);
            int pos2 = random(pos1 + 1, min((int)cur_state.blocks.size() - 1, pos1 + 3), gen);
            if (pos1 == pos2) continue;

            swap(cur_state.blocks[pos1], cur_state.blocks[pos2]);

            if (!try_apply()) {
                // 悪化したら元に戻す
                cur_state.blocks = pre_blocks;
            }
        } else {
            if (cur_state.blocks.empty()) continue;
            auto pre_blocks = cur_state.blocks;

            // Op block transition: remove op block

            // Remove random op block
            int pos = random(0, (int)cur_state.blocks.size() - 1, gen);
            cur_state.blocks.erase(cur_state.blocks.begin() + pos);

            if (!try_apply()) {
                // Revert if not accepted
                cur_state.blocks = pre_blocks;
            }
        }
    }
    dbg(best_score, global_sw.msecs(), try_count);

    return best_state;
}

ANNState good_board(int tl) {
    ANNState ann_state = good_ann_state(tl);
    return ann_state;
}

V<OP> solve_board(const ANNState& ann_state) {
    V<OP> ops;
    State state(ROBOTS);

    // Execute op blocks according to the ANNState
    {
        int current_eval = evaluate_state(ann_state.board, state);

        // Execute op blocks
        for (const auto& block : ann_state.blocks) {
            // Group move
            V<int> group_robots =
                ann_state.board.group[block.gid];  // Make a copy for sorting

            // Sort robots based on movement direction (変更なし)
            if (block.dir == 0) {  // Right
                sort(group_robots.begin(), group_robots.end(),
                     [&](int a, int b) {
                         return state.positions[a].c() > state.positions[b].c();
                     });
            } else if (block.dir == 1) {  // Down
                sort(group_robots.begin(), group_robots.end(),
                     [&](int a, int b) {
                         return state.positions[a].r() > state.positions[b].r();
                     });
            } else if (block.dir == 2) {  // Left
                sort(group_robots.begin(), group_robots.end(),
                     [&](int a, int b) {
                         return state.positions[a].c() < state.positions[b].c();
                     });
            } else {  // Up
                sort(group_robots.begin(), group_robots.end(),
                     [&](int a, int b) {
                         return state.positions[a].r() < state.positions[b].r();
                     });
            }

            while (true) {
                // Calculate improvement without state copy

                int improvement = calculate_group_move_delta(
                    ann_state.board, state, block.gid, block.dir, group_robots);

                if (improvement >= 1) {
                    OP candidate_op = OP::group(block.gid, block.dir);
                    next_state(ann_state.board, state, candidate_op);
                    current_eval -= improvement;
                    ops.push_back(candidate_op);
                } else {
                    break;
                }
            }
        }
    }
    // for (const auto& block : ann_state.blocks) {
    //     OP candidate_op = OP::group(block.gid, block.dir);

    //     // Execute this operation multiple times while it improves the state
    //     while (true) {
    //         // Calculate improvement without state copy
    //         int improvement =
    //             calculate_move_delta(ann_state.board, state, candidate_op);

    //         if (improvement >= 2) {
    //             ops.push_back(candidate_op);
    //             next_state(ann_state.board, state, candidate_op);
    //         } else {
    //             break;
    //         }
    //     }
    // }

    int current_eval = evaluate_state(ann_state.board, state);
    while (true) {
        bool applied = false;
        // Try all possible group moves
        for (int g : iota(0, (int)ann_state.board.group.size())) {
            for (int dir = 0; dir < 4; dir++) {
                while (true) {
                    OP candidate_op = OP::group(g, dir);
                    State test_state = state;
                    next_state(ann_state.board, test_state, candidate_op);

                    int new_eval = evaluate_state(ann_state.board, test_state);
                    int improvement = current_eval - new_eval;

                    if (improvement >= 2 && new_eval < current_eval) {
                        next_state(ann_state.board, state, candidate_op);
                        current_eval = new_eval;
                        ops.push_back(candidate_op);
                        applied = true;
                    } else {
                        break;
                    }
                }
            }
        }

        if (!applied) break;
        break;
    }

    // After executing all op blocks, run greedy to complete the solution
    V<OP> greedy_ops = greedy(ann_state.board, state);
    for (const auto& op : greedy_ops) {
        ops.push_back(op);
    }

    return ops;
}

int main() {
    ANNState ann_state = good_board(int(TL * 0.9));
    V<OP> ops = solve_board(ann_state);
    Answer answer{ann_state.board, ops};
    dbg(calc_score(answer));
    print_answer(answer);

    return 0;
}

Submission Info

Compile Error

./Main.cpp:1620:36: warning: unused parameter 'gid' [-Wunused-parameter]
                               int gid,
                                   ^
./Main.cpp:2093:13: warning: variable 'current_eval' set but not used [-Wunused-but-set-variable]
        int current_eval = evaluate_state(ann_state.board, state);
            ^
./Main.cpp:1452:19: warning: unused function 'calc_score' [-Wunused-function]
static inline int calc_score(const Answer& answer) {
                  ^
3 warnings generated.

Judge Result