1
void solve() {
2
  string s;
3
  cin >> s;
4
  regex ss("^21[34]\\d{2}(?!0000)\\d{4}$");
5
  if (regex_match(s, ss)) {
6
    cout << "YES" << endl;
7
  } else {
8
    cout << "NO" << endl;
9
  }
10
}

1
void solve() {
2
    int n, m;
3
    cin >> n >> m;
4
    vector<string> a(n);
5
    for (int i = 0; i < n; i++) cin >> a[i];
6

7
    const int mod = 998244353;
8

9
    auto process = [&](vector<tuple<int, int, int, int, int, int>> lim, int n, int m) -> int {
10
        int ans = 0;
11
        auto check = [&](int s, int t, int l, int r) -> int {
12
            return l <= s && r <= t && s <= r;
13
        };
14
        int flag1 = 1;
15
        int flag2 = 1;
16
        int last = 0;
17
        for (int i = 0; i < lim.size(); i++) {
18
            auto [left, right, left_inner, right_inner, all_r, all_g] = lim[i];
19
            if (!all_g) last = i + 1;
20
        }
21
        vector<vector<int>> f(m, vector<int>(m));
22
        for (int i = 0; i < lim.size(); i++) {
23
            auto [left, right, left_inner, right_inner, all_r, all_g] = lim[i];
24

25
            vector<vector<int>> tf(m, vector<int>(m));
26
            for (int l1 = 0; l1 < m; l1++) {
27
                for (int r1 = l1; r1 < m; r1++) {
28
                    //l1 <= r2 <= r1
29
                    //l2 <= l1
30
                    (tf[l1][r1] += f[l1][r1]) %= mod;
31
                    if (l1) (tf[l1][l1 - 1] -= f[l1][r1]) %= mod;
32
                }
33
            }
34
            for (int l = m - 1; l >= 0; l--) {
35
                for (int r = m - 1; r >= 0; r--) {
36
                    if (l + 1 < m) (tf[l][r] += tf[l + 1][r]) %= mod;
37
                    if (r + 1 < m) (tf[l][r] += tf[l][r + 1]) %= mod;
38
                    if (max(l, r) + 1 < m) (tf[l][r] -= tf[l + 1][r + 1]) %= mod;
39
                }
40
            }
41
            for (int l = 0; l < m; l++) {
42
                for (int r = l; r < m; r++) {
43
                    if (left <= l && l <= left_inner && right_inner <= r && r <= right) {
44

45
                    } else {
46
                        tf[l][r] = 0;
47
                    }
48
                }
49
            }
50
            if (flag1) {
51
                for (int l = left; l <= left_inner; l++) {
52
                    for (int r = max(l, right_inner); r <= right; r++) {
53
                        if (i && r + 1 < m) continue;
54
                        tf[l][r]++;
55
                        tf[l][r] %= mod;
56
                    }
57
                }
58
            }
59
            if (i + 1 >= last) {
60
                for (int l = 0; l < m; l++) {
61
                    for (int r = l; r < m; r++) {
62
                        if (i + 1 < n && l) continue;
63
                        ans += tf[l][r];
64
                        ans %= mod;
65
                    }
66
                }
67
            }
68
            flag1 &= all_r;
69
            flag2 &= all_g;
70
            f.swap(tf);
71
        }
72
        //out2(flag1, flag2);
73
        ans += flag1 + flag2;
74
        ans %= mod;
75
        ans += mod;
76
        ans %= mod;
77
        return ans;
78
    };
79
    auto solve_row = [&]() -> void {
80
        vector<tuple<int, int, int, int, int, int>> ans;
81
        for (int i = 0; i < m; i++) {
82
            int left = 0, right = n - 1;
83
            int left_inner = n - 1, right_inner = 0;
84
            int flag = 0;
85
            for (int j = 0; j < n; j++) {
86
                if (a[j][i] != '?') {
87
                    if (a[j][i] == '0') {
88
                        if (!flag) {
89
                            left_inner = right_inner = j;
90
                        } else {
91
                            right_inner = j;
92
                        }
93
                        flag = 1;
94
                    } else if (a[j][i] == '1') {
95
                        left = max(left, j + 1);
96
                    } else if (a[j][i] == '2') {
97
                        right = min(right, j - 1);
98
                    }
99
                }
100
            }
101
            ans.emplace_back(left, right, left_inner, right_inner, !flag && right == n - 1, !flag && left == 0);
102
        }
103
        cout << process(ans, m, n) << '\n';
104
    };
105
    auto solve_col = [&]() -> void {
106
        vector<tuple<int, int, int, int, int, int>> ans;
107
        for (int i = 0; i < n; i++) {
108
            int left = 0, right = m - 1;
109
            int left_inner = m - 1, right_inner = 0;
110
            int flag = 0;
111
            for (int j = 0; j < m; j++) {
112
                if (a[i][j] != '?') {
113
                    if (a[i][j] == '0') {
114
                        if (!flag) {
115
                            left_inner = right_inner = j;
116
                        } else {
117
                            right_inner = j;
118
                        }
119
                        flag = 1;
120
                    } else if (a[i][j] == '1') {
121
                        left = max(left, j + 1);
122
                    } else if (a[i][j] == '2') {
123
                        right = min(right, j - 1);
124
                    }
125
                }
126
            }
127
            ans.emplace_back(left, right, left_inner, right_inner, !flag && right == m - 1, !flag && left == 0);
128
        }
129
        cout << process(ans, n, m) << '\n';
130
    };
131
    if (m <= n) solve_col();
132
    else solve_row();
133
}

1
vc<int> pr, vis, mn;
2
void init(int n) {
3
  vis.assign(n + 1, 0);
4
  mn.assign(n + 1, 0);
5
  for (int i = 2; i <= n; i++) {
6
    if (!vis[i]) pr += i, mn[i] = i;
7
    for (auto j : pr) {
8
      if (i * j > n) break;
9
      vis[i * j] = 1;
10
      mn[i * j] = j;
11
      if (i % j == 0) break;
12
    }
13
  }
14
}
15
const int mod = 998244353;
16
namespace MTool {
17
  inline int Cadd(int a, int b) {return (i64)a + b >= mod ? (i64)a + b - mod : a + b;}
18
  inline int Cdel(int a, int b) {return a - b < 0 ? a - b + mod : a - b;}
19
  inline int Cmul(int a, int b) {return 1ll * a * b % mod;}
20
  inline int sqr(int a) {return 1ll * a * a % mod;}
21
  inline void Madd(int &a, int b) {a = (i64)a + b >= mod ? (i64)a + b - mod : a + b;}
22
  inline void Mdel(int &a, int b) {a = a - b < 0 ? a - b + mod : a - b;}
23
  inline void Mmul(int &a, int b) {a = 1ll * a * b % mod;}
24
  inline int neg(int x) {return !x ? 0 : mod - x;}
25
  inline int norm(i64 x) {return (x % mod + mod) % mod;}
26
  template <typename ...Args> inline int Cadd(int a, int b, Args ...args) {return Cadd(Cadd(a, b), args...);}
27
  template <typename ...Args> inline int Cdel(int a, int b, Args ...args) {return Cdel(Cdel(a, b), args...);}
28
  template <typename ...Args> inline int Cmul(int a, int b, Args ...args) {return Cmul(Cmul(a, b), args...);}
29
  template <typename ...Args> inline void Madd(int &a, int b, Args ...args) {Madd(a, b), Madd(a, args...);}
30
  template <typename ...Args> inline void Mdel(int &a, int b, Args ...args) {Mdel(a, b), Mdel(a, args...);}
31
  template <typename ...Args> inline void Mmul(int &a, int b, Args ...args) {Mmul(a, b), Mmul(a, args...);}
32
  inline int ksm(int a, i64 b, int Mod = mod) {int ans = 1; for (; b; b >>= 1, a = 1ll * a * a % Mod) if (b & 1) ans = 1ll * ans * a % Mod; return ans;}
33
}
34
using namespace MTool;
35

36
vc<int> p, tim;
37
void ins(int x, int id) {
38
  for (int i = 5; i >= 0; i--) if (x >> i & 1) {
39
    if (!p[i]) {
40
      p[i] = x, tim[i] = id;
41
      return ;
42
    } else if (tim[i] < id) {
43
      swap(p[i], x), swap(tim[i], id);
44
    }
45
    x ^= p[i];
46
  }
47
}
48
vc<int> pw;
49

50
void solve() {
51
  int n, q;
52
  cin >> n >> q;
53
  vc<int> a(n);
54
  for (int i = 0, x; i < n; i++) {
55
    cin >> x;
56
    while (x != 1) {
57
      a[i]++;
58
      x /= mn[x];
59
    }
60
  }
61
  debug(a);
62

63
  vc<int> sum(n);
64
  for (int i = 0; i < n; i++)
65
    sum[i] = (i ? sum[i - 1] : 0) + (a[i] == 1);
66
  vc<int> rsum(n);
67
  for (int i = 0; i < n; i++)
68
    rsum[i] = (i ? rsum[i - 1] : 0) + (a[i] == 0);
69

70
  vc<int> ans(q);
71
  vc<vc<array<int, 2>>> ask(n);
72

73
  for (int i = 0; i < q; i++) {
74
    int l, r;
75
    cin >> l >> r;
76
    l--, r--;
77
    int rc = rsum[r] - (l ? rsum[l - 1] : 0), c = sum[r] - (l ? sum[l - 1] : 0);
78
    Madd(ans[i], pw[r - l + 1]);
79
    Mdel(ans[i], 1);
80
    if (!c) Madd(ans[i], Cdel(pw[rc], 1));
81
    else Mdel(ans[i], 1);
82
    ask[r] += {l, i};
83
  }
84
  p.assign(6, 0), tim.assign(6, -1);
85
  for (int i = 0; i < n; i++) {
86
    ins(a[i], i);
87
    for (auto [l, id] : ask[i]) {
88
      int c = 0;
89
      for (int j = 0; j <= 5; j++)
90
        if (tim[j] >= l) c++;
91
      Mdel(ans[id], Cdel(pw[i - l + 1 - c], 1));
92
    }
93
  }
94
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
95
}
96

97
void main01() {
98
  #ifdef LOCAL
99
  file("");
100
  #endif
101
  cin.tie(nullptr) -> sync_with_stdio(false);
102
  init(1e7);
103
  pw.resize(1000005);
104
  pw[0] = 1;
105
  for (int i = 1; i < sz(pw); i++) pw[i] = Cadd(pw[i - 1], pw[i - 1]);
106
  int t = 1;
107
  cin >> t;
108
  while (t--) solve();
109
}}
110
signed main() {return Anonyme::main01(), 0;}

1
void solve() {
2
  int n;
3
  cin >> n;
4
  V<int> a(n + 1);
5
  for (int i = 1; i <= n; i++) {
6
    cin >> a[i];
7
  }
8
  V<int> tmp = a;
9
  remDup(tmp);
10
  int d = tmp.size();
11
  auto get = [&](int x) {
12
    return (lower_bound(tmp.begin() + 1, tmp.end(), x) - (tmp.begin()));
13
  };
14
  for (int i = 1; i <= n; i++) {
15
    a[i] = get(a[i]);
16
  }
17
  V<V<int>> nxt(n + 2, V<int>(d + 1, n + 1));
18
  for (int v = 1; v <= d; v++) {
19
    nxt[n + 1][v] = n + 1;
20
  }
21
  for (int i = n; i >= 1; i--) {
22
    for (int v = 1; v <= d; v++) {
23
      nxt[i][v] = nxt[i + 1][v];
24
    }
25
    nxt[i][a[i]] = i;
26
  }
27
  V<int> dp(n + 2, 0);
28
  for (int i = n; i >= 1; i--) {
29
    dp[i] = dp[i + 1];
30
    int j = nxt[i + 1][a[i]];
31
    if (j <= n) {
32
      for (int b = 1; b <= d; b++) {
33
        int k = nxt[j + 1][b];
34
        if (k > n) {
35
          continue;
36
        }
37
        int l = nxt[k + 1][b];
38
        if (l > n) {
39
          continue;
40
        }
41
        dp[i] = max(dp[i], 1 + dp[l + 1]);
42
      }
43
    }
44
    for (int j = i + 1; j <= n; j++) {
45
      int k = nxt[j + 1][a[i]];
46
      if (k > n) {
47
        continue;
48
      }
49
      int l = nxt[k + 1][a[j]];
50
      if (l > n) {
51
        continue;
52
      }
53
      dp[i] = max(dp[i], 1 + dp[l + 1]);
54
    }
55
    for (int j = i + 1; j <= n; j++) {
56
      int k = nxt[j + 1][a[j]];
57
      if (k > n) {
58
        continue;
59
      }
60
      int l = nxt[k + 1][a[i]];
61
      if (l > n) {
62
        continue;
63
      }
64
      dp[i] = max(dp[i], 1 + dp[l + 1]);
65
    }
66
  }
67
  cout << dp[1] << endl;
68
}

1
void solve() {
2
    int n, m, q;
3
    n = read(), m = read(), q = read();
4
    vector<ll> r(n + 1);
5
    for (int i = 1; i <= n; i++) r[i] = read_ll();
6

7
    vector<vector<pair<int, int>>> g(n + 1);
8
    for (int i = 1; i <= m; i++) {
9
        int u, v, w;
10
        u = read(), v = read(), w = read();
11
        g[u].emplace_back(v, w);
12
        g[v].emplace_back(u, w);
13
    }
14

15
    {
16
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, less<pair<ll, int>>> q;
17
        for (int i = 1; i <= n; i++) q.push({r[i], i});
18

19

20
        while (!q.empty()) {
21
            auto [d, u] = q.top(); q.pop();
22
            if (r[u] != d) continue;
23
            for (auto [v, w] : g[u]) {
24
                if (d - w > r[v]) {
25
                    r[v] = d - w;
26
                    q.push({r[v], v});
27
                }
28
            }
29
        }
30
    }
31
    vector<ll> k(r);
32
    sort(k.begin(), k.end());
33
    k.erase(unique(k.begin(), k.end()), k.end());
34

35
    auto check = [&](int u, int v, ll f, int k) -> int {
36
        vector<int> dist(n + 1, infi);
37
        dist[u] = r[u] > f;
38
        deque<pair<int, int>> que;
39
        que.push_back({dist[u], u});
40

41
        while (!que.empty()) {
42
            auto [d, u] = que.front(); que.pop_front();
43
            if (dist[u] != d) continue;
44
            for (auto [v, _] : g[u]) {
45
                int w = r[v] > f;
46
                if (dist[v] > d + w) {
47
                    dist[v] = d + w;
48
                    if (w) que.push_back({dist[v], v});
49
                    else que.push_front({dist[v], v});
50
                }
51
            }
52
        }
53
        return dist[v] <= k;
54
    };
55

56
    while (q--) {
57
        int u, v, c;
58
        u = read(), v = read(), c = read();
59
        int left = 0, right = k.size() - 1;
60
        ll ans = -1;
61
        while (left <= right) {
62
            int mid = left + (right - left) / 2;
63
            if (check(u, v, k[mid], c)) {
64
                ans = k[mid];
65
                right = mid - 1;
66
            } else {
67
                left = mid + 1;
68
            }
69
        }
70
        Print(ans, '\n');
71
    }
72
    Write();
73
}

1
void solve() {
2
  int n, q;
3
  cin >> n >> q;
4

5
  vc<int> a(n);
6
  for (auto &x : a) cin >> x;
7
  set<array<int, 2>> s;
8
  for (int i = 0; i < n; i++) s.insert({a[i], i});
9

10
  vc<int> idx(n, -1);
11
  while (q--) {
12
    int op;
13
    cin >> op;
14
    if (op == 1) {
15
      int x, w;
16
      cin >> x >> w;
17
      x--;
18
      s.erase({a[x], x});
19
      a[x] = w;
20
      s.insert({a[x], x});
21
    } else {
22
      int u, v, k;
23
      cin >> u >> v >> k;
24
      u--, v--;
25

26
      vc<int> pos;
27
      pos += u, pos += v;
28
      idx[u] = 0, idx[v] = 1;
29
      for (auto [d, i] : s) if (i != u && i != v) {
30
        idx[i] = sz(pos), pos += i;
31
        if (sz(pos) == 12) break;
32
      }
33

34
      int m = sz(pos);
35
      vc<vc<int>> f(m, vc<int> (m, inf32));
36
      for (int i = 0; i < m; i++)
37
        for (int j = 0; j < m; j++)
38
          f[i][j] = min(a[pos[i]], a[pos[j]]);
39

40
      for (int i = 0; i < m; i++) f[i][i] = 0;
41
      for (int i = 0; i < k; i++) {
42
        int x, y;
43
        cin >> x >> y;
44
        x--, y--;
45
        if (idx[x] == -1 || idx[y] == -1) continue;
46
        f[idx[x]][idx[y]] = f[idx[y]][idx[x]] = inf32;
47
      }
48
      for (int i = 0; i < m; i++)
49
        for (int j = 0; j < m; j++)
50
          for (int k = 0; k < m; k++)
51
            ckmin(f[j][k], f[j][i] + f[i][k]);
52

53
      cout << f[0][1] << '\n';
54
      for (int i = 0; i < sz(pos); i++) idx[pos[i]] = -1;
55
    }
56
  }
57
}

1
void solve() {
2
  int n;
3
  cin >> n;
4
  V<V<int>> b(n, V<int>(n, 0));
5
  int cnt = 0;
6
  for (auto &x : b) {
7
    cin >> x;
8
  }
9
  for (auto &x : b) {
10
    for (auto &y : x) {
11
      if (y == 0) {
12
        cnt++;
13
      }
14
    }
15
  }
16
  int maxx = div<int>(n * n, 2, flase);
17
  int ok = (cnt <= maxx ? 1 : 0);
18
  for (auto &x : b) {
19
    for (auto &y : x) {
20
      if ((ok and y == 0) or (ok == 0 and y)) {
21
        y = ok;
22
      }
23
    }
24
  }
25
  for (auto &x : b) {
26
    cout << x << endl;
27
  }
28
}

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4

5
const int MAXN = 800 * 3;
6
const i64 INF = 1e18;
7

8
struct Edge {
9
    int to, cap, cost, rev;
10
};
11

12
vector<Edge> G[MAXN];
13
i64 dist[MAXN];
14
int prevv[MAXN], preve[MAXN];
15

16
// 添加边的函数
17
void add_edge(int from, int to, int cap, int cost) {
18
    G[from].push_back({to, cap, cost, (int)G[to].size()});
19
    G[to].push_back({from, 0, -cost, (int)G[from].size() - 1});
20
}
21

22
// 求解最大费用流
23
pair<int, i64> min_cost_flow(int s, int t, int f) {
24
    int flow = 0;
25
    i64 cost = 0;
26
    while (flow < f) {
27
        fill(dist, dist + MAXN, -INF);
28
        dist[s] = 0;
29
        bool update = true;
30
        while (update) {
31
            update = false;
32
            for (int v = 0; v < MAXN; v++) {
33
                if (dist[v] == -INF) continue;
34
                for (int i = 0; i < G[v].size(); i++) {
35
                    Edge &e = G[v][i];
36
                    if (e.cap > 0 && dist[e.to] < dist[v] + e.cost) {
37
                        dist[e.to] = dist[v] + e.cost;
38
                        prevv[e.to] = v;
39
                        preve[e.to] = i;
40
                        update = true;
41
                    }
42
                }
43
            }
44
        }
45

46
        if (dist[t] == -INF) {
47
            return {flow, cost};
48
        }
49

50
        int d = f - flow;
51
        for (int v = t; v != s; v = prevv[v]) {
52
            d = min(d, G[prevv[v]][preve[v]].cap);
53
        }
54

55
        for (int v = t; v != s; v = prevv[v]) {
56
            Edge &e = G[prevv[v]][preve[v]];
57
            e.cap -= d;
58
            G[v][e.rev].cap += d;
59
            cost += 1ll * d * e.cost;
60
        }
61
        flow += d;
62
    }
63
    return {flow, cost};
64
}
65

66
int main() {
67
    cin.tie(nullptr)->sync_with_stdio(false);
68

69
    int t;
70
    cin >> t;
71
    while (t--) {
72
        int n, m;
73
        cin >> n >> m;
74
        i64 ans = 0;
75
        vector<int> a(n + 1), x = a, y = a, z = a;
76
        for (int i = 1; i <= n; i++) {
77
            cin >> a[i];
78
        }
79
        for (int i = 1; i <= n; i++) {
80
            cin >> x[i];
81
        }
82
        for (int i = 1; i <= n; i++) {
83
            cin >> y[i];
84
            ans -= y[i];
85
            x[i] += y[i];
86
        }
87
        for (int i = 1; i <= n; i++) {
88
            cin >> z[i];
89
        }
90
        int tot = 0;
91
        vector<vector<int>> id(n + 1, vector<int>(n + 1));
92
        for (int i = 1; i <= n; i++) {
93
            id[i] = id[i - 1];
94
            id[i][0] = ++tot;
95
            id[i][a[i]] = ++tot;
96
            add_edge(id[i][a[i]], id[i][0], 1, 0);
97
            add_edge(id[i][0], id[i][a[i]], 1, -z[i]);
98
            if (i > 1) {
99
                add_edge(id[i - 1][0], id[i][0], m, 0);
100
                add_edge(id[i - 1][a[i]], id[i][a[i]], 1, x[i]);
101
            }
102
        }
103
        cout << ans + min_cost_flow(id[1][0], id[n][0], m).second << '\n';
104
        for (int i = 1; i <= tot; i++) {
105
            G[i].clear();
106
        }
107
    }
108
}
109
/*
110
1
111
2 2
112
1 2
113
1 1
114
0 0
115
0 0
116
*/

1
void solve() {
2
  int n, m;
3
  cin >> n >> m;
4
  V<string> a(n);
5
  cin >> a;
6
  V<int> avi(n, 0);
7
  for (int i = 0; i < n; i++) {
8
    int so = 0;
9
    for (int j = 0; j < m; j++) {
10
      if (a[i][j] == 'Y') {
11
        so |= (1 << j);
12
      }
13
    }
14
    avi[i] = so;
15
  }
16
  V<V<int>> valid(n);
17
  V<V<int>> cnt(n);
18
  for (int i = 0; i < n; i++) {
19
    for (int j = 0; j < (1 << m); j++) {
20
      if ((j & avi[i]) != j) {
21
        continue;
22
      }
23
      if (j & (j << 1)) {
24
        continue;
25
      }
26
      valid[i].pb(j);
27
    }
28
  }
29
  int lim = (1 << m);
30
  V<V<int>> dp(n, V<int>(lim, -1));
31
  for (auto x : valid[0]) {
32
    dp[0][x] = __builtin_popcount(x);
33
  }
34
  for (int i = 1; i < n; i++) {
35
    for (auto &x : valid[i]) {
36
      int cur = __builtin_popcount(x);
37
      for (auto &y : valid[i - 1]) {
38
        if (dp[i - 1][y] < 0) {
39
          continue;
40
        }
41
        if (x & y) {
42
          continue;
43
        }
44
        dp[i][x] = max(dp[i][x], dp[i - 1][y] + cur);
45
      }
46
    }
47
  }
48

49
  int ans = 0;
50
  for (int i = 0; i < lim; i++) {
51
    ckmax(ans, dp[n-1][i]);
52
  }
53
  cout << ans << endl;
54
}

1
#include <bits/stdc++.h>
2
using namespace std;
3
using i64 = long long;
4

5

6

7
int main() {
8
    cin.tie(nullptr)->sync_with_stdio(false);
9

10
    // ifstream cin;
11
    // cin.open("0.in");
12
    int n, m;
13
    cin >> n >> m;
14
    vector a(n, vector(m, int(0)));
15
    for (auto &t : a) {
16
        string s;
17
        cin >> s;
18
        for (int j = 0; j < m; j++) {
19
            t[j] = s[j] - '0';
20
        }
21
    }
22
    // cin.close();
23
    vector<int> fa(n * m), siz(n * m, 1);
24
    iota(fa.begin(), fa.end(), 0);
25
    auto find = [&](auto &find, int x) -> int {
26
        if (x == fa[x]) return x;
27
        return fa[x] = find(find, fa[x]);
28
    };
29
    auto id = [&](int x, int y) -> int {
30
        return x * m + y;
31
    };
32
    for (int i = 0; i < n; i++) {
33
        for (int j = 0; j < m; j++) {
34
            if (!a[i][j]) continue;
35
            if (i and a[i - 1][j]) {
36
                int fx = find(find, id(i - 1, j));
37
                int fy = find(find, id(i, j));
38
                if (fx == fy) continue;
39
                fa[fy] = fx;
40
                siz[fx] += siz[fy];
41
            }
42
            if (j and a[i][j - 1]) {
43
                int fx = find(find, id(i, j - 1));
44
                int fy = find(find, id(i, j));
45
                if (fx == fy) continue;
46
                fa[fy] = fx;
47
                siz[fx] += siz[fy];
48
            }
49
        }
50
    }
51
    string ans;
52
    for (int j = 0; j < m; j++) {
53
        for (int i = 0; i < n; i++) {
54
            if (!a[i][j]) continue;
55
            int cur = id(i, j);
56
            if (find(find, cur) != cur) continue;
57
            if (siz[cur] <= n * 2) continue;
58
            if (siz[cur] >= n * 15) ans.push_back('0');
59
            else ans.push_back('1');
60
        }
61
    }
62
    cout << ans << '\n';
63
}
64
/*
65
*/