#374652 (C++14) No.861 ケーキカット

提出ソース
結果

問題	No.861 ケーキカット
ユーザー	fine
提出日時	2019-09-01 00:47:06
言語	C++14 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	13 ms / 1,000 ms
コード長	46,326 bytes
コンパイル時間	1,455 ms
コンパイル使用メモリ	171,348 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-07 19:07:10
合計ジャッジ時間	2,353 ms
ジャッジサーバーID （参考情報）	judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 21
権限があれば一括ダウンロードができます
ソースコード

raw source code
プレゼンテーションモードにする

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct UnionFind {
    vector<int> data;
    int num;
    UnionFind(int sz) : num(sz), data(sz, -1) {}
    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        bool is_union = (x != y);
        if (is_union) {
            if (data[x] > data[y]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
            num--;
        }
        return is_union;
    }
    int find(int x) {
        if (data[x] < 0) { //要素xが根である
            return x;
        } else {
            data[x] = find(data[x]); //data[x]がxの属する集合の根でない場合、根になるよう更新される
            return data[x];
        }
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        return -data[find(x)];
    }
};
const int dh[] = {1, -1, 0, 0};
const int dw[] = {0, 0, 1, -1};
int masks[16213] = {0,1,2,4,8,1,1,2,4,8,2,2,4,8,1,1,2,4,8,4,4,8,4,4,8,2,2,4,8,1,1,2,4,8,8,8,8,8,8,8,8,8,4,4,8,4,4,8,2,2,4,8,1,1,2,4,8,16,16,16,16,16
    ,16,16,16,16,16,16,16,16,16,16,16,17,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,34,2,4,8,1,1,2,4,8
    ,34,2,4,8,1,1,2,4,8,40,8,8,8,34,2,4,8,1,1,2,4,8,48,16,48,16,48,16,48,16,17,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,68
    ,4,8,4,4,8,2,2,4,8,1,1,2,4,8,68,4,8,4,4,8,2,2,4,8,1,1,2,4,8,80,16,16,16,80,16,16,16,84,4,8,17,1,2,4,8,84,4,8,17,1,2,4,8,96,32,96,32,34,2,4,8,1,1,2
    ,4,8,4,4,8,18,2,4,8,1,1,2,4,8,68,4,8,18,2,4,8,1,1,2,4,8,48,16,16,32,16,80,32,16,17,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,136
    ,8,8,8,8,8,8,8,4,4,8,4,4,8,2,2,4,8,1,1,2,4,8,144,16,16,16,16,16,16,16,152,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,168,8,8,8,34,2,4,8,1,1,2,4,8,176
    ,16,48,16,152,8,24,8,49,1,2,4,8,160,32,64,68,4,8,4,4,8,2,2,4,8,1,1,2,4,8,8,8,8,8,36,4,8,4,4,8,2,2,4,8,1,1,2,4,8,144,16,48,16,16,16,84,4,8,17,1,2,4
    ,8,24,8,52,4,8,17,1,2,4,8,160,64,32,34,2,4,8,1,1,2,4,8,4,4,8,18,2,4,8,1,1,2,4,8,8,8,18,15,1,18,4,8,18,2,4,8,1,1,2,4,8,144,64,32,16,17,1,2,4,8,17,1
    ,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,272,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,304,16,48,16,48,16,48
    ,16,288,32,64,32,32,64,336,16,16,16,80,16,16,16,352,32,96,32,304,16,16,32,16,80,32,16,288,32,64,128,272,16,16,16,80,16,16,16,16,16,16,16,288,32,96
    ,32,32,32,304,16,112,16,48,16,288,32,96,32,64,272,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512,529,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4
    ,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,596,4,8,17,1,2,4,8
    ,84,4,8,17,1,2,4,8,96,32,96,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,664,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,664,8,24
    ,8,49,1,2,4,8,160,32,64,596,4,8,17,1,2,4,8,24,8,52,4,8,17,1,2,4,8,160,64,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,800
    ,32,32,32,32,32,32,32,800,32,64,32,32,64,864,32,96,32,800,32,64,128,800,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,1058,2,4,8,1,1,2,4,8,34
    ,2,4,8,1,1,2,4,8,40,8,8,8,34,2,4,8,1,1,2,4,8,48,16,48,16,48,16,48,16,17,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,1058
    ,2,4,8,1,1,2,4,8,4,4,8,18,2,4,8,1,1,2,4,8,68,4,8,18,2,4,8,1,1,2,4,8,48,16,16,32,16,80,32,16,17,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32
    ,32,64,128,1192,8,8,8,34,2,4,8,1,1,2,4,8,176,16,48,16,152,8,24,8,49,1,2,4,8,160,32,64,1058,2,4,8,1,1,2,4,8,4,4,8,18,2,4,8,1,1,2,4,8,8,8,18,15,1,18
    ,4,8,18,2,4,8,1,1,2,4,8,144,64,32,16,17,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,1328,16,48,16,48,16,48,16,288,32,64,32,32,64
    ,1328,16,16,32,16,80,32,16,288,32,64,128,1328,16,112,16,48,16,288,32,96,32,64,1296,128,64,32,16,512,529,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8
    ,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,1553,1,2,4,8,17,1,2,4,8
    ,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,664,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,664,8,24,8,49,1,2,4,8,160,32,64,1553,1,2,4,8,17,1,2,4,8,17,32
    ,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,800,32,32,32,32,32,32,32,800,32,64,32,32,64,1824,32,64,128,800,32,96,32,32,32,800,32,96,32,64,2048,2116,4,8,4
    ,4,8,2,2,4,8,1,1,2,4,8,68,4,8,4,4,8,2,2,4,8,1,1,2,4,8,80,16,16,16,80,16,16,16,84,4,8,17,1,2,4,8,84,4,8,17,1,2,4,8,96,32,96,32,34,2,4,8,1,1,2,4,8,4
    ,4,8,18,2,4,8,1,1,2,4,8,68,4,8,18,2,4,8,1,1,2,4,8,48,16,16,32,16,80,32,16,17,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,2116,4,8
    ,4,4,8,2,2,4,8,1,1,2,4,8,8,8,8,8,36,4,8,4,4,8,2,2,4,8,1,1,2,4,8,144,16,48,16,16,16,84,4,8,17,1,2,4,8,24,8,52,4,8,17,1,2,4,8,160,64,32,34,2,4,8,1,1
    ,2,4,8,4,4,8,18,2,4,8,1,1,2,4,8,8,8,18,15,1,18,4,8,18,2,4,8,1,1,2,4,8,144,64,32,16,17,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256
    ,2384,16,16,16,80,16,16,16,352,32,96,32,304,16,16,32,16,80,32,16,288,32,64,128,2320,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512,2644
    ,4,8,17,1,2,4,8,84,4,8,17,1,2,4,8,96,32,96,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,2644,4,8,17,1,2,4,8,24,8,52,4,8,17,1
    ,2,4,8,160,64,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,2912,32,96,32,800,32,64,128,2848,128,64,32,1024,1058,2,4,8,1,1,2
    ,4,8,34,2,4,8,1,1,2,4,8,40,8,8,8,34,2,4,8,1,1,2,4,8,48,16,48,16,48,16,48,16,17,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32
    ,64,68,4,8,4,4,8,2,2,4,8,1,1,2,4,8,68,4,8,4,4,8,2,2,4,8,1,1,2,4,8,80,16,16,16,80,16,16,16,546,2,4,8,1,1,2,4,8,4,4,8,18,2,4,8,1,1,2,4,8,68,4,8,18,2
    ,4,8,1,1,2,4,8,48,16,16,32,16,80,32,16,17,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,2116,4,8,4,4,8,2,2,4,8,1,1,2,4,8,8,8,8,8,36
    ,4,8,4,4,8,2,2,4,8,1,1,2,4,8,144,16,48,16,16,16,546,2,4,8,1,1,2,4,8,4,4,8,18,2,4,8,1,1,2,4,8,8,8,18,15,1,18,4,8,18,2,4,8,1,1,2,4,8,144,64,32,16,17
    ,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,1328,16,48,16,48,16,48,16,288,32,64,32,32,64,336,16,16,16,80,16,16,16,816,16,16,32
    ,16,80,32,16,288,32,64,128,2320,16,112,16,48,16,16,16,784,128,64,32,16,512,529,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32
    ,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,529,1,2,4,8,49,128,79,753,1,2,4,8,17,1,2,4,8,17,32
    ,1,2,4,8,81,32,1,2,4,8,32,32,64,128,2577,1,2,4,8,49,64,1,63,832,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,800,32,32,32,32,32,32
    ,32,800,32,64,32,32,64,800,1024,32,64,128,4096,4232,8,8,8,8,8,8,8,4,4,8,4,4,8,2,2,4,8,1,1,2,4,8,144,16,16,16,16,16,16,16,152,8,24,8,20,4,8,17,1,2
    ,4,8,160,32,32,32,168,8,8,8,34,2,4,8,1,1,2,4,8,176,16,48,16,152,8,24,8,49,1,2,4,8,160,32,64,68,4,8,4,4,8,2,2,4,8,1,1,2,4,8,8,8,8,8,36,4,8,4,4,8,2
    ,2,4,8,1,1,2,4,8,144,16,48,16,16,16,84,4,8,17,1,2,4,8,24,8,52,4,8,17,1,2,4,8,160,64,32,34,2,4,8,1,1,2,4,8,4,4,8,18,2,4,8,1,1,2,4,8,8,8,18,15,1,18
    ,4,8,18,2,4,8,1,1,2,4,8,144,64,32,16,17,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,4368,16,16,16,80,16,16,16,16,16,16,16,288,32
    ,96,32,32,32,304,16,112,16,48,16,288,32,96,32,64,272,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512,4760,8,24,8,20,4,8,17,1,2,4,8,160,32
    ,32,32,664,8,24,8,49,1,2,4,8,160,32,64,596,4,8,17,1,2,4,8,24,8,52,4,8,17,1,2,4,8,160,64,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1
    ,2,4,8,256,4896,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,5288,8,8,8,34,2,4,8,1,1,2,4,8,176,16,48,16,152,8,24,8,49,1,2,4,8,160,32,64,1058
    ,2,4,8,1,1,2,4,8,4,4,8,18,2,4,8,1,1,2,4,8,8,8,18,15,1,18,4,8,18,2,4,8,1,1,2,4,8,144,64,32,16,17,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1
    ,2,4,8,256,5424,16,112,16,48,16,288,32,96,32,64,1296,128,64,32,16,512,4760,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,664,8,24,8,49,1,2,4,8,160,32,64
    ,1553,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,4896,32,96,32,32,32,800,32,96,32,64,2048,2116,4,8,4,4,8,2,2,4,8,1,1,2,4,8,68,4
    ,8,4,4,8,2,2,4,8,1,1,2,4,8,80,16,16,16,80,16,16,16,84,4,8,17,1,2,4,8,84,4,8,17,1,2,4,8,96,32,96,32,34,2,4,8,1,1,2,4,8,4,4,8,18,2,4,8,1,1,2,4,8,68
    ,4,8,18,2,4,8,1,1,2,4,8,48,16,16,32,16,80,32,16,17,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,136,8,8,8,8,8,8,8,4,4,8,4,4,8,2,2,4
    ,8,1,1,2,4,8,144,16,16,16,16,16,16,16,152,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,1092,4,8,4,4,8,2,2,4,8,1,1,2,4,8,8,8,8,8,36,4,8,4,4,8,2,2,4,8,1,1
    ,2,4,8,144,16,48,16,16,16,84,4,8,17,1,2,4,8,24,8,52,4,8,17,1,2,4,8,160,64,32,34,2,4,8,1,1,2,4,8,4,4,8,18,2,4,8,1,1,2,4,8,8,8,18,15,1,18,4,8,18,2,4
    ,8,1,1,2,4,8,144,64,32,16,17,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,4368,16,16,16,80,16,16,16,16,16,16,16,288,32,96,32,32,32
    ,1296,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512,2644,4,8,17,1,2,4,8,84,4,8,17,1,2,4,8,96,32,96,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2
    ,4,8,81,32,1,2,4,8,32,32,64,128,664,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,1620,4,8,17,1,2,4,8,24,8,52,4,8,17,1,2,4,8,160,64,32,529,1,2,4,8,17,1,2
    ,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,4896,32,96,32,32,32,1824,128,64,32,1024,1058,2,4,8,1,1,2,4,8,34,2,4,8,1,1,2,4,8,40,8,8,8,34,2,4,8,1
    ,1,2,4,8,48,16,48,16,48,16,48,16,17,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,68,4,8,4,4,8,2,2,4,8,1,1,2,4,8,68,4,8,4,4
    ,8,2,2,4,8,1,1,2,4,8,80,16,16,16,80,16,16,16,546,2,4,8,1,1,2,4,8,4,4,8,18,2,4,8,1,1,2,4,8,68,4,8,18,2,4,8,1,1,2,4,8,48,16,16,32,16,80,32,16,17,1,2
    ,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,136,8,8,8,8,8,8,8,4,4,8,4,4,8,2,2,4,8,1,1,2,4,8,144,16,16,16,16,16,16,16,546,2,4,8,1,1,2
    ,4,8,72,8,18,15,1,222,129,1,2,4,8,17,1,2,4,8,81,1,31,1,402,4,8,4,4,8,2,2,4,8,1,1,2,4,8,8,8,8,8,36,4,8,4,4,8,2,2,4,8,1,1,2,4,8,144,16,48,16,16,16
    ,546,2,4,8,1,1,2,4,8,4,4,8,18,2,4,8,1,1,2,4,8,8,8,18,15,1,18,4,8,18,2,4,8,1,1,2,4,8,144,64,32,16,17,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31
    ,32,1,2,4,8,256,4368,16,16,16,80,16,16,16,16,16,16,16,784,128,896,16,112,16,48,16,16,16,784,128,64,32,16,512,529,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2
    ,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,529,1,2,4,8,49
    ,128,79,753,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,529,1,2,4,8,17,1,2,4,8,81,1,31,1,31,832,1,2,4,8,17,1,2,4,8,81,1,31,1,863,1
    ,2,4,8,49,64,1,63,832,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,8192,8464,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,288,32
    ,32,32,32,32,32,32,304,16,48,16,48,16,48,16,288,32,64,32,32,64,336,16,16,16,80,16,16,16,352,32,96,32,304,16,16,32,16,80,32,16,288,32,64,128,272,16
    ,16,16,80,16,16,16,16,16,16,16,288,32,96,32,32,32,304,16,112,16,48,16,288,32,96,32,64,272,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512
    ,8992,32,32,32,32,32,32,32,800,32,64,32,32,64,864,32,96,32,800,32,64,128,800,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,9520,16,48,16,48,16
    ,48,16,288,32,64,32,32,64,1328,16,16,32,16,80,32,16,288,32,64,128,1328,16,112,16,48,16,288,32,96,32,64,1296,128,64,32,16,512,8992,32,32,32,32,32
    ,32,32,800,32,64,32,32,64,1824,32,64,128,800,32,96,32,32,32,800,32,96,32,64,2048,10576,16,16,16,80,16,16,16,352,32,96,32,304,16,16,32,16,80,32,16
    ,288,32,64,128,2320,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512,11104,32,96,32,800,32,64,128,2848,128,64,32,1024,9520,16,48,16,48,16
    ,48,16,288,32,64,32,32,64,336,16,16,16,80,16,16,16,816,16,16,32,16,80,32,16,288,32,64,128,2320,16,112,16,48,16,16,16,784,128,64,32,16,512,8992,32
    ,32,32,32,32,32,32,800,32,64,32,32,64,800,1024,32,64,128,4096,8464,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,304,16,48
    ,16,48,16,48,16,288,32,64,32,32,64,2320,16,16,16,80,16,16,16,16,16,16,16,288,32,96,32,32,32,304,16,112,16,48,16,288,32,96,32,64,272,16,112,16,48
    ,16,16,16,288,128,64,32,272,128,64,32,16,512,8992,32,32,32,32,32,32,32,800,32,64,32,32,64,2848,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024
    ,9520,16,48,16,48,16,48,16,288,32,64,32,32,64,3376,16,112,16,48,16,288,32,96,32,64,1296,128,64,32,16,512,8992,32,32,32,32,32,32,32,800,32,64,32,32
    ,64,2848,32,96,32,32,32,800,32,96,32,64,2048,8464,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,1296,16,512,496,1024,16,16
    ,16,80,16,16,16,16,16,16,16,288,32,96,32,32,32,1296,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512,8992,32,32,32,32,32,32,32,1824,2048
    ,32,96,32,32,32,1824,128,64,32,1024,8464,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,784,128,896,16,1008,1024,16,16,16,80,16,16,16,16,16,16,16
    ,784,128,896,16,112,16,48,16,16,16,784,128,64,32,16,512,16384,16913,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32
    ,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,596,4,8,17,1,2,4,8,84,4,8,17,1,2,4,8,96,32,96,32,529,1,2,4,8
    ,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,664,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,664,8,24,8,49,1,2,4,8,160,32,64,596,4,8,17,1,2,4,8
    ,24,8,52,4,8,17,1,2,4,8,160,64,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,800,32,32,32,32,32,32,32,800,32,64,32,32,64,864
    ,32,96,32,800,32,64,128,800,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,16913,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4
    ,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,1553,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1
    ,2,4,8,32,32,64,128,664,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,664,8,24,8,49,1,2,4,8,160,32,64,1553,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31
    ,32,1,2,4,8,256,800,32,32,32,32,32,32,32,800,32,64,32,32,64,1824,32,64,128,800,32,96,32,32,32,800,32,96,32,64,2048,19028,4,8,17,1,2,4,8,84,4,8,17
    ,1,2,4,8,96,32,96,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,2644,4,8,17,1,2,4,8,24,8,52,4,8,17,1,2,4,8,160,64,32,529,1,2
    ,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,2912,32,96,32,800,32,64,128,2848,128,64,32,1024,16913,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4
    ,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,529,1,2,4,8,49,128
    ,79,753,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,2577,1,2,4,8,49,64,1,63,832,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1
    ,2,4,8,256,800,32,32,32,32,32,32,32,800,32,64,32,32,64,800,1024,32,64,128,4096,21144,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,664,8,24,8,49,1,2,4,8
    ,160,32,64,596,4,8,17,1,2,4,8,24,8,52,4,8,17,1,2,4,8,160,64,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,4896,32,96,32,32
    ,32,800,32,96,32,64,800,128,64,32,1024,21144,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,664,8,24,8,49,1,2,4,8,160,32,64,1553,1,2,4,8,17,1,2,4,8,17,32,1
    ,2,4,8,17,1,31,1,31,32,1,2,4,8,256,4896,32,96,32,32,32,800,32,96,32,64,2048,19028,4,8,17,1,2,4,8,84,4,8,17,1,2,4,8,96,32,96,32,529,1,2,4,8,17,1,2
    ,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,664,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,1620,4,8,17,1,2,4,8,24,8,52,4,8,17,1,2,4,8,160,64,32,529,1
    ,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,4896,32,96,32,32,32,1824,128,64,32,1024,16913,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24
    ,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,529,1,2,4,8,49,128,79
    ,753,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,529,1,2,4,8,17,1,2,4,8,81,1,31,1,31,832,1,2,4,8,17,1,2,4,8,81,1,31,1,863,1,2,4,8
    ,49,64,1,63,832,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,8192,25376,32,32,32,32,32,32,32,800,32,64,32,32,64,864,32,96,32,800
    ,32,64,128,800,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,25376,32,32,32,32,32,32,32,800,32,64,32,32,64,1824,32,64,128,800,32,96,32,32,32
    ,800,32,96,32,64,2048,27488,32,96,32,800,32,64,128,2848,128,64,32,1024,25376,32,32,32,32,32,32,32,800,32,64,32,32,64,800,1024,32,64,128,4096,25376
    ,32,32,32,32,32,32,32,800,32,64,32,32,64,2848,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,25376,32,32,32,32,32,32,32,800,32,64,32,32,64,2848
    ,32,96,32,32,32,800,32,96,32,64,2048,25376,32,32,32,32,32,32,32,1824,2048,32,96,32,32,32,1824,128,64,32,1024,32768,541201,1,2,4,8,17,1,2,4,8,20,4
    ,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,596,4,8
    ,17,1,2,4,8,84,4,8,17,1,2,4,8,96,32,96,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,664,8,24,8,20,4,8,17,1,2,4,8,160,32,32
    ,32,664,8,24,8,49,1,2,4,8,160,32,64,596,4,8,17,1,2,4,8,24,8,52,4,8,17,1,2,4,8,160,64,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4
    ,8,256,800,32,32,32,32,32,32,32,800,32,64,32,32,64,864,32,96,32,800,32,64,128,800,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,16913,1,2,4,8
    ,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64
    ,32,32,64,1553,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,664,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,664,8,24,8,49,1,2,4,8,160,32
    ,64,1553,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,800,32,32,32,32,32,32,32,800,32,64,32,32,64,1824,32,64,128,800,32,96,32,32
    ,32,800,32,96,32,64,2048,49681,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49
    ,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,529,1,2,4,8,49,128,79,753,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,2577,1,2,4,8
    ,49,64,1,63,832,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,800,32,32,32,32,32,32,32,800,32,64,32,32,64,800,1024,32,64,128,4096
    ,21144,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,664,8,24,8,49,1,2,4,8,160,32,64,596,4,8,17,1,2,4,8,24,8,52,4,8,17,1,2,4,8,160,64,32,529,1,2,4,8,17,1
    ,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,4896,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,21144,8,24,8,20,4,8,17,1,2,4,8,160,32,32
    ,32,664,8,24,8,49,1,2,4,8,160,32,64,1553,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,4896,32,96,32,32,32,800,32,96,32,64,2048
    ,49681,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2
    ,4,8,32,32,64,32,32,64,529,1,2,4,8,49,128,79,753,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,529,1,2,4,8,17,1,2,4,8,81,1,31,1,31
    ,832,1,2,4,8,17,1,2,4,8,81,1,31,1,863,1,2,4,8,49,64,1,63,832,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,8192,25376,32,32,32,32
    ,32,32,32,800,32,64,32,32,64,864,32,96,32,800,32,64,128,800,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,25376,32,32,32,32,32,32,32,800,32,64
    ,32,32,64,1824,32,64,128,800,32,96,32,32,32,800,32,96,32,64,2048,58144,32,32,32,32,32,32,32,800,32,64,32,32,64,800,1024,32,64,128,4096,25376,32,32
    ,32,32,32,32,32,800,32,64,32,32,64,2848,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,25376,32,32,32,32,32,32,32,800,32,64,32,32,64,2848,32,96
    ,32,32,32,800,32,96,32,64,2048,65536,1589777,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8
    ,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,596,4,8,17,1,2,4,8,84,4,8,17,1,2,4,8,96,32,96,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4
    ,8,81,32,1,2,4,8,32,32,64,128,664,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,664,8,24,8,49,1,2,4,8,160,32,64,596,4,8,17,1,2,4,8,24,8,52,4,8,17,1,2,4,8
    ,160,64,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,800,32,32,32,32,32,32,32,800,32,64,32,32,64,864,32,96,32,800,32,64,128
    ,800,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,16913,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32
    ,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,1553,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,664
    ,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,664,8,24,8,49,1,2,4,8,160,32,64,1553,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,800,32,32
    ,32,32,32,32,32,800,32,64,32,32,64,1824,32,64,128,800,32,96,32,32,32,800,32,96,32,64,2048,16913,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20
    ,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,1553,1,2,4,8,49,128,79,3825,1,2,4,8,49,64,1,63,2127,32,32,32,32,32,32,32,1824,22257,1,2,4,8,17,1,2,4,8,20
    ,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,529,1
    ,2,4,8,49,128,79,753,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,2577,1,2,4,8,49,64,1,63,832,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1
    ,31,1,31,32,1,2,4,8,256,800,32,32,32,32,32,32,32,800,32,64,32,32,64,800,1024,32,64,128,4096,82449,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8
    ,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,1553,1,2,4,8,49,128,79,1777,1,2,4,8,17,1,2,4,8,81,1,31,1,31,1856,1,2,4,8,49,64,1,63,26432,1,2,4,8,17,1
    ,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32
    ,64,529,1,2,4,8,49,128,79,753,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,529,1,2,4,8,17,1,2,4,8,81,1,31,1,31,832,1,2,4,8,17,1,2,4
    ,8,81,1,31,1,863,1,2,4,8,49,64,1,63,832,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,8192,25376,32,32,32,32,32,32,32,800,32,64,32
    ,32,64,864,32,96,32,800,32,64,128,800,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,25376,32,32,32,32,32,32,32,800,32,64,32,32,64,1824,32,64
    ,128,800,32,96,32,32,32,800,32,96,32,64,2048,25376,32,32,32,32,32,32,32,1824,30720,32,32,32,32,32,32,32,800,32,64,32,32,64,800,1024,32,64,128,4096
    ,131072,3686929,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24
    ,8,49,1,2,4,8,32,32,64,32,32,64,596,4,8,17,1,2,4,8,84,4,8,17,1,2,4,8,96,32,96,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128
    ,664,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,664,8,24,8,49,1,2,4,8,160,32,64,596,4,8,17,1,2,4,8,24,8,52,4,8,17,1,2,4,8,160,64,32,529,1,2,4,8,17,1,2
    ,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,800,32,32,32,32,32,32,32,800,32,64,32,32,64,864,32,96,32,800,32,64,128,800,32,96,32,32,32,800,32,96
    ,32,64,800,128,64,32,1024,16913,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49
    ,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,1553,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,664,8,24,8,20,4,8,17,1,2,4,8,160
    ,32,32,32,664,8,24,8,49,1,2,4,8,160,32,64,1553,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,800,32,32,32,32,32,32,32,800,32,64,32
    ,32,64,1824,32,64,128,800,32,96,32,32,32,800,32,96,32,64,2048,16913,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32
    ,32,32,32,32,1553,1,2,4,8,49,128,79,3825,1,2,4,8,49,64,1,63,2127,32,32,32,32,32,32,32,1824,22257,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20
    ,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,529,1,2,4,8,49,128,79,753,1,2,4,8
    ,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,2577,1,2,4,8,49,64,1,63,832,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,800
    ,32,32,32,32,32,32,32,800,32,64,32,32,64,800,1024,32,64,128,4096,16913,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32
    ,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,2577,1,2,4,8,17,1,2,4,8,81,1,31,1,31,832,1,2,4,8,17,1,2,4
    ,8,81,1,31,1,863,1,2,4,8,49,64,1,63,26432,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17
    ,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,2577,1,2,4,8,17,1,2,4,8,81,1,31,1,31,832,1,2,4,8,17,1,2,4,8,81,1,31,1,27487,1,2,4,8,17
    ,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,1553,1,2,4,8,49,128,79,1777,1,2,4,8,17,1,2,4,8,81,1,31,1,31,1856,1
    ,2,4,8,49,64,1,63,26432,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8
    ,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,529,1,2,4,8,49,128,79,753,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,529,1,2,4,8,17,1,2,4
    ,8,81,1,31,1,31,832,1,2,4,8,17,1,2,4,8,81,1,31,1,863,1,2,4,8,49,64,1,63,832,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,8192
    ,262144,270608,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,304,16,48,16,48,16,48,16,288,32,64,32,32,64,336,16,16,16,80
    ,16,16,16,352,32,96,32,304,16,16,32,16,80,32,16,288,32,64,128,272,16,16,16,80,16,16,16,16,16,16,16,288,32,96,32,32,32,304,16,112,16,48,16,288,32
    ,96,32,64,272,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512,8992,32,32,32,32,32,32,32,800,32,64,32,32,64,864,32,96,32,800,32,64,128,800
    ,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,9520,16,48,16,48,16,48,16,288,32,64,32,32,64,1328,16,16,32,16,80,32,16,288,32,64,128,1328,16
    ,112,16,48,16,288,32,96,32,64,1296,128,64,32,16,512,8992,32,32,32,32,32,32,32,800,32,64,32,32,64,1824,32,64,128,800,32,96,32,32,32,800,32,96,32,64
    ,2048,10576,16,16,16,80,16,16,16,352,32,96,32,304,16,16,32,16,80,32,16,288,32,64,128,2320,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512
    ,11104,32,96,32,800,32,64,128,2848,128,64,32,1024,9520,16,48,16,48,16,48,16,288,32,64,32,32,64,336,16,16,16,80,16,16,16,816,16,16,32,16,80,32,16
    ,288,32,64,128,2320,16,112,16,48,16,16,16,784,128,64,32,16,512,8992,32,32,32,32,32,32,32,800,32,64,32,32,64,800,1024,32,64,128,4096,8464,16,16,16
    ,16,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,304,16,48,16,48,16,48,16,288,32,64,32,32,64,2320,16,16,16,80,16,16,16,16,16,16,16
    ,288,32,96,32,32,32,304,16,112,16,48,16,288,32,96,32,64,272,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512,8992,32,32,32,32,32,32,32,800
    ,32,64,32,32,64,2848,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,9520,16,48,16,48,16,48,16,288,32,64,32,32,64,3376,16,112,16,48,16,288,32,96
    ,32,64,1296,128,64,32,16,512,8992,32,32,32,32,32,32,32,800,32,64,32,32,64,2848,32,96,32,32,32,800,32,96,32,64,2048,8464,16,16,16,16,16,16,16,16,16
    ,16,16,16,16,16,16,288,32,32,32,32,32,32,32,1296,16,512,496,1024,16,16,16,80,16,16,16,16,16,16,16,288,32,96,32,32,32,1296,16,112,16,48,16,16,16
    ,288,128,64,32,272,128,64,32,16,512,8992,32,32,32,32,32,32,32,1824,2048,32,96,32,32,32,1824,128,64,32,1024,8464,16,16,16,16,16,16,16,16,16,16,16
    ,16,16,16,16,784,128,896,16,1008,1024,16,16,16,80,16,16,16,16,16,16,16,784,128,896,16,112,16,48,16,16,16,784,128,64,32,16,512,16384,287520,32,32
    ,32,32,32,32,32,800,32,64,32,32,64,864,32,96,32,800,32,64,128,800,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,25376,32,32,32,32,32,32,32,800
    ,32,64,32,32,64,1824,32,64,128,800,32,96,32,32,32,800,32,96,32,64,2048,27488,32,96,32,800,32,64,128,2848,128,64,32,1024,25376,32,32,32,32,32,32,32
    ,800,32,64,32,32,64,800,1024,32,64,128,4096,25376,32,32,32,32,32,32,32,800,32,64,32,32,64,2848,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024
    ,25376,32,32,32,32,32,32,32,800,32,64,32,32,64,2848,32,96,32,32,32,800,32,96,32,64,2048,25376,32,32,32,32,32,32,32,1824,2048,32,96,32,32,32,1824
    ,128,64,32,1024,32768,811808,32,32,32,32,32,32,32,800,32,64,32,32,64,864,32,96,32,800,32,64,128,800,32,96,32,32,32,800,32,96,32,64,800,128,64,32
    ,1024,25376,32,32,32,32,32,32,32,800,32,64,32,32,64,1824,32,64,128,800,32,96,32,32,32,800,32,96,32,64,2048,58144,32,32,32,32,32,32,32,800,32,64,32
    ,32,64,800,1024,32,64,128,4096,25376,32,32,32,32,32,32,32,800,32,64,32,32,64,2848,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,25376,32,32,32
    ,32,32,32,32,800,32,64,32,32,64,2848,32,96,32,32,32,800,32,96,32,64,2048,65536,1860384,32,32,32,32,32,32,32,800,32,64,32,32,64,864,32,96,32,800,32
    ,64,128,800,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,25376,32,32,32,32,32,32,32,800,32,64,32,32,64,1824,32,64,128,800,32,96,32,32,32,800
    ,32,96,32,64,2048,25376,32,32,32,32,32,32,32,1824,30720,32,32,32,32,32,32,32,800,32,64,32,32,64,800,1024,32,64,128,4096,131072,270608,16,16,16,16
    ,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,304,16,48,16,48,16,48,16,288,32,64,32,32,64,336,16,16,16,80,16,16,16,352,32,96,32,304
    ,16,16,32,16,80,32,16,288,32,64,128,272,16,16,16,80,16,16,16,16,16,16,16,288,32,96,32,32,32,304,16,112,16,48,16,288,32,96,32,64,272,16,112,16,48
    ,16,16,16,288,128,64,32,272,128,64,32,16,512,8992,32,32,32,32,32,32,32,800,32,64,32,32,64,864,32,96,32,800,32,64,128,800,32,96,32,32,32,800,32,96
    ,32,64,800,128,64,32,1024,9520,16,48,16,48,16,48,16,288,32,64,32,32,64,1328,16,16,32,16,80,32,16,288,32,64,128,1328,16,112,16,48,16,288,32,96,32
    ,64,1296,128,64,32,16,512,8992,32,32,32,32,32,32,32,800,32,64,32,32,64,1824,32,64,128,800,32,96,32,32,32,800,32,96,32,64,2048,74000,16,16,16,16,16
    ,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,304,16,48,16,48,16,48,16,288,32,64,32,32,64,2320,16,16,16,80,16,16,16,16,16,16,16,288,32
    ,96,32,32,32,304,16,112,16,48,16,288,32,96,32,64,272,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512,8992,32,32,32,32,32,32,32,800,32,64
    ,32,32,64,2848,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,9520,16,48,16,48,16,48,16,288,32,64,32,32,64,3376,16,112,16,48,16,288,32,96,32,64
    ,1296,128,64,32,16,512,8992,32,32,32,32,32,32,32,800,32,64,32,32,64,2848,32,96,32,32,32,800,32,96,32,64,2048,8464,16,16,16,16,16,16,16,16,16,16,16
    ,16,16,16,16,288,32,32,32,32,32,32,32,1296,16,512,496,1024,16,16,16,80,16,16,16,16,16,16,16,288,32,96,32,32,32,1296,16,112,16,48,16,16,16,288,128
    ,64,32,272,128,64,32,16,512,8992,32,32,32,32,32,32,32,1824,2048,32,96,32,32,32,1824,128,64,32,1024,8464,16,16,16,16,16,16,16,16,16,16,16,16,16,16
    ,16,784,128,896,16,1008,1024,16,16,16,80,16,16,16,16,16,16,16,784,128,896,16,112,16,48,16,16,16,784,128,64,32,16,512,16384,287520,32,32,32,32,32
    ,32,32,800,32,64,32,32,64,864,32,96,32,800,32,64,128,800,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,25376,32,32,32,32,32,32,32,800,32,64,32
    ,32,64,1824,32,64,128,800,32,96,32,32,32,800,32,96,32,64,2048,90912,32,32,32,32,32,32,32,800,32,64,32,32,64,2848,32,96,32,32,32,800,32,96,32,64
    ,800,128,64,32,1024,25376,32,32,32,32,32,32,32,800,32,64,32,32,64,2848,32,96,32,32,32,800,32,96,32,64,2048,25376,32,32,32,32,32,32,32,1824,2048,32
    ,96,32,32,32,1824,128,64,32,1024,32768,811808,32,32,32,32,32,32,32,800,32,64,32,32,64,864,32,96,32,800,32,64,128,800,32,96,32,32,32,800,32,96,32
    ,64,800,128,64,32,1024,25376,32,32,32,32,32,32,32,800,32,64,32,32,64,1824,32,64,128,800,32,96,32,32,32,800,32,96,32,64,2048,90912,32,32,32,32,32
    ,32,32,800,32,64,32,32,64,2848,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,25376,32,32,32,32,32,32,32,800,32,64,32,32,64,2848,32,96,32,32,32
    ,800,32,96,32,64,2048,65536,270608,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,304,16,48,16,48,16,48,16,288,32,64,32,32
    ,64,336,16,16,16,80,16,16,16,352,32,96,32,304,16,16,32,16,80,32,16,288,32,64,128,272,16,16,16,80,16,16,16,16,16,16,16,288,32,96,32,32,32,304,16
    ,112,16,48,16,288,32,96,32,64,272,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512,8992,32,32,32,32,32,32,32,800,32,64,32,32,64,864,32,96
    ,32,800,32,64,128,800,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,41232,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32
    ,32,1296,16,512,496,13840,32,32,32,32,32,32,32,1824,13808,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,784,128,896,16,1008,29696,16,16,16,16,16,16
    ,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,304,16,48,16,48,16,48,16,288,32,64,32,32,64,2320,16,16,16,80,16,16,16,16,16,16,16,288,32,96
    ,32,32,32,304,16,112,16,48,16,288,32,96,32,64,272,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512,8992,32,32,32,32,32,32,32,800,32,64,32
    ,32,64,2848,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,41232,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,1296,16
    ,512,496,1024,16,16,16,80,16,16,16,16,16,16,16,288,32,96,32,32,32,1296,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512,8992,32,32,32,32
    ,32,32,32,1824,2048,32,96,32,32,32,1824,128,64,32,1024,8464,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,784,128,896,16,1008,1024,16,16,16,80,16
    ,16,16,16,16,16,16,784,128,896,16,112,16,48,16,16,16,784,128,64,32,16,512,16384,287520,32,32,32,32,32,32,32,800,32,64,32,32,64,864,32,96,32,800,32
    ,64,128,800,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,58144,32,32,32,32,32,32,32,1824,63488,32,32,32,32,32,32,32,800,32,64,32,32,64,2848
    ,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,58144,32,32,32,32,32,32,32,1824,2048,32,96,32,32,32,1824,128,64,32,1024,32768,270608,16,16,16
    ,16,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,304,16,48,16,48,16,48,16,288,32,64,32,32,64,336,16,16,16,80,16,16,16,352,32,96,32
    ,304,16,16,32,16,80,32,16,288,32,64,128,272,16,16,16,80,16,16,16,16,16,16,16,288,32,96,32,32,32,304,16,112,16,48,16,288,32,96,32,64,272,16,112,16
    ,48,16,16,16,288,128,64,32,272,128,64,32,16,512,24848,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,784,128,1920,1024,16,16,16,80,16,16,16,16,16,16
    ,16,784,128,27520,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,1296,16,512,496,29696,16,16,16,16,16,16,16,16,16,16,16,16
    ,16,16,16,784,128,896,16,1008,29696,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,304,16,48,16,48,16,48,16,288,32,64,32,32
    ,64,2320,16,16,16,80,16,16,16,16,16,16,16,288,32,96,32,32,32,304,16,112,16,48,16,288,32,96,32,64,272,16,112,16,48,16,16,16,288,128,64,32,272,128
    ,64,32,16,512,24848,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,784,128,2944,16,16,16,80,16,16,16,16,16,16,16,784,128,27520,16,16,16,16,16,16,16
    ,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,1296,16,512,496,1024,16,16,16,80,16,16,16,16,16,16,16,288,32,96,32,32,32,1296,16,112,16,48,16,16
    ,16,288,128,64,32,272,128,64,32,16,512,24848,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,784,128,896,16,1008,1024,16,16,16,80,16,16,16,16,16,16
    ,16,784,128,896,16,112,16,48,16,16,16,784,128,64,32,16,512,16384,16913,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32
    ,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,596,4,8,17,1,2,4,8,84,4,8,17,1,2,4,8,96,32,96,32,529,1,2
    ,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,664,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,664,8,24,8,49,1,2,4,8,160,32,64,596,4,8,17,1,2
    ,4,8,24,8,52,4,8,17,1,2,4,8,160,64,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,800,32,32,32,32,32,32,32,800,32,64,32,32,64
    ,864,32,96,32,800,32,64,128,800,32,96,32,32,32,800,32,96,32,64,800,128,64,32,1024,16913,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1
    ,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,1553,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81
    ,32,1,2,4,8,32,32,64,128,664,8,24,8,20,4,8,17,1,2,4,8,160,32,32,32,664,8,24,8,49,1,2,4,8,160,32,64,1553,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1
    ,31,32,1,2,4,8,256,800,32,32,32,32,32,32,32,800,32,64,32,32,64,1824,32,64,128,800,32,96,32,32,32,800,32,96,32,64,2048,16913,1,2,4,8,17,1,2,4,8,20
    ,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,1553,1,2,4,8,49,128,79,3825,1,2,4,8,49,64,1,63,2127,32,32,32,32,32,32,32,1824
    ,22257,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2
    ,4,8,32,32,64,32,32,64,529,1,2,4,8,49,128,79,753,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,2577,1,2,4,8,49,64,1,63,832,1,2,4,8
    ,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,800,32,32,32,32,32,32,32,800,32,64,32,32,64,800,1024,32,64,128,4096,16913,1,2,4,8,17,1,2,4,8
    ,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64
    ,2577,1,2,4,8,17,1,2,4,8,81,1,31,1,31,832,1,2,4,8,17,1,2,4,8,81,1,31,1,863,1,2,4,8,49,64,1,63,26432,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8
    ,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,2577,1,2,4,8,17,1,2,4,8,81,1
    ,31,1,31,832,1,2,4,8,17,1,2,4,8,81,1,31,1,27487,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,1553,1,2
    ,4,8,49,128,79,1777,1,2,4,8,17,1,2,4,8,81,1,31,1,31,1856,1,2,4,8,49,64,1,63,26432,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8
    ,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,529,1,2,4,8,49,128,79,753,1,2,4,8,17,1,2,4,8,17
    ,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,529,1,2,4,8,17,1,2,4,8,81,1,31,1,31,832,1,2,4,8,17,1,2,4,8,81,1,31,1,863,1,2,4,8,49,64,1,63,832,1,2,4,8,17
    ,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,8192,8464,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,304,16,48,16,48
    ,16,48,16,288,32,64,32,32,64,336,16,16,16,80,16,16,16,352,32,96,32,304,16,16,32,16,80,32,16,288,32,64,128,272,16,16,16,80,16,16,16,16,16,16,16,288
    ,32,96,32,32,32,304,16,112,16,48,16,288,32,96,32,64,272,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512,529,1,2,4,8,17,1,2,4,8,20,4,8,17
    ,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,596,4,8,17,1
    ,2,4,8,84,4,8,17,1,2,4,8,96,32,96,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,4368,16,16,16,16,16,16,16,16,16,16,16,16,16
    ,16,16,17,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,144,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,16,4,8,3,1,17,1,2,5,1,2,4,16,1,1,7,1,3,1,1,1,17,1,7,1,3
    ,1,2,16,1,8,4,2,1,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,144,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,49,1,2,5,1,2,4,16,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2
    ,64,336,16,16,16,80,16,16,16,84,4,8,17,1,2,4,8,208,4,8,3,1,17,1,2,5,1,2,4,80,1,8,4,2,1,32,529,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,144,1,1,2,5,1,2,1,1
    ,1,1,17,1,2,5,1,2,1,1,2,17,8,24,1,2,5,1,2,4,128,272,16,16,16,80,16,16,16,16,16,16,16,17,1,2,4,8,17,1,2,4,8,81,1,31,1,31,63,1,1,2,5,1,2,1,1,1,1,17
    ,1,2,5,1,2,1,1,2,80,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,16,1,8,4,2,1,32,529,1,2,4,8,17,1,2,4,8,81,1,31,1,94,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,80,1
    ,1,7,1,3,1,1,1,17,1,7,1,3,1,2,64,272,16,112,16,48,16,16,16,17,1,2,4,8,49,64,1,63,63,1,1,2,5,1,2,1,1,1,1,49,8,55,1,1,7,1,3,1,1,1,48,1,8,4,2,1,32
    ,1024,8464,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,784,128,1920,1024,16,16,16,80,16,16,16,16,16,16,16,784,128,3201,1,2,4,8,17,1,2,4,8,20,4,8
    ,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,1553,1,2
    ,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,4368,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,17,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8
    ,144,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,16,4,8,3,1,17,1,2,5,1,2,4,16,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,16,1,8,4,2,1,32,272,128,129,1,2,4,8,17,1,2
    ,4,8,49,1,2,4,8,144,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,49,1,2,5,1,2,4,16,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,64,1296,257,1,2,4,8,17,1,2,4,8,17,32,1
    ,2,4,8,144,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,17,8,24,1,2,5,1,2,4,128,272,16,16,16,80,16,16,16,16,16,16,16,17,1,2,4,8,17,1,2,4,8,81,1,31,1,31
    ,63,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,80,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,16,1,8,4,2,1,32,272,128,129,1,2,4,8,17,1,2,4,8,81,1,31,1,94,1,1,2,5,1
    ,2,1,1,1,1,17,1,2,5,1,2,1,1,2,80,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,64,2048,8464,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32
    ,1296,16,512,496,5377,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,1553,1,2,4,8,49,128,79,5616,16,16
    ,16,16,16,16,16,16,16,16,16,16,16,16,16,17,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,144,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,16,4,8,3,1,17,1,2,5,1,2
    ,4,16,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,16,1,8,4,2,1,32,1296,16,241,1,2,4,8,49,191,1,1,2,5,1,2,1,1,1,1,49,8,13751,16,16,16,16,16,16,16,16,16,16,16,16
    ,16,16,16,784,128,896,16,1008,5377,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8
    ,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,529,1,2,4,8,49,128,79,753,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,81,32,1,2,4,8,32,32,64,128,4368,16
    ,16,16,16,16,16,16,16,16,16,16,16,16,16,16,17,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,144,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,16,4,8,3,1,17,1,2,5
    ,1,2,4,16,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,16,1,8,4,2,1,32,272,128,129,1,2,4,8,17,1,2,4,8,49,1,2,4,8,144,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,49,1
    ,2,5,1,2,4,16,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,64,272,16,241,1,2,4,8,49,191,1,1,2,5,1,2,1,1,1,1,49,8,439,257,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,144,1
    ,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,17,8,24,1,2,5,1,2,4,128,4096,8464,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,304
    ,16,48,16,48,16,48,16,288,32,64,32,32,64,2320,16,16,16,80,16,16,16,16,16,16,16,288,32,96,32,32,32,304,16,112,16,48,16,288,32,96,32,64,272,16,112
    ,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512,529,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32
    ,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,2577,1,2,4,8,17,1,2,4,8,81,1,31,1,31,832,1,2,4,8,17,1,2,4,8,81,1,31,1
    ,863,1,2,4,8,49,64,1,63,1599,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,17,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,144,1,1,2,5,1,2,1,1,1,1,17,1,2,5
    ,1,2,1,1,2,16,4,8,3,1,17,1,2,5,1,2,4,16,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,16,1,8,4,2,1,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,144,1,1,2,5,1,2,1,1,1,1
    ,17,1,2,5,1,2,1,1,2,49,1,2,5,1,2,4,16,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,64,2320,16,16,16,80,16,16,16,16,16,16,16,17,1,2,4,8,17,1,2,4,8,81,1,31,1,31
    ,63,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,80,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,16,1,8,4,2,1,32,529,1,2,4,8,17,1,2,4,8,81,1,31,1,94,1,1,2,5,1,2,1,1,1
    ,1,17,1,2,5,1,2,1,1,2,80,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,64,272,16,112,16,48,16,16,16,17,1,2,4,8,49,64,1,63,63,1,1,2,5,1,2,1,1,1,1,49,8,55,1,1,7,1
    ,3,1,1,1,48,1,8,4,2,1,32,1024,8464,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,784,128,2944,16,16,16,80,16,16,16,16,16,16,16,784,128,3201,1,2,4,8
    ,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64
    ,32,32,64,2577,1,2,4,8,17,1,2,4,8,81,1,31,1,31,832,1,2,4,8,17,1,2,4,8,81,1,31,1,2654,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,17,1,2,4,8,17,1
    ,2,4,8,20,4,8,17,1,2,4,8,144,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,16,4,8,3,1,17,1,2,5,1,2,4,16,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,16,1,8,4,2,1,32
    ,272,128,129,1,2,4,8,17,1,2,4,8,49,1,2,4,8,144,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,49,1,2,5,1,2,4,16,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,64,2320,16
    ,16,16,80,16,16,16,16,16,16,16,17,1,2,4,8,17,1,2,4,8,81,1,31,1,31,63,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,80,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,16,1
    ,8,4,2,1,32,272,128,129,1,2,4,8,17,1,2,4,8,81,1,31,1,94,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,80,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,64,2048,8464,16
    ,16,16,16,16,16,16,16,16,16,16,16,16,16,16,288,32,32,32,32,32,32,32,1296,16,512,496,1024,16,16,16,80,16,16,16,16,16,16,16,288,32,96,32,32,32,1296
    ,16,112,16,48,16,16,16,288,128,64,32,272,128,64,32,16,512,529,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32,32,32,32,32
    ,32,32,1553,1,2,4,8,49,128,79,1777,1,2,4,8,17,1,2,4,8,81,1,31,1,31,1856,1,2,4,8,49,64,1,63,1599,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,17,1
    ,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,144,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,16,4,8,3,1,17,1,2,5,1,2,4,16,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,16,1,8
    ,4,2,1,32,1296,16,241,1,2,4,8,49,191,1,1,2,5,1,2,1,1,1,1,49,8,1463,16,16,16,80,16,16,16,16,16,16,16,17,1,2,4,8,17,1,2,4,8,81,1,31,1,31,63,1,1,2,5
    ,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,80,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,16,1,8,4,2,1,32,1296,16,112,16,48,16,16,16,17,1,2,4,8,49,64,1,63,63,1,1,2,5,1,2
    ,1,1,1,1,49,8,55,1,1,7,1,3,1,1,1,48,1,8,4,2,1,32,1024,8464,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,784,128,896,16,1008,1024,16,16,16,80,16,16
    ,16,16,16,16,16,784,128,896,16,112,16,48,16,16,16,784,128,64,32,16,512,529,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,24,8,24,8,20,4,8,17,1,2,4,8,32,32
    ,32,32,32,32,32,32,529,1,2,4,8,17,1,2,4,8,49,1,2,4,8,24,8,24,8,49,1,2,4,8,32,32,64,32,32,64,529,1,2,4,8,49,128,79,753,1,2,4,8,17,1,2,4,8,17,32,1,2
    ,4,8,81,32,1,2,4,8,32,32,64,128,529,1,2,4,8,17,1,2,4,8,81,1,31,1,31,832,1,2,4,8,17,1,2,4,8,81,1,31,1,863,1,2,4,8,49,64,1,63,832,1,2,4,8,17,1,2,4,8
    ,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4,8,256,272,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,17,1,2,4,8,17,1,2,4,8,20,4,8,17,1,2,4,8,144,1,1,2,5,1
    ,2,1,1,1,1,17,1,2,5,1,2,1,1,2,16,4,8,3,1,17,1,2,5,1,2,4,16,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,16,1,8,4,2,1,32,272,128,129,1,2,4,8,17,1,2,4,8,49,1,2,4
    ,8,144,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,49,1,2,5,1,2,4,16,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,64,272,16,241,1,2,4,8,49,191,1,1,2,5,1,2,1,1,1,1,49
    ,8,439,257,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,144,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,17,8,24,1,2,5,1,2,4,128,272,16,16,16,80,16,16,16,16,16,16
    ,16,17,1,2,4,8,17,1,2,4,8,81,1,31,1,31,63,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,80,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,16,1,8,4,2,1,32,272,128,129,1,2
    ,4,8,17,1,2,4,8,81,1,31,1,94,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,80,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,64,272,16,112,16,48,16,16,16,17,1,2,4,8,49
    ,64,1,63,63,1,1,2,5,1,2,1,1,1,1,49,8,55,1,1,7,1,3,1,1,1,48,1,8,4,2,1,32,272,128,64,32,16,17,1,2,4,8,17,1,2,4,8,17,32,1,2,4,8,17,1,31,1,31,32,1,2,4
    ,8,16,1,1,2,5,1,2,1,1,1,1,17,1,2,5,1,2,1,1,2,17,8,24,1,2,5,1,2,4,16,1,1,7,1,3,1,1,1,17,1,7,1,3,1,2,16,1,8,4,2,1,16,1,1,2,4,1,1,2,1,1,1};<hide>
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    array< array<ll, 5>, 5> c;
    ll total = 0;
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            cin >> c[i][j];
            total += c[i][j];
        }
    }
    for (int i = 1; i < 16213; i++) {
        masks[i] += masks[i - 1];
    }
    ll ans = 1e15;
    for (int i : masks) {
        UnionFind uf(25);
        ll sum = 0;
        for (int j = 0; j < 25; j++) {
            int val = (j == 0 ? 1 : ((i & (1 << (j - 1))) > 0));
            int h = j / 5;
            int w = j % 5;
            if (val) sum += c[h][w];
            for (int k = 0; k < 4; k++) {
                int h2 = h + dh[k], w2 = w + dw[k];
                if (h2 < 0 || h2 >= 5 || w2 < 0 || w2 >= 5) continue;
                int hoge = h2 * 5 + w2;
                int val2 = (hoge == 0 ? 1 : ((i & (1 << (hoge - 1))) > 0));
                if (val == val2) uf.unite(j, hoge);
            }
        }
        if (uf.num != 2) {
            continue;
        }
        ans = min(ans, abs(total - sum * 2));
    }
    cout << ans << "\n";
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
yukicoder

結果

ソースコード
