QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#916709#10102. Puzzle: Nurikabelunch break at 4:30 (Maksim Gorokhovskii, Ivan Safonov, Ramazan Rakhmatullin)AC ✓49ms35640kbC++2011.2kb2025-02-26 21:55:142025-02-26 21:55:16

Judging History

This is the latest submission verdict.

  • [2025-02-26 21:55:16]
  • Judged
  • Verdict: AC
  • Time: 49ms
  • Memory: 35640kb
  • [2025-02-26 21:55:14]
  • Submitted

answer

/*
    author:  Maksim1744
    created: 22.02.2025 15:08:10
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()

#ifdef ONPC
mt19937 rnd(223);
#else
mt19937 rnd(chrono::high_resolution_clock::now()
                        .time_since_epoch().count());
#endif


template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void setmin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void setmax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/home/team/tools/programming-library/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#define OSTREAM(...)    ;
#define OSTREAM0(...)   ;
#endif

vector<string> flipi(vector<string> v) {
    reverse(all(v));
    return v;
}

vector<string> flipj(vector<string> v) {
    for (auto& s : v) {
        reverse(all(s));
    }
    return v;
}

vector<string> trans(const vector<string>& v) {
    if (v.empty()) {
        return v;
    }
    vector<string> res(v[0].size(), string(v.size(), ' '));
    for (int i = 0; i < v.size(); ++i) {
        for (int j = 0; j < v[i].size(); ++j) {
            res[j][i] = v[i][j];
        }
    }
    return res;
}

namespace grid_iterator_ns {
const array<pair<int, int>, 8> dirs = {{{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}}};
struct GridIterator {
    int n, m;
    GridIterator(int n, int m) : n(n), m(m) {}

    template<size_t N>
    struct NeighbourIteratorContainer {
        int i, j, n, m;
        NeighbourIteratorContainer(int i, int j, int n, int m) : i(i), j(j), n(n), m(m) {}

        struct NeighbourIterator {
            int cur;
            int i, j, n, m;
            NeighbourIterator(int cur, int i, int j, int n, int m) : cur(cur), i(i), j(j), n(n), m(m) {
                skip_to_first_allowed();
            }

            void skip_to_first_allowed() {
                while (cur < N &&
                    (i + dirs[cur].first  < 0 || i + dirs[cur].first  >= n ||
                     j + dirs[cur].second < 0 || j + dirs[cur].second >= m)) {
                    ++cur;
                }
            }

            NeighbourIterator& operator ++ () {
                ++cur;
                skip_to_first_allowed();
                return *this;
            }

            pair<int, int> operator * () const { return {i + dirs[cur].first, j + dirs[cur].second}; }

            bool operator == (const NeighbourIterator& other) const { return cur == other.cur; }
            bool operator != (const NeighbourIterator& other) const { return cur != other.cur; }
        };

        auto begin() const { return NeighbourIterator(0, i, j, n, m); }
        auto end()   const { return NeighbourIterator(N, i, j, n, m); }

        auto collect() const {
            vector<pair<int, int>> result;
            for (auto it = begin(); it != end(); ++it) result.push_back(*it);
            return result;
        }
    };

    template<size_t N>
    auto iterate(int i, int j) const {
        static_assert(N == 4 || N == 8, "you can remove this, but make sure you understand what you are doing");
        return NeighbourIteratorContainer<N>(i, j, n, m);
    }
};
}
using grid_iterator_ns::GridIterator;


vector<string> solve(int n, int m, int i, int j, int x) {
    show(n, m, i, j, x);
    if (i > n - 1 - i) {
        return flipi(solve(n, m, n - 1 - i, j, x));
    }
    if (j > m - 1 - j) {
        return flipj(solve(n, m, i, m - 1 - j, x));
    }
    if (min(n, m) <= 2 && n > m) {
        return trans(solve(m, n, j, i, x));
    }
    if (n == 1) {
        if (x < j + 1) {
            return {};
        }
        vector<string> v(1, string(m, '.'));
        for (int k = x; k < m; ++k) {
            v[0][k] = '#';
        }
        return v;
    }
    if (n == 2) {
        assert(i == 0);
        int min_white = m - 2;
        if (j == 0) {
            min_white += 1;
        }
        if (x < min_white) {
            return {};
        }
        vector<string> v(2, string(m, '.'));
        int need_black = n * m - x;
        int have_black = 0;
        // show(need_black);
        auto add = [&](int x, int y) {
            if (i == x && j == y) {
                return;
            }
            // show(x, y, have_black, need_black);
            if (have_black >= need_black) return;
            have_black += 1;
            v[x][y] = '#';
        };
        add(0, 0);
        for (int k = 0; k < m; ++k) {
            add(1, k);
        }
        add(0, m - 1);
        return v;
    }
    if (j == 0 && i != 0) {
        return trans(solve(m, n, j, i, x));
    }
    int max_black = n * m - (n - 2) * (m - 2) + (n - 3) * (m - 3) / 2;
    set<pair<int, int>> bad;
    if (i == 0) {
        --max_black;
        bad.emplace(0, j);
        if (j == 0) {
            bad.emplace(0, 1);
            --max_black;
        }
    }
    int min_white = n * m - max_black;
    show(n, m, i, j, x, min_white, max_black);
    if (x < min_white) {
        return {};
    }
    int skip_col = j;
    if (i == 0) skip_col = 1;
    vector<string> res(n, string(m, '.'));
    int need_black = n * m - x;
    int have_black = 0;
    auto add = [&](int x, int y) {
        show(x, y, have_black, need_black);
        if (bad.count({x, y})) return;
        if (have_black >= need_black) return;
        have_black += 1;
        res[x][y] = '#';
    };
    for (int i = 1; i + 1 < n; ++i) {
        res[i][0] = '#';
        res[i].back() = '#';
        have_black += 2;
    }
    res[0] = string(m, '#');
    res.back() = string(m, '#');
    have_black += m * 2;
    show(have_black, bad);
    for (auto [i, j] : bad) {
        res[i][j] = '.';
        have_black -= 1;
    }
    show(have_black);

    for (int i = 2; i + 2 < n; i += 2) {
        for (int j = 1; j < skip_col; ++j) {
            add(i, j);
        }
        for (int j = m - 2; j > skip_col; --j) {
            add(i, j);
        }
    }
    if (n % 2 == 0) {
        for (int j = 2; j <= skip_col; j += 2) {
            add(n - 2, j);
        }
        for (int j = m - 3; j > skip_col; j -= 2) {
            add(n - 2, j);
        }
    }
    if (i == 0) {
        res[0][j] = '.';
        if (j == 0) {
            res[0][1] = '.';
        }
    }

    GridIterator gi(n, m);

    set<pair<int, pair<int, int>>> rem;
    vector<vector<int>> deg(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            int dd = 0;
            if (res[i][j] == '#') {
                for (auto [x, y] : gi.iterate<4>(i, j)) {
                    if (res[x][y] == '#') {
                        dd++;
                    }
                }
                rem.emplace(dd, mp(i, j));
                deg[i][j] = dd;
            }
        }
    }
    show(need_black, rem.size());
    show(res);
    while (rem.size() > need_black) {
        int i, j;
        if (rem.begin()->first == 2) {
            i = 0;
            j = 1;
            rem.erase({2, {i, j}});
        } else {
            auto [_, who] = *rem.begin();
            rem.erase(rem.begin());
            tie(i, j) = who;
        }
        res[i][j] = '.';
        for (auto [x, y] : gi.iterate<4>(i, j)) {
            if (res[x][y] == '#') {
                rem.erase({deg[x][y], mp(x, y)});
                deg[x][y] -= 1;
                rem.insert({deg[x][y], mp(x, y)});
            }
        }
    }
    return res;
}

void test_case(int test) {
    int n, m;
    cin >> n >> m;
    int i, j, x;
    cin >> i >> j >> x;
    --i; --j;
    // for (int n = 1; n <= 10; ++n) {
    //     for (int m = 1; m <= 10; ++m) {
    //         for (int i = 0; i < n; ++i) {
    //             for (int j = 0; j < m; ++j) {
    //                 for (int x = 1; x <= n * m; ++x) {
    //                     auto v = solve(n, m, i, j, x);
    //                     cout << n << ' ' << m << ' ' << i << ' ' << j << ' ' << x << endl;
    //                     for (const auto& s : v) {
    //                         cout << s << '\n';
    //                     }
    //                     cout << '\n';
    //                     if (!v.empty()) {
    //                         cout.flush();
    //                         assert(v.size() == n);
    //                         assert(v[0].size() == m);
    //                         assert(v[i][j] == '.');
    //                         int cnt = 0;
    //                         for (const auto& s : v) {
    //                             cnt += count(all(s), '.');
    //                         }
    //                         assert(cnt == x);
    //                     }
    //                 }
    //             }
    //         }
    //     }
    // }
    // exit(0);
    auto v = solve(n, m, i, j, x);
    if (v.empty()) {
        cout << "No\n";
    } else {
        cout << "Yes\n";
        for (const auto& l : v) {
            cout << l << '\n';
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int T;
    cin >> T;
    for (int test = 1; test <= T; ++test) {
        test_case(test);
    }

    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

4
3 3
2 2 1
5 5
2 2 1
4 6
1 1 20
2 5
2 5 10

output:

Yes
###
#.#
###
No
Yes
......
......
......
..####
Yes
.....
.....

result:

ok Correct, #(YES) = 3, #(NO) = 1, sum(nm) = 68 (4 test cases)

Test #2:

score: 0
Accepted
time: 16ms
memory: 3584kb

input:

6417
1 1
1 1 1
1 2
1 1 1
1 2
1 1 2
1 2
1 2 1
1 2
1 2 2
1 3
1 1 1
1 3
1 1 2
1 3
1 1 3
1 3
1 2 2
1 3
1 2 3
1 4
1 1 1
1 4
1 1 2
1 4
1 1 3
1 4
1 1 4
1 4
1 2 2
1 4
1 2 3
1 4
1 2 4
1 5
1 1 1
1 5
1 1 2
1 5
1 1 3
1 5
1 1 4
1 5
1 1 5
1 5
1 2 2
1 5
1 2 3
1 5
1 2 4
1 5
1 2 5
1 6
1 1 1
1 6
1 1 2
1 6
1 1 3
1 6
1...

output:

Yes
.
Yes
.#
Yes
..
Yes
#.
Yes
..
Yes
.##
Yes
..#
Yes
...
Yes
..#
Yes
...
Yes
.###
Yes
..##
Yes
...#
Yes
....
Yes
..##
Yes
...#
Yes
....
Yes
.####
Yes
..###
Yes
...##
Yes
....#
Yes
.....
Yes
..###
Yes
...##
Yes
....#
Yes
.....
Yes
.#####
Yes
..####
Yes
...###
Yes
....##
Yes
.....#
Yes
......
Yes
..#...

result:

ok Correct, #(YES) = 6417, #(NO) = 0, sum(nm) = 445848 (6417 test cases)

Test #3:

score: 0
Accepted
time: 18ms
memory: 3584kb

input:

6417
1 1
1 1 1
1 2
1 2 1
1 2
1 2 2
1 2
1 1 1
1 2
1 1 2
1 3
1 3 1
1 3
1 3 2
1 3
1 3 3
1 3
1 2 2
1 3
1 2 3
1 4
1 4 1
1 4
1 4 2
1 4
1 4 3
1 4
1 4 4
1 4
1 3 2
1 4
1 3 3
1 4
1 3 4
1 5
1 5 1
1 5
1 5 2
1 5
1 5 3
1 5
1 5 4
1 5
1 5 5
1 5
1 4 2
1 5
1 4 3
1 5
1 4 4
1 5
1 4 5
1 6
1 6 1
1 6
1 6 2
1 6
1 6 3
1 6
1...

output:

Yes
.
Yes
#.
Yes
..
Yes
.#
Yes
..
Yes
##.
Yes
#..
Yes
...
Yes
..#
Yes
...
Yes
###.
Yes
##..
Yes
#...
Yes
....
Yes
##..
Yes
#...
Yes
....
Yes
####.
Yes
###..
Yes
##...
Yes
#....
Yes
.....
Yes
###..
Yes
##...
Yes
#....
Yes
.....
Yes
#####.
Yes
####..
Yes
###...
Yes
##....
Yes
#.....
Yes
......
Yes
###...

result:

ok Correct, #(YES) = 6417, #(NO) = 0, sum(nm) = 445848 (6417 test cases)

Test #4:

score: 0
Accepted
time: 19ms
memory: 3584kb

input:

6417
1 1
1 1 1
1 2
1 1 1
1 2
1 1 2
1 2
1 2 1
1 2
1 2 2
1 3
1 1 1
1 3
1 1 2
1 3
1 1 3
1 3
1 2 2
1 3
1 2 3
1 4
1 1 1
1 4
1 1 2
1 4
1 1 3
1 4
1 1 4
1 4
1 2 2
1 4
1 2 3
1 4
1 2 4
1 5
1 1 1
1 5
1 1 2
1 5
1 1 3
1 5
1 1 4
1 5
1 1 5
1 5
1 2 2
1 5
1 2 3
1 5
1 2 4
1 5
1 2 5
1 6
1 1 1
1 6
1 1 2
1 6
1 1 3
1 6
1...

output:

Yes
.
Yes
.#
Yes
..
Yes
#.
Yes
..
Yes
.##
Yes
..#
Yes
...
Yes
..#
Yes
...
Yes
.###
Yes
..##
Yes
...#
Yes
....
Yes
..##
Yes
...#
Yes
....
Yes
.####
Yes
..###
Yes
...##
Yes
....#
Yes
.....
Yes
..###
Yes
...##
Yes
....#
Yes
.....
Yes
.#####
Yes
..####
Yes
...###
Yes
....##
Yes
.....#
Yes
......
Yes
..#...

result:

ok Correct, #(YES) = 6417, #(NO) = 0, sum(nm) = 445848 (6417 test cases)

Test #5:

score: 0
Accepted
time: 19ms
memory: 3712kb

input:

6417
1 1
1 1 1
1 2
1 2 1
1 2
1 2 2
1 2
1 1 1
1 2
1 1 2
1 3
1 3 1
1 3
1 3 2
1 3
1 3 3
1 3
1 2 2
1 3
1 2 3
1 4
1 4 1
1 4
1 4 2
1 4
1 4 3
1 4
1 4 4
1 4
1 3 2
1 4
1 3 3
1 4
1 3 4
1 5
1 5 1
1 5
1 5 2
1 5
1 5 3
1 5
1 5 4
1 5
1 5 5
1 5
1 4 2
1 5
1 4 3
1 5
1 4 4
1 5
1 4 5
1 6
1 6 1
1 6
1 6 2
1 6
1 6 3
1 6
1...

output:

Yes
.
Yes
#.
Yes
..
Yes
.#
Yes
..
Yes
##.
Yes
#..
Yes
...
Yes
..#
Yes
...
Yes
###.
Yes
##..
Yes
#...
Yes
....
Yes
##..
Yes
#...
Yes
....
Yes
####.
Yes
###..
Yes
##...
Yes
#....
Yes
.....
Yes
###..
Yes
##...
Yes
#....
Yes
.....
Yes
#####.
Yes
####..
Yes
###...
Yes
##....
Yes
#.....
Yes
......
Yes
###...

result:

ok Correct, #(YES) = 6417, #(NO) = 0, sum(nm) = 445848 (6417 test cases)

Test #6:

score: 0
Accepted
time: 47ms
memory: 3584kb

input:

33271
9 2
6 2 2
5 4
3 3 3
8 2
2 2 10
7 8
4 8 39
2 9
2 7 8
2 4
2 1 5
9 1
1 1 3
2 6
1 6 2
6 9
2 5 19
10 10
1 7 15
10 3
2 1 16
7 8
4 5 10
4 8
4 5 8
4 1
4 1 2
9 4
4 3 13
4 9
1 2 2
1 1
1 1 1
3 10
1 9 17
5 9
3 4 36
10 9
3 7 16
6 6
5 4 5
7 6
5 2 5
6 7
6 1 35
10 6
1 4 47
10 1
2 1 2
8 1
6 1 1
9 1
4 1 6
5 8
4...

output:

No
No
Yes
##
#.
#.
#.
#.
..
..
..
Yes
######..
#.......
#.......
#.......
#.......
#.......
######..
Yes
#########
........#
Yes
###.
....
Yes
.
.
.
#
#
#
#
#
#
No
Yes
#########
#.......#
####.####
#.......#
#.#.#.#.#
#########
No
Yes
.##
..#
..#
..#
..#
..#
..#
..#
#.#
###
No
No
Yes
#
#
.
.
Yes
###...

result:

ok Correct, #(YES) = 24504, #(NO) = 8767, sum(nm) = 1000000 (33271 test cases)

Test #7:

score: 0
Accepted
time: 47ms
memory: 3712kb

input:

33153
9 6
3 6 48
2 7
2 1 5
7 10
1 7 45
4 9
2 5 32
7 7
3 6 3
10 5
5 1 11
5 10
5 3 15
10 5
6 2 27
7 10
1 1 22
7 6
2 1 38
10 2
7 1 8
1 5
1 1 4
10 1
5 1 4
1 8
1 5 4
1 7
1 3 3
4 9
4 9 2
2 3
1 3 4
7 3
2 2 19
9 4
2 4 25
8 7
6 4 16
9 10
1 3 45
3 3
1 1 5
6 2
2 2 11
1 9
1 9 9
5 7
1 7 29
6 7
2 2 23
2 7
1 5 11
...

output:

Yes
......
......
......
#.....
#.....
#.....
#.....
#.....
#.....
No
Yes
#####.....
#........#
#........#
#........#
#........#
#........#
##########
Yes
.........
.........
.........
.....####
No
No
No
Yes
#####
#...#
#...#
#...#
#...#
#...#
#...#
#...#
#...#
...##
No
Yes
......
......
......
.......

result:

ok Correct, #(YES) = 24518, #(NO) = 8635, sum(nm) = 1000000 (33153 test cases)

Test #8:

score: 0
Accepted
time: 49ms
memory: 3712kb

input:

32853
7 7
2 2 23
5 1
4 1 1
7 8
3 1 32
1 3
1 3 1
5 3
5 1 14
9 6
9 4 4
3 10
2 5 25
4 9
1 7 3
10 4
10 2 8
7 1
1 1 5
6 8
3 1 48
10 6
2 5 26
3 3
3 2 8
7 7
3 4 29
10 7
1 2 60
9 7
6 6 50
8 3
3 3 7
9 1
8 1 1
7 10
4 3 60
9 5
3 5 4
2 6
1 2 2
9 8
6 1 51
1 4
1 2 3
6 1
4 1 4
3 2
3 1 1
10 3
6 3 24
6 3
5 3 13
3 6
...

output:

Yes
#######
#.....#
#...###
#.....#
#.....#
#.....#
#######
No
Yes
########
.......#
.......#
#......#
#......#
#......#
########
Yes
##.
Yes
..#
...
...
...
...
No
Yes
..........
..........
.....#####
No
No
Yes
.
.
.
.
.
#
#
Yes
........
........
........
........
........
........
Yes
######
#.......

result:

ok Correct, #(YES) = 24094, #(NO) = 8759, sum(nm) = 1000000 (32853 test cases)

Test #9:

score: 0
Accepted
time: 46ms
memory: 3712kb

input:

33193
1 1
1 1 1
4 10
3 9 10
10 1
7 1 9
4 6
2 2 18
8 10
8 1 53
7 3
2 1 15
10 8
10 5 68
8 9
8 7 26
5 3
5 2 7
5 3
4 2 15
10 10
10 8 56
2 9
1 1 15
8 8
1 6 6
2 2
1 1 4
5 9
3 2 33
9 3
4 3 23
3 9
2 6 12
7 7
4 6 29
4 7
2 1 7
7 2
4 2 7
3 7
2 5 4
5 8
4 6 31
5 9
1 7 23
7 1
5 1 2
4 2
4 1 3
4 1
1 1 4
4 9
4 5 29
...

output:

Yes
.
No
Yes
#
.
.
.
.
.
.
.
.
.
Yes
......
......
......
######
Yes
##########
#........#
#........#
#........#
#........#
#........#
#........#
.....#####
Yes
...
..#
..#
..#
..#
..#
..#
Yes
########
#......#
#......#
........
........
........
........
........
........
........
No
Yes
###
#.#
#....

result:

ok Correct, #(YES) = 24358, #(NO) = 8835, sum(nm) = 1000000 (33193 test cases)

Test #10:

score: 0
Accepted
time: 47ms
memory: 3712kb

input:

33163
9 1
1 1 2
10 9
5 4 72
10 1
8 1 2
1 10
1 2 10
6 8
3 3 22
7 4
7 3 26
2 5
2 4 7
8 9
3 8 25
8 7
6 5 10
8 4
1 1 26
3 4
3 2 12
2 5
2 3 9
1 5
1 4 3
9 7
7 5 26
2 4
1 1 7
9 3
1 1 5
7 1
5 1 1
5 1
3 1 5
8 9
2 1 60
1 10
1 6 9
2 1
1 1 1
1 7
1 2 4
4 4
3 4 11
10 2
3 1 17
10 7
3 4 11
2 7
1 3 14
10 1
8 1 7
10 ...

output:

Yes
.
.
#
#
#
#
#
#
#
Yes
.........
.........
.........
.........
........#
#.......#
#.......#
#.......#
#.......#
#########
No
Yes
..........
Yes
########
#......#
##....##
#......#
#......#
########
Yes
##..
....
....
....
....
....
....
Yes
...##
....#
No
No
Yes
....
....
....
....
....
....
#.....

result:

ok Correct, #(YES) = 24404, #(NO) = 8759, sum(nm) = 1000000 (33163 test cases)

Test #11:

score: 0
Accepted
time: 49ms
memory: 3584kb

input:

33164
9 10
5 4 66
7 4
4 4 2
7 9
2 4 11
8 3
2 1 19
7 4
1 2 3
5 5
3 3 13
10 7
5 5 40
6 8
3 7 23
4 2
3 1 7
8 6
5 5 29
7 6
5 6 36
1 6
1 6 1
7 4
3 2 12
1 4
1 1 4
7 10
1 7 52
3 10
2 7 26
8 3
2 3 4
3 3
1 2 4
6 6
5 6 9
7 6
6 6 3
2 9
2 8 13
3 8
1 7 21
8 9
7 5 71
5 10
2 7 1
5 3
1 3 7
6 2
5 2 12
4 6
4 2 2
1 4
...

output:

Yes
..........
#........#
#........#
#........#
#........#
#........#
#........#
#........#
##########
No
No
Yes
...
...
...
..#
..#
..#
..#
..#
No
Yes
....#
#...#
#...#
#...#
#####
Yes
#######
#.....#
#.....#
#.....#
#.....#
#.....#
#.....#
#.....#
#.....#
#######
Yes
########
#......#
##.....#
#.....

result:

ok Correct, #(YES) = 24467, #(NO) = 8697, sum(nm) = 1000000 (33164 test cases)

Test #12:

score: 0
Accepted
time: 21ms
memory: 3840kb

input:

1568
39 2
6 2 2
45 34
33 9 543
18 42
18 8 402
27 38
8 2 417
12 19
8 17 170
2 4
2 1 5
49 21
2 14 981
32 6
31 6 14
26 19
16 5 133
50 40
31 37 815
50 33
12 16 1276
27 48
1 21 802
4 28
4 17 8
14 31
6 18 204
9 4
4 3 13
34 49
9 38 1254
31 11
18 6 279
33 10
7 9 317
15 9
13 4 36
30 49
23 36 1156
46 16
39 6 ...

output:

No
No
Yes
##########################################
#........................................#
#........................................#
#...................................######
#........................................#
#.########################################
#..................................

result:

ok Correct, #(YES) = 904, #(NO) = 664, sum(nm) = 1000000 (1568 test cases)

Test #13:

score: 0
Accepted
time: 21ms
memory: 3712kb

input:

1562
9 46
3 22 390
22 17
20 10 323
7 40
1 7 45
44 19
18 11 676
7 47
3 8 248
10 25
5 11 61
25 50
25 3 465
40 35
26 12 277
27 30
18 21 712
37 6
4 1 128
10 22
7 1 168
11 35
2 21 339
20 41
15 23 144
21 8
15 5 108
11 37
10 29 1
14 9
12 9 2
32 13
9 5 232
47 23
23 3 240
49 14
14 12 99
28 7
2 4 100
19 40
13...

output:

Yes
..............................................
..............................................
..............................................
..............................................
..............................................
..............................................
.................

result:

ok Correct, #(YES) = 868, #(NO) = 694, sum(nm) = 1000000 (1562 test cases)

Test #14:

score: 0
Accepted
time: 22ms
memory: 3712kb

input:

1534
37 37
19 13 958
45 1
44 1 6
47 38
16 9 1288
11 33
5 12 253
5 33
5 22 134
19 46
7 14 302
43 20
40 5 175
44 19
13 7 279
20 44
20 30 728
17 21
16 20 54
36 28
33 13 816
50 26
12 1 1066
23 13
11 13 190
37 47
15 3 1116
10 27
1 20 30
49 7
6 6 267
28 23
7 15 463
19 41
9 32 63
37 30
13 23 880
19 15
11 5...

output:

Yes
#####################################
#...................................#
############.########################
#...................................#
############.########################
#...................................#
############.########################
#................................

result:

ok Correct, #(YES) = 911, #(NO) = 623, sum(nm) = 1000000 (1534 test cases)

Test #15:

score: 0
Accepted
time: 21ms
memory: 3840kb

input:

1554
11 31
9 8 171
14 30
13 29 370
40 31
17 21 259
24 6
6 2 114
8 10
8 1 53
27 13
10 3 183
20 48
20 37 68
48 49
32 26 794
25 13
5 3 157
5 33
4 29 135
50 30
30 18 756
42 9
39 1 321
38 18
23 18 646
2 32
1 11 32
5 9
3 2 33
29 13
26 6 38
33 29
20 1 33
37 17
10 9 158
24 47
10 8 1015
17 32
7 32 105
23 27
...

output:

Yes
###############################
#.............................#
#######.......................#
#.............................#
#######.#######################
#.............................#
#######.#######################
#.............................#
#######.#######################
#..........

result:

ok Correct, #(YES) = 897, #(NO) = 657, sum(nm) = 1000000 (1554 test cases)

Test #16:

score: 0
Accepted
time: 18ms
memory: 3840kb

input:

1491
39 21
4 15 272
40 9
15 4 72
30 21
18 15 242
41 20
14 12 790
6 38
3 13 142
47 34
34 9 1178
42 15
10 4 37
48 29
43 13 361
18 27
10 15 154
38 44
35 37 1402
13 24
5 18 216
22 45
22 8 209
41 35
14 14 1103
9 17
7 1 44
12 4
11 1 15
9 23
1 23 185
37 31
17 17 345
5 31
3 30 55
8 9
2 1 60
11 40
8 6 9
42 1...

output:

No
No
No
Yes
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
.................

result:

ok Correct, #(YES) = 845, #(NO) = 646, sum(nm) = 1000000 (1491 test cases)

Test #17:

score: 0
Accepted
time: 22ms
memory: 3840kb

input:

1531
9 20
5 14 66
17 34
7 14 208
27 19
5 8 29
8 43
2 32 291
47 24
23 2 943
5 5
3 3 13
10 47
5 13 440
6 8
3 7 23
14 42
9 41 491
18 6
3 5 77
27 26
6 14 672
11 36
4 24 271
7 44
3 26 264
21 44
2 17 272
7 40
1 37 122
43 30
8 27 266
38 33
32 12 496
23 3
18 2 28
46 26
23 14 789
47 6
15 6 207
12 29
8 14 181...

output:

No
No
No
Yes
...........................................
...........................................
#.........................................#
#.........................................#
#.........................................#
#.........................................#
#.........................

result:

ok Correct, #(YES) = 911, #(NO) = 620, sum(nm) = 1000000 (1531 test cases)

Test #18:

score: 0
Accepted
time: 22ms
memory: 3840kb

input:

1549
37 22
18 20 762
36 22
27 4 269
17 16
2 6 204
25 23
2 17 368
46 2
31 1 20
14 26
14 13 243
36 18
2 4 395
7 42
7 15 36
11 10
4 3 11
1 17
1 1 5
45 31
39 26 1307
45 27
20 14 190
10 11
5 2 105
32 33
22 3 474
13 26
8 3 12
24 40
2 14 14
35 40
30 8 779
45 24
31 5 557
34 38
10 27 855
49 14
23 10 636
43 3...

output:

Yes
......................
......................
......................
......................
......................
......................
......................
......................
......................
......................
......................
......................
.......................

result:

ok Correct, #(YES) = 912, #(NO) = 637, sum(nm) = 1000000 (1549 test cases)

Test #19:

score: 0
Accepted
time: 20ms
memory: 3840kb

input:

1509
15 13
11 9 192
9 43
1 15 160
7 10
7 9 11
42 38
5 22 613
48 33
5 3 1481
30 40
29 36 537
12 34
5 27 183
11 18
8 1 145
12 25
5 18 128
39 29
33 27 777
4 21
3 7 44
33 14
20 8 310
21 20
3 18 3
47 18
30 3 362
8 9
5 3 49
4 46
1 31 161
35 42
12 34 574
9 34
3 15 36
18 9
5 7 84
36 23
2 1 38
16 19
10 7 50
...

output:

Yes
###..........
.............
.............
.............
.............
.............
.............
.............
.............
.............
.............
.............
.............
.............
.............
No
No
No
Yes
.................................
.................................
........

result:

ok Correct, #(YES) = 861, #(NO) = 648, sum(nm) = 1000000 (1509 test cases)

Test #20:

score: 0
Accepted
time: 21ms
memory: 3840kb

input:

1521
39 7
23 4 143
36 30
11 21 65
50 50
45 46 1658
9 10
1 9 70
39 11
11 6 93
46 11
42 4 405
30 12
22 3 292
15 2
4 2 21
5 43
1 38 157
22 36
17 33 525
26 27
8 23 358
18 5
8 2 6
25 37
18 25 799
5 45
3 44 133
7 49
7 41 320
34 44
34 4 637
40 2
17 2 17
31 6
29 2 165
6 13
5 13 45
34 39
27 27 510
35 39
29 3...

output:

Yes
#######
#.....#
#.....#
#.....#
#.....#
#.....#
#.....#
#.....#
#.....#
#.....#
#.....#
#.....#
#.....#
#.....#
#.....#
#.....#
###...#
#.....#
###.###
#.....#
###.###
#.....#
###.###
#.....#
###.###
#.....#
###.###
#.....#
###.###
#.....#
###.###
#.....#
###.###
#.....#
###.###
#.....#
###.###
...

result:

ok Correct, #(YES) = 876, #(NO) = 645, sum(nm) = 1000000 (1521 test cases)

Test #21:

score: 0
Accepted
time: 22ms
memory: 3840kb

input:

1611
18 18
9 15 189
12 17
11 14 122
13 37
10 12 174
37 47
2 15 1518
50 12
3 2 356
28 34
3 11 232
37 46
29 21 1526
22 48
4 37 298
49 22
27 19 157
40 8
29 2 135
5 23
5 11 18
18 20
3 1 250
16 12
4 6 76
12 31
12 14 140
29 17
27 5 1
13 38
2 28 270
22 11
21 8 25
40 41
28 26 289
35 41
4 8 713
15 18
15 13 2...

output:

Yes
##################
#................#
##############.###
#................#
##############.###
#................#
##############.###
#................#
##############.###
#................#
######.........###
#................#
#................#
#................#
#................#
#.............

result:

ok Correct, #(YES) = 966, #(NO) = 645, sum(nm) = 1000000 (1611 test cases)

Test #22:

score: 0
Accepted
time: 0ms
memory: 5248kb

input:

1
1 1000000
1 154393 198552

output:

Yes
...........................................................................................................................................................................................................................................................................................................

result:

ok Correct, #(YES) = 1, #(NO) = 0, sum(nm) = 1000000 (1 test case)

Test #23:

score: 0
Accepted
time: 21ms
memory: 35640kb

input:

1
1000000 1
237817 1 837572

output:

Yes
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...

result:

ok Correct, #(YES) = 1, #(NO) = 0, sum(nm) = 1000000 (1 test case)

Test #24:

score: 0
Accepted
time: 1ms
memory: 5120kb

input:

1
1 1000000
1 821241 866722

output:

Yes
########################################################################################################################################################################################################################################################################################################...

result:

ok Correct, #(YES) = 1, #(NO) = 0, sum(nm) = 1000000 (1 test case)

Test #25:

score: 0
Accepted
time: 28ms
memory: 35512kb

input:

1
1000000 1
937369 1 243235

output:

Yes
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
#
...

result:

ok Correct, #(YES) = 1, #(NO) = 0, sum(nm) = 1000000 (1 test case)

Extra Test:

score: 0
Extra Test Passed