#include "testlib.h"
//
#include <bits/stdc++.h>

#include "limits.h"

namespace solve_wrong {

template <typename T>
void chmax(T& val, const T& upd) { val = std::max(val, upd); }

int solve_n1(std::vector<int64_t> a, std::vector<int64_t> b) {
    int n = a.size();
    std::vector<int64_t> prf_a(n + 1), prf_b(n + 1);
    for (int i = 0; i < n; i++) {
        prf_a[i + 1] = prf_a[i] + a[i];
        prf_b[i + 1] = prf_b[i] + b[i];
    }

    auto get = [&](auto& vec, int ind) -> int64_t {
        if (ind < 0) {
            return 0;
        }
        if (vec.size() <= ind) {
            return vec.back();
        }
        return vec[ind];
    };

    auto check = [&](int d) {
        int64_t max = -1e18;
        for (int i = 0; i <= n; i++) {
            max = std::max(max, -get(prf_a, i) + get(prf_b, i - d));
            int64_t val = get(prf_a, i) - get(prf_b, i + d);
            if (max + val > 0) {
                return false;
            }
        }
        return true;
    };

    int beg = -1, end = n;
    while (beg + 1 < end) {
        int mid = (beg + end) / 2;
        (check(mid) ? end : beg) = mid;
    }

    return end;
}

template <int n>
constexpr auto gen_masks() {
    if constexpr (n == 1) {
        std::array<std::array<int, 1>, 1> res;
        res[0][0] = 0;
        return res;
    } else {
        auto mk = gen_masks<n - 1>();
        std::array<std::array<int, n>, mk.size() * 3> res;
        for (int i = 0; i < mk.size(); i++) {
            for (int k = -1; k <= 1; k++) {
                std::copy(mk[i].begin(), mk[i].end(), res[3 * i + (k + 1)].begin());
                res[3 * i + (k + 1)].back() = mk[i].back() + k;
            }
        }
        for (auto& vec : res) {
            int min = *std::min_element(vec.begin(), vec.end());
            std::for_each(vec.begin(), vec.end(), [&](int& x) { x -= min; });
        }
        return res;
    }
}

template <int n>
int solve(int m, std::vector<int64_t> a, std::vector<int64_t> b) {
    std::vector<int64_t> prf_b(n * m + 1);
    for (int i = 0; i < n * m; i++) {
        prf_b[i + 1] = prf_b[i] + b[i];
    }
    std::vector<int64_t> prf_B(m + 1);
    for (int i = 0; i < m; i++) {
        prf_B[i + 1] = prf_B[i];
        for (int j = 0; j < n; j++) {
            prf_B[i + 1] += b[j * m + i];
        }
    }

    constexpr auto masks = gen_masks<n>();
    constexpr size_t k = masks.size();

    std::vector<int> min_dist(k * k);
    for (int mk1 = 0; mk1 < k; mk1++) {
        for (int mk2 = 0; mk2 < k; mk2++) {
            int max = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    max = std::max(max, std::abs(masks[mk1][i] - masks[mk2][j]) - std::abs(i - j));
                }
            }
            min_dist[mk1 * k + mk2] = max;
        }
    }

    auto check = [&](int D) -> bool {
        auto get1 = [&](int l, int r) -> int64_t {
            return prf_B[r] - prf_B[l];
        };
        auto get2 = [&](int j, int l, int r) -> int64_t {
            return prf_b[j * m + r] - prf_b[j * m + l];
        };

        std::vector<std::array<int64_t, k>> dp(m), dlt_r(m);

        for (int i = 0; i < m; i++) {
            for (int mk = 0; mk < k; mk++) {
                int64_t val = 0, dlt = 0;
                for (int j = 0; j < n; j++) {
                    val += a[j * m + i] * (masks[mk][j] == 0);
                    val -= get2(j, std::clamp(i - (D - masks[mk][j]), 0, i + 1), i + 1);
                    dlt -= get2(j, i + 1, std::clamp(i + (D - masks[mk][j]) + 1, i + 1, m));
                }
                dp[i][mk] = val, dlt_r[i][mk] = dlt;
            }
        }

        auto meow = [&](int i, int i2) {
            for (int mk = 0; mk < k; mk++) {
                int64_t val = dp[i][mk];
                for (int mk2 = 0; mk2 < k; mk2++) {
                    if (i2 - i < min_dist[mk * k + mk2]) {
                        continue;
                    }
                    int64_t dlt = 0;
                    for (int j = 0; j < n; j++) {
                        int l = std::clamp(i + (D - masks[mk][j]) + 1, i + 1, i2 + 1);
                        int r = std::clamp(i2 - (D - masks[mk2][j]), l, i2 + 1);
                        dlt += a[j * m + i2] * (masks[mk2][j] == 0);
                        dlt -= get2(j, i + 1, l) + get2(j, r, i2 + 1);
                    }
                    chmax(dp[i2][mk2], val + dlt);
                }
            }
        };

        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j <= i + n && j < m; j++) {
                meow(i, j);
            }
            // for (int j = std::max(i + 1, i + 2 * D - 2 * (n - 1)); j <= i + 2 * D && j < m; j++) {
            //     meow(i, j);
            // }
        }

        for (int i = 0; i < m; i++) {
            for (int mk = 0; mk < k; mk++) {
                if (int64_t d = dp[i][mk] + dlt_r[i][mk]; d > 0) {
                    return false;
                }
            }
        }
        return true;
    };

    std::vector<int64_t> A(m), B(m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            A[j] += a[i * m + j];
            B[j] += b[i * m + j];
        }
    }

    int x = solve_n1(A, B);

    int beg = x - 1, end = x + (n - 1);
    while (beg + 1 < end) {
        int mid = (beg + end) / 2;
        (check(mid) ? end : beg) = mid;
    }
    return end;
}

template <size_t scale, size_t... S, typename Functor>
__attribute__((always_inline)) constexpr void static_foreach_seq(Functor function, std::index_sequence<S...>) {
    ((function(std::integral_constant<size_t, S * scale>())), ...);
}

template <size_t Size, size_t scale = 1, typename Functor>
__attribute__((always_inline)) constexpr void static_for(Functor functor) {
    return static_foreach_seq<scale>(functor, std::make_index_sequence<Size>());
}

int solve(int n, int m, std::vector<int> a, std::vector<int> b) {
    std::vector<int64_t> A(a.begin(), a.end()), B(b.begin(), b.end());
    int res = -1;
    static_for<5>([&](auto i) {
        if (i + 1 == n) {
            int ans1 = solve<i + 1>(m, A, B);
            int ans2 = solve<i + 1>(m, B, A);
            int ans = std::max(ans1, ans2);
            res = ans;
        }
    });
    return res;
}

};  // namespace solve_wrong

namespace solve {

template <typename T>
void chmax(T& val, const T& upd) { val = std::max(val, upd); }

int solve_n1(std::vector<int64_t> a, std::vector<int64_t> b) {
    int n = a.size();
    std::vector<int64_t> prf_a(n + 1), prf_b(n + 1);
    for (int i = 0; i < n; i++) {
        prf_a[i + 1] = prf_a[i] + a[i];
        prf_b[i + 1] = prf_b[i] + b[i];
    }

    auto get = [&](auto& vec, int ind) -> int64_t {
        if (ind < 0) {
            return 0;
        }
        if (vec.size() <= ind) {
            return vec.back();
        }
        return vec[ind];
    };

    auto check = [&](int d) {
        int64_t max = -1e18;
        for (int i = 0; i <= n; i++) {
            max = std::max(max, -get(prf_a, i) + get(prf_b, i - d));
            int64_t val = get(prf_a, i) - get(prf_b, i + d);
            if (max + val > 0) {
                return false;
            }
        }
        return true;
    };

    int beg = -1, end = n;
    while (beg + 1 < end) {
        int mid = (beg + end) / 2;
        (check(mid) ? end : beg) = mid;
    }

    return end;
}

template <int n>
constexpr auto gen_masks() {
    if constexpr (n == 1) {
        std::array<std::array<int, 1>, 1> res;
        res[0][0] = 0;
        return res;
    } else {
        auto mk = gen_masks<n - 1>();
        std::array<std::array<int, n>, mk.size() * 3> res;
        for (int i = 0; i < mk.size(); i++) {
            for (int k = -1; k <= 1; k++) {
                std::copy(mk[i].begin(), mk[i].end(), res[3 * i + (k + 1)].begin());
                res[3 * i + (k + 1)].back() = mk[i].back() + k;
            }
        }
        for (auto& vec : res) {
            int min = *std::min_element(vec.begin(), vec.end());
            std::for_each(vec.begin(), vec.end(), [&](int& x) { x -= min; });
        }
        return res;
    }
}

template <int n>
int solve(int m, std::vector<int64_t> a, std::vector<int64_t> b) {
    std::vector<int64_t> prf_b(n * m + 1);
    for (int i = 0; i < n * m; i++) {
        prf_b[i + 1] = prf_b[i] + b[i];
    }
    std::vector<int64_t> prf_B(m + 1);
    for (int i = 0; i < m; i++) {
        prf_B[i + 1] = prf_B[i];
        for (int j = 0; j < n; j++) {
            prf_B[i + 1] += b[j * m + i];
        }
    }

    constexpr auto masks = gen_masks<n>();
    constexpr size_t k = masks.size();

    std::vector<int> min_dist(k * k);
    for (int mk1 = 0; mk1 < k; mk1++) {
        for (int mk2 = 0; mk2 < k; mk2++) {
            int max = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    max = std::max(max, std::abs(masks[mk1][i] - masks[mk2][j]) - std::abs(i - j));
                }
            }
            min_dist[mk1 * k + mk2] = max;
        }
    }

    auto check = [&](int D) -> bool {
        auto get1 = [&](int l, int r) -> int64_t {
            return prf_B[r] - prf_B[l];
        };
        auto get2 = [&](int j, int l, int r) -> int64_t {
            return prf_b[j * m + r] - prf_b[j * m + l];
        };

        std::vector<std::array<int64_t, k>> dp(m), dlt_r(m);

        for (int i = 0; i < m; i++) {
            for (int mk = 0; mk < k; mk++) {
                int64_t val = 0, dlt = 0;
                for (int j = 0; j < n; j++) {
                    val += a[j * m + i] * (masks[mk][j] == 0);
                    val -= get2(j, std::clamp(i - (D - masks[mk][j]), 0, i + 1), i + 1);
                    dlt -= get2(j, i + 1, std::clamp(i + (D - masks[mk][j]) + 1, i + 1, m));
                }
                dp[i][mk] = val, dlt_r[i][mk] = dlt;
            }
        }

        auto meow = [&](int i, int i2) {
            for (int mk = 0; mk < k; mk++) {
                int64_t val = dp[i][mk];
                for (int mk2 = 0; mk2 < k; mk2++) {
                    if (i2 - i < min_dist[mk * k + mk2]) {
                        continue;
                    }
                    int64_t dlt = 0;
                    for (int j = 0; j < n; j++) {
                        int l = std::clamp(i + (D - masks[mk][j]) + 1, i + 1, i2 + 1);
                        int r = std::clamp(i2 - (D - masks[mk2][j]), l, i2 + 1);
                        dlt += a[j * m + i2] * (masks[mk2][j] == 0);
                        dlt -= get2(j, i + 1, l) + get2(j, r, i2 + 1);
                    }
                    chmax(dp[i2][mk2], val + dlt);
                }
            }
        };

        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j <= i + n && j < m; j++) {
                meow(i, j);
            }
            for (int j = std::max(i + 1, i + 2 * D - 2 * (n - 1)); j <= i + 2 * D && j < m; j++) {
                meow(i, j);
            }
        }

        for (int i = 0; i < m; i++) {
            for (int mk = 0; mk < k; mk++) {
                if (int64_t d = dp[i][mk] + dlt_r[i][mk]; d > 0) {
                    return false;
                }
            }
        }
        return true;
    };

    std::vector<int64_t> A(m), B(m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            A[j] += a[i * m + j];
            B[j] += b[i * m + j];
        }
    }

    int x = solve_n1(A, B);

    int beg = x - 1, end = x + (n - 1);
    while (beg + 1 < end) {
        int mid = (beg + end) / 2;
        (check(mid) ? end : beg) = mid;
    }
    return end;
}

template <size_t scale, size_t... S, typename Functor>
__attribute__((always_inline)) constexpr void static_foreach_seq(Functor function, std::index_sequence<S...>) {
    ((function(std::integral_constant<size_t, S * scale>())), ...);
}

template <size_t Size, size_t scale = 1, typename Functor>
__attribute__((always_inline)) constexpr void static_for(Functor functor) {
    return static_foreach_seq<scale>(functor, std::make_index_sequence<Size>());
}

int solve(int n, int m, std::vector<int> a, std::vector<int> b) {
    std::vector<int64_t> A(a.begin(), a.end()), B(b.begin(), b.end());
    int res = -1;
    static_for<5>([&](auto i) {
        if (i + 1 == n) {
            res = solve<i + 1>(m, A, B);
        }
    });
    assert(res != -1);
    return res;
}

};  // namespace solve

void transpose(int n, int m, std::vector<int>& a) {
    std::vector<int> b(n * m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            b[j * n + i] = a[i * m + j];
        }
    }
    a.swap(b);
}

struct Test {
    int n, m;
    std::vector<int> a, b;

    // bool no_swap;

    Test() : n(0), m(0) {}

    Test(int n, int m) : n(n), m(m), a(n * m), b(n * m) { ; }

    void print() {
        std::cout << n << " " << m << "\n";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                std::cout << a[i * m + j] << " \n"[j + 1 == m];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                std::cout << b[i * m + j] << " \n"[j + 1 == m];
            }
        }
    }

    void reverse() {
        std::reverse(a.begin(), a.end());
        std::reverse(b.begin(), b.end());
    }
    void flip() {
        for (int i = 0; i < n; i++) {
            std::reverse(a.begin() + i * m, a.begin() + i * m + m);
            std::reverse(b.begin() + i * m, b.begin() + i * m + m);
        }
    }

    void add_noise(size_t cnt, int noise, int max_val) {
        for (size_t it = 0; it < cnt; it++) {
            int i = rnd.next(0, n * m - 1);
            int j = rnd.next(0, n * m - 1);
            int mn = std::min({noise, a[i], b[j]});
            int mx = std::min({noise, max_val - a[i], max_val - b[j]});

            mn = 0;
            int dlt = rnd.next(-mn, mx);
            a[i] += dlt, b[j] += dlt;
        }
    }

    void add_noise_2(size_t cnt, int noise, int max_val, int max_dist) {
        for (size_t it = 0; it < cnt; it++) {
            int x1 = rnd.next(0, n - 1);
            int y1 = rnd.next(0, m - 1);
            int dx = std::min(max_dist, n - 1);
            int dy = std::min(max_dist, m - 1);

            int x2 = x1 + rnd.next(-dx, dx);
            int y2 = y1 + rnd.next(-dy, dy);

            if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m || std::abs(x1 - x2) + std::abs(y1 - y2) > max_dist) {
                it--;
                continue;
            }
            {
                // assert(std::abs(x1 - x2) + std::abs(y1 - y2) <= max_dist);
                int i = x1 * m + y1, j = x2 * m + y2;

                int mn = std::min({noise, a[i], b[j]});
                int mx = std::min({noise, max_val - a[i], max_val - b[j]});

                mn = 0;
                int dlt = rnd.next(-mn, mx);
                a[i] += dlt, b[j] += dlt;
            }
        }
    }

    void stretch(int width, double p = 0.5) {
        if (m == 1) {
            return;
        }
        transpose(n, m, a), transpose(n, m, b);

        int dlt = (width - m) / (m - 1);
        std::vector<int> a2, b2;
        int m2 = 0;
        for (int i = 0; i < m; i++) {
            if (i != 0 && rnd.next() < p) {
                m2 += dlt;
                a2.insert(a2.end(), dlt * n, 0);
                b2.insert(b2.end(), dlt * n, 0);
            }
            m2++;
            a2.insert(a2.end(), a.begin() + i * n, a.begin() + i * n + n);
            b2.insert(b2.end(), b.begin() + i * n, b.begin() + i * n + n);
        }
        a = a2;
        b = b2;
        m = m2;

        transpose(m, n, a), transpose(m, n, b);

        assert(a.size() == n * m);
        assert(b.size() == n * m);
    }

    void upscale(int max_val, int64_t max_sum) {
        int max_a = 0, max_b = 0;
        int64_t sum = 0;
        for (auto& i : a) sum += i;
        for (auto& i : a) max_a = std::max(max_a, i);
        for (auto& i : b) max_b = std::max(max_b, i);
        int max = std::max(max_a, max_b);

        if (max == 0) {
            return;
        }

        int max_f = std::min<int64_t>({max_val / max, max_sum / sum});
        max_f = std::max(1, max_f);
        assert(max_f > 0);
        int f = rnd.next(std::max(1, max_f / 10), max_f);

        for (auto& i : a) i *= f, assert(i <= 1e9);
        for (auto& i : b) i *= f, assert(i <= 1e9);
    }
};

std::vector<int> sub_perm(int n, int k) {
    std::vector<int> ord = rnd.perm(n);
    ord.resize(k);
    return ord;
}

template <typename T>
void just_shuffle(std::vector<T>& vec) {
    for (int i = 0; i < vec.size(); i++) {
        std::swap(vec[i], vec[rnd.next(0, i)]);
    }
}

std::vector<int> gen_random(int n, int a, int k = -1, int64_t sum = -1, int64_t max_sum = -1) {
    if (k == -1) {
        k = n;
    }
    k = std::min(k, n);
    if (max_sum == -1) {
        max_sum = int64_t(a) * n;
    }
    std::vector<int> ord = sub_perm(n, k);

    std::vector<int> vec(n);
    for (int i : ord) {
        vec[i] = rnd.next(0, a);
    }
    assert(sum <= int64_t(a) * k);
    int64_t s = std::accumulate(vec.begin(), vec.end(), 0ll);
    {
        int64_t cnt = 0;
        std::vector<int> ind = ord;
        while (sum != -1 && s < sum) {
            assert(ind.size());
            // int i = ord[rnd.next(0, (int)ord.size() - 1)];
            for (auto& i : ind) {
                cnt++;
                int max_dlt = std::min<int64_t>(a - vec[i], sum - s);
                if (max_dlt == 0) {
                    i = -1;
                    continue;
                }
                int dlt = rnd.next(0, max_dlt);
                vec[i] += dlt, s += dlt;
            }
            std::erase(ind, -1);
        }
        // std::cerr << cnt << " ";
    }
    {
        std::vector<int> ind = ord;
        int64_t cnt = 0;
        while (sum != -1 && sum < s || max_sum < s) {
            assert(ind.size());
            // int i = ord[rnd.next(0, (int)ord.size() - 1)];
            for (auto& i : ind) {
                cnt++;
                int max_dlt = std::min<int64_t>(vec[i], s - sum);
                if (max_dlt == 0) {
                    i = -1;
                    continue;
                }
                int dlt = rnd.next(0, max_dlt);
                vec[i] -= dlt, s -= dlt;
            }
            std::erase(ind, -1);
        }
        // std::cerr << cnt << " ";
    }

    return vec;
}

std::vector<int> b_shuffle(std::vector<int> vec, int max_val, int k = -1) {
    int n = vec.size();
    if (k == -1) {
        k = n;
    }
    std::vector<int> ord = sub_perm(n, k);
    std::vector<int> b(n);

    std::vector<int> ind(n);
    std::iota(ind.begin(), ind.end(), 0);
    while (ind.size()) {
        // for (auto& val : vec) {
        for (int i : ind) {
            auto& val = vec[i];
            int j = ord[rnd.next(0, (int)ord.size() - 1)];
            int dlt = rnd.next(0, val);
            if (b[j] + dlt <= max_val) {
                val -= dlt;
                b[j] += dlt;
            }
        }
        std::erase_if(ind, [&](int i) { return vec[i] == 0; });
    }
    return b;
}

std::vector<int> b_move(int n, int m, std::vector<int> vec, int max_val, int max_dist) {
    std::vector<int> res(n * m);

    std::vector<std::pair<int, int>> ind(n * m);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ind[i * m + j] = {i, j};
        }
    }

    while (ind.size()) {
        for (auto [i, j] : ind) {
            int dx = std::min(max_dist, n - 1);
            int dy = std::min(max_dist, m - 1);

            int x = i + rnd.next(-dx, dx);
            int y = j + rnd.next(-dy, dy);
            if (x < 0 || x >= n || y < 0 || y >= m || std::abs(i - x) + std::abs(j - y) > max_dist) {
                continue;
            }

            int max_dlt = std::min(vec[i * m + j], max_val - res[x * m + y]);
            int dlt = rnd.next(0, max_dlt);
            vec[i * m + j] -= dlt, res[x * m + y] += dlt;
        }
        std::erase_if(ind, [&](auto ij) { return vec[ij.first * m + ij.second] == 0; });
    }
    return res;
}

namespace patterns {
const std::vector<std::string> patterns_data = {
    R"(

5

3 30

0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0


3 30
0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0


3 10
1 0 1 0 0 0 2 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 2 0 1 0 0 0 1 0



3 7

0 1 0 1 0 1 0
0 1 0 1 0 1 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 1 0 1 0 0
1 0 1 0 1 0 1


3 13
0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 1 0 1 0 1 0 0
1 0 1 0 1 0 1 0 1 0 1 0 1


    )",

    R"(
    
9
3 25
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
3 17
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
3 31
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
3 11
0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 2
1 0 0 0 1 2 0 0 0 0 0
0 0 2 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 2 0 0 0
0 0 1 0 0 0 0 0 1 0 2
3 13
1 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 2 0 0 0 0 0 2
0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 1 0 0 0 0 0 0 0 0 1
0 0 0 2 0 0 0 0 0 2 0 0 0
3 28
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0
3 14
0 0 0 0 2 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 3
0 0 0 0 1 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 1 1 0 0 0 1
1 0 0 0 0 0 0 0 2 0 0 0 0 0
3 18
0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
3 23
0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 2
0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 2

    
    
    )",

    R"(

8

2 11
0 0 1 0 0 0 1 1 1 0 0
0 1 1 0 0 0 1 0 0 0 0
2 0 0 0 2 0 0 0 1 0 0
0 0 0 0 1 0 0 1 0 0 0

2 9
0 0 1 0 1 0 1 0 0
0 0 2 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0
2 0 0 0 2 0 0 0 0



2 28
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 19
3 0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0
0 0 0 0 0 0 3 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 2
2 15
2 0 1 0 1 0 3 0 0 0 0 0 0 0 3
0 0 2 0 0 0 1 0 0 0 1 0 0 0 0
1 0 1 0 1 0 0 0 0 0 2 0 0 0 1
4 0 2 0 0 0 0 0 0 0 2 0 0 0 0
2 16
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 2 0 0 0 2 0 1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 3 0 0 0 0 0 1 0 0 0 0 0 0
2 33
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 26
1 0 0 0 0 3 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0
1 0 0 0 0 3 0 0 0 0 1 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0





    )",

    // anti skip

    R"(
12


3 3
1 2 0
0 0 2
1 1 0
0 0 4
1 0 1
1 0 0

3 9
1 1 0 0 0 0 0 1 0
1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 0

3 6
0 1 0 1 0 1
0 0 0 0 0 0
1 0 0 0 0 1
0 0 0 1 0 0
0 1 0 1 0 0
0 0 0 2 0 0
3 7
1 0 1 0 0 0 1
0 0 0 0 1 0 0
0 1 0 0 0 0 0
1 0 0 0 1 0 0
0 0 0 0 1 0 0
0 0 1 0 1 0 0


3 6
1 0 0 0 0 1
0 0 1 0 0 0
1 0 0 0 1 0
0 1 1 0 0 0
0 0 1 0 1 0
0 0 1 0 0 0
3 8
0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1
1 0 0 1 0 0 1 1
0 0 0 1 0 0 1 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 2 0
3 15
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 2
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
3 10
0 0 0 0 0 0 0 0 0 1
0 0 2 0 0 0 1 0 0 0
0 0 1 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 0 1 0 0 0 1 0 0 0
1 0 0 0 0 0 1 0 0 0


3 14
0 0 0 0 0 0 0 0 0 0 0 0 0 2
0 0 0 0 0 0 1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 2 0
0 0 0 0 0 0 1 0 0 0 0 0 1 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 2
3 17
1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 2 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0


3 10
2 0 0 0 0 0 0 0 2 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 2
0 0 0 0 1 0 0 0 0 0
1 0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 0 2
3 15
0 0 0 0 1 0 0 0 1 0 0 0 2 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 1 0 0 0 0 1 1
0 0 0 0 0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0



    )",

    R"(
1
1 3
1 0 0
0 0 1

    )",
};

struct Pattern {
    struct Block {
        std::vector<int> a, b;
        int dist_to_next = 0;
    };

    int n, width;
    int max;
    int64_t sum;
    int A, B;
    std::vector<Block> blocks;

    int ans_0;

    Pattern(int n, int m, std::vector<int> a, std::vector<int> b) : n(n) {
        ans_0 = solve::solve(n, m, a, b);

        transpose(n, m, a);
        transpose(n, m, b);

        for (int i = 0; i < m; i++) {
            Block bl;
            bl.a.assign(a.begin() + i * n, a.begin() + i * n + n);
            bl.b.assign(b.begin() + i * n, b.begin() + i * n + n);

            bool all_zeros = std::accumulate(bl.a.begin(), bl.a.end(), 0ll) == 0 && std::accumulate(bl.b.begin(), bl.b.end(), 0ll) == 0;
            if (!all_zeros) {
                if (blocks.size() && blocks.back().dist_to_next == 0) {
                    blocks.back().a.insert(blocks.back().a.end(), bl.a.begin(), bl.a.end());
                    blocks.back().b.insert(blocks.back().b.end(), bl.b.begin(), bl.b.end());
                } else {
                    blocks.push_back(bl);
                }
            } else {
                if (blocks.size()) {
                    blocks.back().dist_to_next += 1;
                }
            }
        }

        assert(blocks.size());
        blocks.back().dist_to_next = 0;

        width = 0;
        max = 0;
        sum = 0;
        A = 0, B = 0;
        for (auto& bl : blocks) {
            for (auto& i : bl.a) {
                sum += i;
            }

            for (auto& i : bl.a) A += bool(i), max = std::max(max, i);
            for (auto& i : bl.b) B += bool(i), max = std::max(max, i);

            width += bl.a.size() / n;
            width += bl.dist_to_next;
        }
    }

    Test gen_test(int max_m, bool fixed = false) const {
        int max_dlt = (max_m - width) / std::max<int>(1, blocks.size() - 1);
        int dlt = rnd.next(max_dlt / 2, max_dlt);
        int left = max_m - width - dlt * ((int)blocks.size() - 1);
        int p_left = rnd.next(0, left / 2);
        int p_right = rnd.next(0, left / 2);

        if (fixed) {
            dlt = 0;
        }

        Test test;
        test.n = n;

        test.a.insert(test.a.end(), p_left * n, 0);
        test.b.insert(test.b.end(), p_left * n, 0);

        for (size_t i = 0; i < blocks.size(); i++) {
            const Block& bl = blocks[i];

            test.a.insert(test.a.end(), bl.a.begin(), bl.a.end());
            test.b.insert(test.b.end(), bl.b.begin(), bl.b.end());

            if (i + 1 != blocks.size()) {
                test.a.insert(test.a.end(), (bl.dist_to_next + dlt) * n, 0);
                test.b.insert(test.b.end(), (bl.dist_to_next + dlt) * n, 0);
            }
        }

        test.a.insert(test.a.end(), p_right * n, 0);
        test.b.insert(test.b.end(), p_right * n, 0);

        test.m = test.a.size() / test.n;

        transpose(test.m, test.n, test.a);
        transpose(test.m, test.n, test.b);

        assert(test.a.size() == test.n * test.m);
        assert(test.b.size() == test.n * test.m);

        return test;
    }
};

std::vector<Pattern> read_patterns(std::string s) {
    std::stringstream sin(s);
    int t;
    sin >> t;
    std::vector<Pattern> vec;
    for (int it = 0; it < t; it++) {
        int n, m;
        sin >> n >> m;
        std::vector<int> a(n * m), b(n * m);
        for (auto& i : a) sin >> i;
        for (auto& i : b) sin >> i;

        vec.push_back(Pattern(n, m, a, b));
    }

    assert(!sin.fail());

    return vec;
}

std::vector<std::string> patterns_fixed_data = {
    R"(
11

3 8
0 0 1 0 0 0 0 0
0 0 0 1 0 0 1 1
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 0
0 0 0 0 0 1 0 0
0 1 0 0 0 1 0 0

3 7
0 0 1 0 1 0 0
1 0 0 0 1 0 0
0 0 0 0 0 0 0
0 0 1 0 0 0 1
0 0 1 0 0 0 0
0 0 1 0 0 0 0



3 8
0 0 1 0 0 0 2 1
0 0 1 2 0 0 0 0
0 0 2 0 0 0 0 2
0 0 0 0 1 0 2 0
1 0 1 0 3 0 0 0
0 0 0 1 0 0 1 1
3 9
0 2 0 0 0 1 1 4 0
1 0 0 0 0 0 1 0 1
0 0 0 1 0 0 1 0 0
0 0 0 2 1 0 3 1 0
1 0 0 1 0 0 0 0 0
0 0 0 0 1 0 1 0 2
3 9
0 0 0 0 1 0 1 1 2
1 0 0 0 1 0 0 0 0
0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 3 0 0
0 1 0 0 1 0 0 1 1


3 13
0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 1 0 1 0 1 0 0
1 0 1 0 1 0 1 0 1 0 1 0 1


2 10
0 0 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 1 0 0 0 1 0 0 0
2 13
0 0 0 0 1 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 1 1 0 0 0 1
0 0 0 0 0 0 1 0 0 0 1 0 0
0 0 1 0 1 1 0 0 0 0 1 0 0
2 11
0 0 1 0 0 0 2 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 1 0 0 0 1 0 0


2 10
0 0 1 1 0 1 1 0 0 1
0 0 0 1 0 1 0 0 0 0
0 1 0 0 0 0 0 1 0 0
0 1 1 1 0 0 0 2 0 0
2 9
0 0 0 1 0 0 0 3 0
0 0 1 2 0 0 0 0 0
0 0 0 0 0 3 0 0 0
1 2 0 0 0 1 0 0 0


                )",

    R"(

5



2 10
0 0 0 1 0 1 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 1 0 1 0 0 0 0 0
2 6
0 0 1 0 0 0
0 0 2 0 2 0
0 1 0 1 0 0
0 1 0 2 0 0
3 7
0 0 0 0 0 1 0
0 0 0 0 0 1 0
0 0 0 1 0 1 0
0 0 0 0 0 0 0
0 0 0 0 1 1 1
0 0 0 0 1 0 0
3 7
0 0 0 1 0 1 0
0 1 0 0 0 1 0
0 0 0 0 0 1 0
0 0 0 0 1 0 0
0 0 0 0 1 1 1
0 1 0 0 0 0 0
3 6
0 0 1 0 1 0
1 1 0 0 1 0
0 0 1 0 1 0
0 0 0 1 0 0
0 0 1 1 1 1
1 1 0 0 0 0

                
                )"

    R"(

6

2 11
0 0 1 0 0 0 2 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 1 0 0 0 1 0 0
3 8
0 0 1 0 0 0 2 1
0 0 1 2 0 0 0 0
0 0 2 0 0 0 0 2
0 0 0 0 1 0 2 0
1 0 1 0 3 0 0 0
0 0 0 1 0 0 1 1

3 9
0 0 0 0 1 0 1 1 2
1 0 0 0 1 0 0 0 0
0 0 0 0 1 1 0 0 0
0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 3 0 0
0 1 0 0 1 0 0 1 1
3 6
0 0 0 0 0 0
0 0 0 0 0 0
1 0 1 0 0 0
0 0 0 0 0 0
0 1 0 0 0 0
0 1 0 0 0 0

2 3
0 0 0
1 0 1
0 1 0
0 1 0

3 3
1 0 0
0 0 0
1 0 1
0 0 0
1 1 0
                )",

    // anti skip
    R"(

5

3 6
1 0 1 0 0 0
1 0 0 0 0 0
0 1 0 1 0 0
0 0 1 0 0 0
1 1 1 0 0 0
0 0 1 0 0 0


3 4
1 0 1 0
1 1 0 1
0 1 0 1
2 0 0 0
2 0 1 1
0 0 1 0

3 4
1 0 1 1
0 1 0 1
0 1 0 1
1 0 0 1
2 0 0 2
0 0 1 0
3 3
1 1 0
1 0 2
1 0 0
0 1 0
1 0 2
1 0 1

3 5
0 1 0 1 0
1 0 1 1 0
1 0 0 0 0
1 0 1 0 0
1 0 2 0 0
0 0 1 0 0


        )",

};

std::vector<Pattern> patterns = [] {
    std::vector<std::string> data = patterns_data;
    data.insert(data.end(), patterns_fixed_data.begin(), patterns_fixed_data.end());

    std::vector<Pattern> res;
    for (auto s : data) {
        auto vec = read_patterns(s);
        res.insert(res.end(), vec.begin(), vec.end());
    }
    return res;
}();

std::vector<Pattern> patterns_fixed = [] {
    std::vector<Pattern> res;
    for (auto s : patterns_fixed_data) {
        auto vec = read_patterns(s);
        res.insert(res.end(), vec.begin(), vec.end());
    }
    return res;
}();

};  // namespace patterns

int main(int argc, char* argv[]) {
    registerGen(argc, argv, 1);

    std::string seed = opt<std::string>("seed", "meow");

    Limits limits = LIMITS[opt<int>("group")];
    const int max_T = opt<int>("max_T", limits.max_T);
    const int max_sum_m = opt<int>("sum_m", limits.max_sum_m);
    const int max_n = opt<int>("n", limits.max_n);
    const int max_m = opt<int>("m", std::min(max_sum_m, limits.max_m));

    const int max_val = opt<int>("max_val", limits.max_val);
    const int max_val_a = opt<int>("max_val_a", max_val);

    const int64_t max_sum_init = opt<int64_t>("max_sum", limits.max_sum);
    const int max_A = opt<int>("max_A", limits.max_A);
    const int max_B = opt<int>("max_B", limits.max_B);
    const int max_ans = opt<int>("max_ans", limits.max_ans);

    std::string mode = opt<std::string>("mode");

    // const int T = [&] {
    //     return std::min(max_T, sum_m / m);
    // }();

    std::vector<Test> tests;

    int sum_m = 0;

    int pattern_skips = opt<int>("pattern_skips", 0);

    for (int test_ind = 0, counter = 0; test_ind < max_T; test_ind++, counter++) {
        int n = max_n, m = max_m;

        if (opt<bool>("list_small_nm")) {
            n = test_ind % max_n + 1;
            m = test_ind / max_n + 1;
        }

        if (opt<bool>("many_tests")) {
            int avg_m = max_sum_m / max_T;
            assert(0 < avg_m);

            auto gen_m = [&] {
                return rnd.next(std::clamp<int>(avg_m * 0.8, 1, max_m), std::min<int>(max_m, avg_m * 1.5));
            };

            m = gen_m();
            if (m > avg_m) {
                m = gen_m();
            }
        } else if (opt<bool>("exact_tests")) {
            m = std::min(max_m, max_sum_m / max_T);
        }

        Test test(n, m);
        if (sum_m + test.m > max_sum_m) {
            break;
        }

        int stretch_from_max = opt<int>("stretch_from_max", -1);
        int stretch_from = -1;
        if (stretch_from_max != -1) {
            stretch_from = rnd.next(3, stretch_from_max);
            test = Test(n, stretch_from);
        }

        int n0 = n, m0 = m;

        n = test.n, m = test.m;

        int64_t max_sum = std::min<int64_t>(max_sum_init, int64_t(max_val) * n * m);

        if (mode == "dual") {
            std::string A = opt<std::string>("A");
            std::string B = opt<std::string>("B");

            std::vector<std::string> A_modes = {
                "sorted_random",
                "random",
            };
            std::vector<std::string> B_modes = {
                "sorted_random",
                "r_sorted_random",
                "random",
                "b_shuffle",
            };

            if (max_A >= test.n * test.m) {
                A_modes.push_back("uniform");
            }
            if (max_B >= test.n * test.m) {
                B_modes.push_back("random_b_move");
                B_modes.push_back("uniform");
            }
            if (max_sum <= 1e7) {
                if (max_A >= test.n * test.m) {
                    A_modes.push_back("random_by_one");
                }
                if (max_B >= test.n * test.m) {
                    B_modes.push_back("random_by_one");
                }
            }

            if (A == "choose_random") {
                A = A_modes[rnd.next(0, (int)A_modes.size() - 1)];
            }
            if (B == "choose_random") {
                B = B_modes[rnd.next(0, (int)B_modes.size() - 1)];
            }

            // std::cerr << test_ind + 1 << " " << A << " " << B << std::endl;

            if (A == "sorted_random") {
                test.a = gen_random(n * m, max_val_a, max_A, -1, max_sum);
                for (int i = 0; i < n; i++) {
                    std::sort(test.a.begin() + i * m, test.a.begin() + i * m + m);
                }
            } else if (A == "random_by_one") {
                assert(max_sum <= 1e8);
                for (int64_t i = 0; i < max_sum; i++) {
                    int j = rnd.next(0, n * m - 1);
                    test.a[j] += 1;
                }
            } else if (A == "random") {
                test.a = gen_random(n * m, max_val_a, max_A, -1, max_sum);
            } else if (A == "random_k") {
                test.a = gen_random(n * m, max_val_a, opt<int>("k"), -1, max_sum);
            } else if (A == "uniform") {
                test.a = std::vector<int>(n * m, rnd.next(0, (int)std::min<int64_t>(max_val_a, max_sum / (n * m))));
            } else {
                ensuref(false, "unknown A mode: \"%s\"", A.c_str());
            }

            int64_t sum_a = std::accumulate(test.a.begin(), test.a.end(), 0ll);

            if (B == "random_b_move") {
                test.b = b_move(test.n, test.m, test.a, max_val, max_ans);
            } else if (B == "sorted_random") {
                test.b = gen_random(n * m, max_val, max_B, sum_a);

                for (int i = 0; i < n; i++) {
                    std::sort(test.b.begin() + i * m, test.b.begin() + i * m + m);
                }
            } else if (B == "r_sorted_random") {
                test.b = gen_random(n * m, max_val, max_B, sum_a);
                for (int i = 0; i < n; i++) {
                    std::sort(test.b.begin() + i * m, test.b.begin() + i * m + m, std::greater<int>());
                }
            } else if (B == "random_by_one") {
                assert(sum_a <= 1e8);
                for (int64_t i = 0; i < sum_a; i++) {
                    int j = rnd.next(0, n * m - 1);
                    test.b[j] += 1;
                }
            } else if (B == "random") {
                test.b = gen_random(n * m, max_val, max_B, sum_a);
            } else if (B == "random_k") {
                test.b = gen_random(n * m, max_val, opt<int>("k"), sum_a, max_sum);
            } else if (B == "uniform") {
                test.b = std::vector<int>(n * m, sum_a / (n * m));
                int cnt = sum_a % (n * m);
                if (cnt != 0) {
                    for (int i = 0; i < cnt; i++) {
                        test.b[int64_t(n * m) * i / cnt] += 1;
                    }
                }
                // std::vector<int> ord = sub_perm(n * m, sum_a % (n * m));
                // for (int i : ord) {
                //     test.b[i] += 1;
                // }
            } else if (B == "shuffle") {
                test.b = test.a;
                just_shuffle(test.b);
            } else if (B == "b_shuffle") {
                test.b = b_shuffle(test.a, max_val, max_B);
            } else {
                ensuref(false, "unknown B mode: \"%s\"", B.c_str());
            }

        } else if (mode == "pattern") {
            using namespace patterns;

            auto& pts = patterns::patterns;
            const Pattern& p = pts[counter % pts.size()];
            if (n > 1 && p.n == 1) {
                test_ind--;
                continue;
            }
            if (p.n != n || p.sum > max_sum || p.width > m || p.A > max_A || p.B > max_B || p.ans_0 > max_ans) {
                test_ind--;
                continue;
            }

            // bool expand = !opt<bool>("no_expand");
            bool fixed = opt<bool>("fixed");
            test = p.gen_test(m, fixed);

            if (pattern_skips > 0) {
                test_ind--;
                pattern_skips -= 1;
                continue;
            }

        } else if (mode == "max_ans") {
            test.a[0] = std::min<int64_t>({max_val, max_val_a, max_sum});
            test.b.back() = test.a[0];
        } else if (mode == "chain_1") {
            assert(2 <= n);

            int width = opt<int>("width", -1);
            if (width == -1) {
                int max_width = std::min(max_ans - 1, m / 10);
                width = rnd.next(1, max_width);
            }

            int max_segments = opt<int>("max_segments", -1);
            if (max_segments == -1) {
                max_segments = m;
            }
            max_segments = std::min<int64_t>({max_segments, max_sum / 2, max_A / 2, max_B / 2});
            max_segments = std::min<int64_t>((m - 1) / (2 * width), max_segments);

            int segments = opt<int>("segments", -1);
            if (segments == -1) {
                segments = rnd.next(std::max(1, max_segments / 10), max_segments);
            } else if (segments == -2) {
                segments = max_segments;
            }

            int len = 1 + 2 * width * segments;
            int start = rnd.next(0, m - len);

            int ind = 0;
            std::vector<int> inds = {0, 1};
            if (opt<bool>("high") || rnd.next(0, 2)) {
                inds = {0, n - 1};
            }
            if (width + 1 == max_ans) {
                inds = {0, 1};
            }

            bool shifted = opt<bool>("shifted");
            if (shifted) {
                assert(3 <= n);
                inds = {1, 2};
            }

            for (int i = 0; i < segments; i++) {
                test.a[ind * m + (start + 2 * width * i + 0 * width)] += 1;
                if (shifted && test.a[ind * m + (start + 2 * width * i + 0 * width)] == 2) {
                    test.a[(ind + 0) * m + (start + 2 * width * i + 0 * width)]--;
                    test.a[(ind + 1) * m + (start + 2 * width * i + 0 * width)]++;
                }
                test.a[ind * m + (start + 2 * width * i + 2 * width)] += 1;
                test.b[inds[0] * m + start + 2 * width * i + 1 * width] += 1;
                test.b[inds[1] * m + start + 2 * width * i + 1 * width] += 1;
            }
        }

        else {
            ensuref(false, "unknown mode: \"%s\"", mode.c_str());
        }

        if (stretch_from != -1) {
            double p = opt<double>("stretch_prob", 0.8);
            test.stretch(m0, p);
        }

        test.upscale(max_val, max_sum);

        sum_m += test.m;
        tests.push_back(test);
    }

    if (opt<bool>("exact_tests")) {
        assert(tests.size() == max_T);
    }

    if (int noise = opt<int>("noise", 0); noise) {
        double intensity = opt<double>("intensity", 1.0);
        for (auto& test : tests) {
            size_t cnt = test.n * test.m;
            cnt = cnt * intensity;
            test.add_noise(cnt, noise, max_val);
        }
    }
    if (int noise = opt<int>("noise_d", 0); noise) {
        int dist = opt<int>("dist");
        double intensity = opt<double>("intensity", 1.0);
        for (auto& test : tests) {
            size_t cnt = test.n * test.m;
            cnt = cnt * intensity;
            test.add_noise_2(cnt, noise, max_val, dist);
        }
    }

    bool swap = !opt<bool>("no_swap");
    for (auto& test : tests) {
        if (swap && limits.max_A == limits.max_B && rnd.next(0, 1)) {
            test.a.swap(test.b);
        }
        if (rnd.next(0, 1)) {
            test.reverse();
        }
        if (rnd.next(0, 1)) {
            test.flip();
        }
    }

    std::cout << tests.size() << "\n";
    for (auto& test : tests) {
        test.print();
    }

    return 0;
}
