#ifndef HIDDEN_IN_VS // 折りたたみ用

// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS

// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;

// 型名の短縮
using ll = long long; // -2^63 ～ 2^63 = 9 * 10^18（int は -2^31 ～ 2^31 = 2 * 10^9）
using pii = pair<int, int>;	using pll = pair<ll, ll>;	using pil = pair<int, ll>;	using pli = pair<ll, int>;
using vi = vector<int>;		using vvi = vector<vi>;		using vvvi = vector<vvi>;	using vvvvi = vector<vvvi>;
using vl = vector<ll>;		using vvl = vector<vl>;		using vvvl = vector<vvl>;	using vvvvl = vector<vvvl>;
using vb = vector<bool>;	using vvb = vector<vb>;		using vvvb = vector<vvb>;
using vc = vector<char>;	using vvc = vector<vc>;		using vvvc = vector<vvc>;
using vd = vector<double>;	using vvd = vector<vd>;		using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;

// 定数の定義
const double PI = acos(-1);
const vi DX = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
const vi DY = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003104004004LL; // (int)INFL = 1010931620;
double EPS = 1e-15;

// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;

// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), x))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), x))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0; set < (1 << int(d)); ++set) // d ビット全探索（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define smod(n, m) ((((n) % (m)) + (m)) % (m)) // 非負mod
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定

// 汎用関数の定義
template <class T> inline ll pow(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）
template <class T> inline T get(T set, int i) { return (set >> i) & T(1); }

// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }

#endif // 折りたたみ用


#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;

#ifdef _MSC_VER
#include "localACL.hpp"
#endif

using mint = modint1000000007;
//using mint = modint998244353;
//using mint = modint; // mint::set_mod(m);

namespace atcoder {
	inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
	inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>;
#endif


#ifdef _MSC_VER // 手元環境（Visual Studio）
#include "local.hpp"
#else // 提出用（gcc）
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : -1; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : -1; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define gcd __gcd
#define dump(...)
#define dumpel(v)
#define dump_list(v)
#define dump_mat(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) while (1) cout << "OLE"; }
#endif

// Simple Perfect Squared Squares (SPSSs)
// http://www.squaring.net/sq/ss/spss/spss.html
// に解の一覧が載っている．
// そんなに数は多くないみたいだったので，ソースの表示からコピペしてきて整形し埋め込む．

vvi ans = {
{21,112,112,50,35,27,8,19,15,17,11,6,24,29,25,9,2,7,18,16,42,4,37,33},
{22,110,110,60,50,23,27,24,22,14,7,16,8,6,12,15,13,2,28,26,4,21,3,18,17},
{22,110,110,60,50,27,23,24,22,14,4,19,8,6,3,12,16,9,2,28,26,21,1,18,17},
{22,139,139,80,59,21,38,29,28,17,27,7,10,18,20,4,3,32,8,1,31,30,24,2,22},
{22,147,147,55,44,48,40,4,52,26,29,23,3,20,31,21,5,47,43,9,17,1,8,32,25},
{22,147,147,59,43,45,41,2,47,34,25,21,37,8,55,22,12,10,23,32,11,26,19,4,15},
{22,154,154,61,52,41,11,30,9,35,19,46,24,16,33,22,2,36,17,50,47,21,5,31,26},
{22,172,172,97,75,22,53,39,42,38,9,44,4,19,13,2,36,3,11,33,16,24,1,18,17},
{22,192,192,86,49,57,41,8,28,37,19,9,47,35,4,31,14,10,36,17,26,12,71,62,59},
{23,110,110,44,29,37,21,8,13,32,28,16,15,19,12,4,3,1,2,14,5,10,41,38,7,31},
{23,139,139,80,59,21,38,26,19,15,14,27,1,13,16,18,20,7,12,33,32,8,28,24,2,22},
{23,140,140,54,38,48,28,10,31,27,33,13,8,5,3,2,1,29,20,4,23,16,19,53,45,42},
{23,140,140,60,44,36,8,28,30,22,33,15,12,2,26,24,3,9,7,23,18,16,50,47,4,43},
{23,145,145,84,61,27,34,30,29,25,12,15,8,26,9,3,6,20,4,36,1,32,31,2,24,22},
{23,180,180,92,88,34,22,32,45,47,12,10,23,19,25,21,43,2,41,8,4,15,37,11,33,26},
{23,188,188,96,92,45,47,26,37,33,15,11,25,8,4,23,21,19,51,2,49,12,34,32,10,22},
{23,208,208,71,75,62,22,40,67,4,60,10,9,1,12,18,11,23,17,41,16,24,3,73,70,65},
{23,215,215,79,66,70,22,40,4,74,60,10,9,1,12,18,11,23,17,41,16,24,76,3,71,68},
{23,228,228,99,73,56,17,39,68,22,36,25,57,42,9,16,2,7,10,28,23,15,87,18,72,69},
{23,257,257,134,123,11,24,33,55,60,57,28,15,9,20,22,29,14,32,2,79,3,66,17,63,49},
{23,332,332,123,89,120,58,31,83,68,49,50,24,26,56,48,1,47,30,15,53,17,129,38,112,91},
{24,120,120,47,32,41,15,17,8,33,19,20,23,25,14,5,4,13,3,10,16,9,12,46,40,6,34},
{24,186,186,96,90,36,28,26,43,23,30,2,24,8,22,16,7,9,12,60,4,18,3,15,47,46,33},
{24,194,194,72,54,68,37,17,3,65,20,53,19,34,42,69,18,10,36,61,28,2,9,25,23,7,16},
{24,195,195,80,63,52,11,41,17,27,30,61,26,10,16,21,18,53,42,39,54,7,4,49,47,2,45},
{24,196,196,105,91,24,36,31,51,44,10,34,5,26,20,21,2,17,1,48,18,47,15,40,11,32,29},
{24,201,201,103,98,22,26,50,46,40,17,23,12,4,9,21,11,1,10,6,58,20,18,3,53,52,38},
{24,201,201,108,93,15,26,52,44,39,19,10,11,9,1,16,22,20,8,24,18,4,56,5,54,49,42},
{24,203,203,105,98,18,32,48,54,40,11,29,15,17,24,58,2,1,21,26,20,44,10,36,5,34,31},
{24,247,247,136,111,25,46,40,32,36,48,45,6,34,24,28,23,9,5,19,12,14,3,66,63,62,56},
{24,253,253,104,77,72,31,18,23,27,50,13,5,28,24,20,70,61,4,44,38,40,9,88,2,86,79},
{24,255,255,137,118,44,74,59,53,25,28,41,16,65,11,63,27,22,10,52,26,5,17,32,3,23,20},
{24,288,288,159,129,57,72,56,39,25,16,23,9,7,2,28,36,42,15,17,22,87,10,18,73,68,60},
{24,288,288,165,123,51,72,64,69,32,30,21,93,17,8,7,1,36,9,26,59,5,54,20,14,48,34},
{24,290,290,166,124,42,82,61,59,48,40,8,30,84,11,14,31,2,65,3,63,17,9,21,45,12,33},
{24,292,292,175,117,44,73,15,29,57,54,22,24,17,1,16,102,33,20,2,26,12,8,67,3,63,60},
{24,304,304,132,76,96,56,20,116,72,47,69,25,22,3,48,29,11,100,35,92,12,17,7,5,57,55},
{24,304,304,175,129,53,76,72,28,24,44,7,37,23,4,20,32,99,16,85,12,36,57,27,3,33,30},
{24,314,314,139,79,96,62,17,113,78,59,2,64,19,40,44,16,4,12,105,97,28,29,11,18,65,47},
{24,316,316,172,144,65,79,78,57,37,36,52,14,93,33,24,23,13,66,12,9,15,10,3,55,54,48},
{24,326,326,142,83,101,65,18,119,80,56,6,71,24,32,11,44,15,1,14,106,104,43,29,10,63,53},
{24,423,423,186,114,123,105,9,132,62,60,31,33,29,2,27,77,36,17,49,50,47,15,168,32,128,127},
{24,435,435,192,112,131,93,19,74,76,100,56,23,13,10,88,80,2,78,33,44,45,8,150,143,1,142},
{24,435,435,200,112,123,101,11,134,95,50,55,30,27,44,3,24,12,21,45,5,63,9,178,54,140,117},
{24,459,459,198,126,135,117,9,144,98,55,45,10,116,36,65,180,68,30,8,57,38,16,100,95,11,84},
{24,459,459,198,126,135,117,9,144,115,38,45,21,17,10,33,83,36,4,23,25,6,50,180,31,146,133},
{24,479,479,175,140,164,35,29,52,24,28,160,6,23,130,86,43,60,26,17,77,44,68,174,5,155,150},
{25,147,147,74,73,32,41,40,34,15,17,6,16,12,14,9,13,10,8,33,27,25,5,4,3,23,20,19},
{25,208,208,119,89,30,59,50,44,26,29,18,8,4,24,60,1,3,7,2,5,12,17,45,39,11,36,28},
{25,213,213,90,49,74,24,25,17,7,6,35,58,13,31,26,47,3,16,28,23,5,21,36,81,20,76,56},
{25,215,215,83,60,33,39,27,6,45,63,24,42,41,69,26,37,1,40,43,15,11,7,62,55,4,51,47},
{25,216,216,113,103,49,54,41,33,39,8,25,19,64,5,32,17,59,16,45,30,2,1,4,11,3,7,18},
{25,236,236,107,65,64,24,40,46,19,15,4,12,16,14,1,13,9,47,59,48,44,2,38,85,11,81,70},
{25,242,242,131,111,47,64,54,51,26,25,1,31,17,14,67,3,60,13,57,6,16,23,19,9,7,30,28},
{25,244,244,134,110,17,27,66,7,10,26,30,45,40,37,22,4,19,15,5,70,2,68,65,21,1,20,41},
{25,252,252,113,71,68,32,36,42,29,13,44,4,40,62,37,38,31,7,108,25,12,11,34,23,77,10,67},
{25,253,253,133,120,50,70,54,42,37,5,24,38,20,12,35,66,27,63,10,14,6,4,2,45,9,43,36},
{25,260,260,112,78,70,37,33,34,44,4,29,15,26,71,65,10,31,38,1,28,27,24,7,100,6,83,77},
{25,264,264,134,130,24,42,64,61,53,20,26,18,38,22,7,19,8,40,12,16,70,69,31,54,37,3,34},
{25,264,264,134,130,24,42,64,71,43,20,26,18,38,22,40,3,29,16,70,59,12,8,21,54,47,13,34},
{25,264,264,135,129,6,54,69,73,68,20,16,18,3,66,4,12,21,22,61,9,56,17,1,11,10,42,39},
{25,265,265,135,130,22,42,66,62,56,17,39,10,11,21,9,1,12,6,74,20,4,18,3,16,69,68,54},
{25,273,273,120,65,88,43,22,21,1,89,12,52,62,33,37,29,4,30,11,8,27,17,19,10,96,91,86},
{25,273,273,140,133,25,46,62,68,54,18,22,21,1,50,16,23,14,31,9,78,32,65,17,48,6,44,38},
{25,275,275,100,81,94,68,13,107,51,49,2,55,60,53,33,74,71,37,35,25,17,41,34,3,31,7,24},
{25,276,276,120,69,87,51,18,105,44,36,45,46,8,19,9,41,11,53,1,47,30,21,84,71,5,63,58},
{25,280,280,97,95,88,34,54,68,27,55,42,41,20,18,24,21,53,50,5,17,6,11,117,32,28,85,78},
{25,280,280,106,96,78,18,60,75,39,54,52,36,3,63,2,50,56,37,44,30,14,79,8,72,7,65,64},
{25,284,284,110,77,97,38,39,19,78,68,42,37,1,59,26,14,16,23,12,2,18,11,40,109,106,29,69},
{25,286,286,153,133,54,79,53,30,37,33,23,7,32,1,35,20,16,28,80,12,15,5,10,74,68,4,64},
{25,289,289,102,104,83,21,62,100,2,50,36,41,14,17,5,32,76,61,3,20,52,87,13,74,8,68,60},
{25,289,289,149,140,31,44,65,68,64,17,12,5,7,29,19,23,21,16,3,32,2,84,25,4,76,72,57},
{25,290,290,119,91,80,11,69,28,38,36,77,60,10,2,34,50,13,56,18,15,1,14,29,17,111,94,85},
{25,293,293,130,68,95,41,27,34,88,21,20,54,66,85,32,110,42,24,11,28,78,18,6,17,55,5,50},
{25,297,297,160,137,38,99,77,68,15,53,26,69,18,8,10,36,61,60,17,28,43,2,9,25,23,7,16},
{25,308,308,116,113,79,34,45,43,87,10,7,77,39,3,4,13,12,37,25,38,1,44,62,115,108,23,85},
{25,308,308,133,73,102,28,45,13,7,8,16,86,6,1,9,19,70,71,38,43,33,5,48,36,120,104,84},
{25,309,309,117,92,100,25,59,8,108,82,60,26,33,56,23,7,16,24,48,34,39,31,101,14,76,70,62},
{25,311,311,160,151,26,23,16,25,61,83,60,17,7,9,28,2,36,43,18,10,8,99,38,91,68,15,53},
{25,314,314,128,85,101,69,16,53,64,70,32,26,6,44,87,11,38,75,116,36,29,7,1,74,22,73,51},
{25,316,316,120,111,85,26,59,53,30,21,33,79,41,9,12,39,35,69,38,3,56,1,34,40,117,103,96},
{25,317,317,113,94,110,19,59,16,126,92,40,52,47,5,42,112,37,6,7,32,81,75,9,1,8,17,49},
{25,320,320,116,108,96,12,35,49,23,53,44,101,15,38,21,14,63,9,56,8,54,46,7,112,2,105,103},
{25,320,320,168,152,27,30,95,85,72,11,35,3,33,26,9,8,25,17,31,80,29,22,73,67,18,51,49},
{25,320,320,170,150,38,34,78,69,41,60,4,30,42,28,13,16,14,7,6,92,1,33,90,8,81,24,57},
{25,320,320,170,150,38,34,78,71,39,60,4,30,42,24,15,16,14,9,6,92,3,31,90,8,28,79,59},
{25,322,322,178,144,47,97,80,76,22,9,38,31,10,28,23,8,18,16,81,4,24,68,3,65,64,20,44},
{25,322,322,178,144,59,85,80,76,22,19,3,16,28,18,35,10,8,93,38,4,24,68,15,64,20,53,44},
{25,323,323,164,159,23,36,34,66,72,57,35,10,13,7,3,2,32,4,50,46,15,42,98,87,18,78,60},
{25,323,323,168,155,31,51,73,83,67,18,49,29,22,95,27,30,88,72,11,35,3,33,26,9,8,25,17},
{25,323,323,177,146,48,98,82,72,23,6,42,29,20,9,2,13,27,11,19,79,28,74,14,64,18,60,46},
{25,325,325,134,112,79,28,51,5,23,99,18,92,43,46,45,40,3,13,32,37,12,25,6,114,11,108,103},
{25,326,326,168,158,10,36,37,75,90,88,35,1,38,27,8,4,16,93,12,28,24,70,21,68,22,49,46},
{25,327,327,140,100,87,13,74,52,61,84,44,12,55,9,46,36,62,21,23,10,26,19,2,120,16,104,103},
{25,328,328,176,152,40,38,74,73,45,58,2,36,42,28,17,8,102,14,94,7,10,4,3,27,79,26,53},
{25,334,334,168,166,24,49,93,78,68,22,46,21,28,10,98,27,12,16,88,8,4,38,75,35,1,37,36},
{25,336,336,184,152,40,38,74,73,45,58,8,2,36,50,110,28,17,14,94,7,10,4,3,27,79,26,53},
{25,338,338,174,164,10,53,101,70,46,68,25,28,24,22,96,19,94,16,12,4,8,39,36,73,38,1,37},
{25,338,338,174,164,10,57,97,70,46,68,24,22,21,36,96,15,94,43,8,4,16,77,12,28,38,5,33},
{25,340,340,171,169,24,66,79,85,64,22,46,16,44,4,53,13,50,92,5,11,84,6,17,61,1,52,51},
{25,344,344,175,169,83,86,98,77,48,56,53,3,89,71,27,44,23,8,14,39,17,36,11,25,21,2,19},
{25,359,359,187,172,46,41,85,82,74,31,14,27,43,25,9,23,10,17,18,7,40,102,8,98,29,90,69},
{25,361,361,205,156,49,107,66,74,47,67,27,20,9,98,32,34,7,89,26,82,22,8,2,6,56,14,36},
{25,363,363,208,155,53,102,64,37,25,32,58,45,12,13,6,26,27,21,1,20,41,4,106,97,28,91,69},
{25,364,364,191,173,82,91,75,52,64,23,29,28,109,9,100,98,16,13,4,24,3,8,2,6,19,14,57},
{25,367,367,212,155,53,102,4,49,64,37,25,32,58,12,13,6,26,27,21,1,20,41,110,97,28,91,69},
{25,368,368,208,160,48,112,91,88,46,31,15,16,42,18,1,17,51,96,25,72,33,69,22,47,6,45,39},
{25,371,371,211,160,51,109,90,64,43,65,21,22,7,102,46,38,1,95,70,20,8,30,50,24,2,28,26},
{25,373,373,148,105,120,43,62,41,79,104,87,6,35,68,32,3,22,60,7,15,31,8,17,138,23,121,114},
{25,378,378,213,165,48,117,80,38,56,87,20,18,2,41,31,22,21,96,85,17,10,78,27,3,24,68,51},
{25,378,378,217,161,56,105,68,43,61,30,29,42,1,15,13,31,2,46,7,25,18,17,112,100,27,93,73},
{25,380,380,194,186,79,107,113,81,31,48,60,21,20,87,35,17,73,40,18,67,4,49,19,45,33,7,26},
{25,380,380,203,177,82,95,49,38,60,56,16,22,44,5,15,6,4,121,13,9,33,50,24,108,84,17,67},
{25,381,381,186,110,85,25,60,100,35,95,84,57,45,21,79,12,54,36,59,27,42,111,13,23,96,92,82},
{25,384,384,204,180,84,96,46,47,51,60,45,1,44,4,27,19,9,21,120,12,8,11,108,35,32,89,67},
{25,384,384,204,180,84,96,81,37,26,60,11,15,44,4,19,31,120,12,108,99,17,9,8,1,32,25,57},
{25,384,384,212,172,76,96,100,55,57,56,20,48,7,116,5,17,35,12,29,11,80,72,25,3,22,69,47},
{25,385,385,224,161,56,105,7,49,68,43,61,30,29,1,15,13,31,2,46,119,25,18,17,100,27,93,73},
{25,392,392,153,98,141,55,43,68,116,88,34,30,56,4,26,23,15,8,7,32,77,48,31,151,29,135,106},
{25,392,392,171,129,92,51,41,115,14,10,31,54,21,52,98,73,35,19,16,55,12,39,25,148,27,123,121},
{25,392,392,197,195,81,114,98,99,24,30,27,97,1,96,4,28,11,16,22,8,31,83,14,5,21,64,52},
{25,393,393,207,186,29,66,91,85,69,45,8,37,50,73,25,16,53,116,101,27,23,4,24,68,64,20,44},
{25,396,396,160,126,110,16,94,69,73,125,35,104,68,5,99,32,36,111,14,97,49,4,46,93,48,1,47},
{25,396,396,199,197,98,99,83,52,64,31,21,14,22,28,16,5,11,8,114,30,27,24,4,101,1,100,81},
{25,396,396,216,180,81,99,98,73,45,60,48,18,117,41,32,17,31,82,16,9,75,8,3,14,11,66,56},
{25,398,398,154,100,144,56,44,68,120,99,53,2,58,46,7,28,17,23,65,11,6,29,39,145,15,134,119},
{25,400,400,179,122,99,23,76,81,64,35,41,100,79,40,24,55,26,53,6,47,3,37,29,21,142,137,121},
{25,404,404,205,199,6,80,113,111,100,26,54,14,31,53,28,21,92,88,20,3,17,32,71,68,46,7,39},
{25,404,404,215,189,88,101,96,32,25,62,7,18,28,11,29,16,12,10,127,13,4,47,114,20,93,23,70},
{25,408,408,213,195,18,72,105,79,46,52,54,33,13,7,43,2,41,57,30,20,116,16,27,3,108,100,84},
{25,412,412,169,114,129,99,15,144,86,83,39,60,3,87,32,89,11,54,139,43,12,85,26,73,68,21,47},
{25,413,413,155,148,110,38,72,7,64,81,34,105,57,106,48,56,17,39,59,153,75,20,60,125,70,5,65},
{25,416,416,169,112,135,82,30,7,128,37,104,65,13,24,2,11,40,44,35,39,62,4,58,25,153,143,120},
{25,416,416,237,179,75,104,88,85,31,16,17,15,1,64,29,22,24,133,20,2,26,12,8,98,3,94,91},
{25,421,421,177,116,128,104,12,140,94,38,22,23,16,5,1,4,20,9,2,7,56,83,48,35,153,150,118},
{25,421,421,222,199,23,59,117,102,107,36,51,44,18,26,40,11,12,105,29,97,5,38,92,20,72,17,55},
{25,422,422,243,179,68,111,93,100,46,4,29,43,13,16,59,2,20,132,18,38,86,7,79,28,23,74,51},
{25,425,425,181,116,128,104,12,140,102,46,14,19,9,5,4,20,13,10,3,79,48,56,31,157,142,16,126},
{25,441,441,222,219,27,72,120,118,80,24,51,6,66,5,52,38,47,18,102,101,39,16,7,92,23,84,62},
{25,454,454,184,134,136,79,53,2,51,87,109,46,29,69,35,17,91,34,1,88,63,48,55,161,11,150,143},
{25,456,456,193,128,135,49,72,7,142,31,18,115,63,15,13,5,77,59,52,11,60,10,50,179,148,19,129},
{25,465,465,173,139,153,125,14,111,56,82,91,31,25,6,19,24,13,32,73,9,64,201,74,21,53,137,127},
{25,472,472,221,118,133,103,15,148,115,81,128,61,87,34,47,136,13,35,26,123,65,9,104,44,58,7,51},
{25,477,477,169,141,167,115,26,193,82,87,77,5,72,135,149,76,117,86,49,16,19,41,37,12,25,3,22},
{25,492,492,255,237,62,47,128,123,132,15,32,60,17,49,31,29,50,127,114,9,105,36,2,27,33,77,69},
{25,492,492,257,235,95,140,123,134,50,45,5,63,117,112,11,55,101,44,57,30,12,9,54,21,27,3,24},
{26,212,212,99,57,56,1,55,26,32,20,6,38,48,19,28,4,24,16,39,12,7,5,2,85,23,17,65,62},
{26,214,214,86,61,67,55,6,34,39,56,30,29,5,44,26,36,23,9,20,32,72,10,64,27,19,8,43,35},
{26,215,215,78,63,74,15,48,35,39,60,33,19,11,5,27,37,17,1,7,31,6,24,20,16,77,10,71,67},
{26,237,237,92,64,81,47,17,28,70,48,44,2,26,25,24,34,16,4,32,33,52,86,31,1,68,45,7,38},
{26,252,252,140,112,44,68,54,22,21,43,27,17,1,20,23,10,7,3,72,18,2,16,69,9,14,58,5,53},
{26,258,258,119,70,69,1,23,45,49,22,27,18,14,4,10,39,66,59,31,34,5,29,28,3,105,7,80,73},
{26,260,260,109,85,66,19,47,32,44,28,80,29,75,21,11,10,1,45,60,31,14,17,72,71,9,62,7,55},
{26,261,261,126,73,62,11,51,53,31,22,9,60,68,52,34,47,21,13,32,88,16,33,3,24,67,17,56,50},
{26,264,264,99,64,44,57,20,11,13,9,2,72,93,41,58,25,47,24,17,3,22,7,38,107,19,31,88,69},
{26,266,266,135,131,35,38,58,70,36,29,7,12,10,8,24,3,21,20,43,2,16,14,1,77,76,61,9,52},
{26,268,268,107,91,70,21,49,40,44,28,83,24,16,61,64,60,15,46,78,5,73,36,35,4,42,1,38,37},
{26,270,270,141,129,25,34,70,72,69,16,9,7,36,23,17,6,13,28,71,3,21,60,2,15,57,18,43,39},
{26,270,270,145,125,53,72,45,11,9,16,31,33,2,7,13,8,15,21,14,32,30,37,19,80,18,73,62,55},
{26,271,271,93,99,79,44,35,87,6,81,24,9,26,60,17,43,91,53,21,3,18,88,39,38,15,8,31,23},
{26,271,271,108,92,71,23,48,16,47,27,2,25,84,40,20,80,9,58,49,79,5,74,28,10,8,72,18,46},
{26,274,274,91,100,83,17,66,82,9,73,53,4,62,57,58,60,37,29,64,1,63,43,15,13,41,6,35,28},
{26,274,274,116,90,68,22,46,26,33,29,24,10,60,75,67,4,20,5,37,15,35,23,14,9,100,8,91,83},
{26,275,275,90,76,53,56,50,3,59,49,27,55,35,65,12,71,20,21,43,51,23,1,22,28,107,18,89,79},
{26,275,275,156,58,61,55,3,64,43,12,76,57,52,19,24,47,13,6,1,23,7,20,2,74,72,5,67,62},
{26,276,276,125,80,71,9,15,47,53,30,6,21,10,11,23,7,16,1,59,69,56,48,44,4,99,13,95,82},
{26,278,278,150,128,57,71,69,40,41,15,42,39,1,33,9,28,43,24,59,10,54,3,51,22,49,7,36,29},
{26,280,280,129,80,71,9,15,47,53,30,6,21,10,11,23,7,16,1,59,69,56,4,52,44,103,13,95,82},
{26,280,280,157,123,34,89,66,75,50,24,26,21,68,57,9,1,6,17,48,20,12,5,47,11,8,4,32,28},
{26,282,282,118,92,72,20,52,26,54,32,77,67,24,60,39,15,13,11,2,9,23,7,16,1,98,10,97,87},
{26,282,282,148,134,55,79,76,72,31,24,7,27,69,22,26,17,25,20,58,18,9,8,5,42,40,1,37,36},
{26,283,283,111,82,90,29,53,42,48,72,44,24,4,9,23,6,20,56,1,5,54,14,28,36,37,100,92,91},
{26,285,285,144,68,73,44,24,23,50,20,4,27,53,11,88,66,57,21,36,38,9,84,30,8,75,22,74,52},
{26,286,286,103,96,87,9,32,46,26,56,23,84,19,41,14,45,60,40,16,8,33,20,25,24,99,5,94,93},
{26,286,286,121,76,89,45,18,13,15,87,11,7,4,3,1,17,16,67,36,41,55,31,5,46,32,110,98,78},
{26,288,288,116,73,99,47,26,21,104,53,63,68,43,10,33,40,31,22,15,7,27,85,9,20,76,69,11,58},
{26,293,293,128,85,80,5,75,43,47,84,87,24,23,1,7,20,70,19,6,13,52,81,3,78,12,2,68,66},
{26,296,296,164,132,47,43,42,60,63,26,15,1,41,4,40,11,55,37,81,33,27,24,69,7,62,6,45,39},
{26,297,297,116,78,103,38,40,15,88,77,33,44,55,17,7,4,5,3,1,6,10,50,27,37,18,106,104,87},
{26,299,299,135,80,84,76,4,88,70,46,19,17,2,15,47,16,32,36,68,24,22,96,5,94,41,9,59,50},
{26,301,301,122,82,97,28,39,15,24,88,17,11,10,64,74,43,5,18,4,14,32,31,12,44,36,116,105,80},
{26,303,303,170,133,55,78,47,27,36,60,32,23,20,7,5,2,3,11,24,8,9,92,86,10,31,73,21,52},
{26,304,304,153,151,2,33,38,78,82,42,31,11,48,5,43,53,3,75,22,72,69,13,56,10,4,18,14,32},
{26,308,308,135,85,88,56,29,20,68,6,14,27,8,22,77,58,52,28,3,25,13,55,24,42,19,115,97,96},
{26,312,312,171,141,30,32,79,72,50,41,36,2,34,5,52,13,46,92,22,28,69,25,19,9,54,1,53,44},
{26,312,312,179,133,55,78,47,27,36,60,9,41,23,20,7,101,5,2,3,11,24,8,86,10,31,73,21,52},
{26,313,313,185,128,60,68,61,55,31,38,35,25,32,36,10,15,24,7,90,43,4,40,6,73,67,42,1,41},
{26,314,314,170,144,52,92,60,36,27,47,21,31,7,20,2,5,24,11,3,8,97,10,32,9,84,23,78,55},
{26,316,316,140,91,85,6,32,47,54,43,17,15,62,60,42,29,64,5,59,13,16,52,3,19,122,30,112,82},
{26,316,316,165,151,80,71,69,56,40,14,26,2,12,13,35,10,27,44,25,85,18,82,28,17,60,11,50,39},
{26,318,318,163,155,8,26,50,71,76,37,38,20,2,24,22,36,1,35,4,31,48,21,92,3,82,17,79,65},
{26,324,324,179,145,64,81,73,58,48,18,29,17,98,10,45,11,15,31,22,40,72,16,9,13,56,52,6,46},
{26,325,325,163,162,1,12,71,78,74,45,34,11,23,21,36,29,16,6,15,13,9,32,92,7,88,28,85,60},
{26,330,330,162,88,80,22,58,74,14,36,94,71,95,70,25,41,98,42,29,5,26,73,16,13,21,57,55,47},
{26,331,331,176,155,21,48,86,68,49,33,20,27,13,7,50,32,46,19,30,18,8,6,2,90,10,87,78,76},
{26,332,332,180,152,26,45,81,7,19,87,88,5,12,40,36,4,14,99,34,10,24,65,22,21,64,3,61,43},
{26,334,334,183,151,66,85,75,74,34,56,25,19,6,98,31,1,40,33,76,26,61,7,17,9,37,10,35,27},
{26,336,336,187,149,24,34,91,14,10,4,40,85,84,36,45,19,12,7,5,96,26,3,68,22,65,64,21,43},
{26,339,339,175,164,13,60,91,64,39,53,17,2,15,32,25,14,61,31,11,56,100,38,84,55,1,54,8,46},
{26,340,340,157,111,72,39,33,6,27,70,65,21,48,93,64,5,56,4,52,75,29,35,108,90,32,26,84,58},
{26,342,342,175,167,15,37,38,77,67,42,59,7,22,58,1,39,25,17,8,44,24,100,18,98,20,4,80,64},
{26,343,343,134,98,111,51,34,13,21,103,55,69,50,15,66,19,31,28,27,54,22,12,1,129,10,128,32,86},
{26,345,345,129,57,54,105,3,51,33,27,6,21,39,98,79,52,42,74,10,32,62,19,60,40,142,41,102,101},
{26,345,345,144,88,113,63,25,38,100,84,60,101,24,15,21,42,58,9,6,27,117,93,32,3,29,16,74,61},
{26,346,346,183,163,68,95,55,50,78,41,27,5,17,28,42,18,6,11,24,34,88,85,32,21,20,66,54,53},
{26,348,348,192,156,69,87,71,58,63,51,18,105,53,5,47,21,41,30,72,11,19,1,46,9,45,44,8,36},
{26,352,352,145,104,103,25,22,56,80,24,3,19,36,16,20,15,88,57,5,66,61,18,62,31,44,127,119,106},
{26,353,353,153,94,106,82,12,118,76,77,34,48,20,14,6,45,129,58,17,1,16,49,39,33,84,8,74,66},
{26,356,356,135,110,111,55,54,1,51,61,105,30,2,39,10,22,34,64,21,71,43,31,3,42,11,127,116,113},
{26,357,357,196,161,61,100,73,51,46,26,20,24,43,34,23,9,5,19,22,29,14,4,96,11,92,88,7,81},
{26,357,357,196,161,69,92,73,51,38,34,4,43,19,14,23,42,5,9,22,29,24,20,104,88,7,3,84,81},
{26,360,360,161,93,106,80,13,119,90,71,44,36,20,16,15,17,12,135,5,27,19,67,22,109,49,61,6,55},
{26,360,360,192,168,78,90,53,64,75,42,11,21,45,12,31,44,102,17,18,37,24,16,1,19,73,69,60,56},
{26,362,362,182,180,42,58,80,85,57,40,30,52,36,22,28,20,9,5,4,1,33,6,26,102,95,18,88,77},
{26,362,362,182,180,42,58,80,87,55,40,30,52,26,18,11,36,22,7,4,3,31,28,102,6,20,93,88,79},
{26,363,363,175,103,85,18,67,72,49,41,75,84,43,65,30,25,7,34,5,27,35,21,22,136,20,1,123,104},
{26,363,363,183,180,72,108,53,61,69,45,8,37,32,26,55,60,30,2,28,82,33,75,57,1,56,51,9,42},
{26,363,363,188,175,73,102,104,84,28,45,48,36,13,7,8,16,86,6,1,9,19,71,33,70,55,5,43,38},
{26,364,364,146,123,95,28,67,44,68,39,91,55,29,77,20,24,14,6,2,10,61,48,8,36,51,127,125,112},
{26,364,364,152,119,93,26,67,33,31,40,41,2,20,9,113,56,18,49,108,38,71,72,99,14,12,96,85,84},
{26,365,365,154,97,114,57,21,10,9,1,8,11,4,118,36,79,46,59,63,33,13,20,52,48,15,133,132,100},
{26,368,368,200,168,53,35,80,81,50,69,13,22,5,8,48,10,7,1,23,17,120,31,19,37,99,87,25,62},
{26,368,368,209,159,67,92,69,36,39,48,17,59,25,33,3,42,117,20,28,13,7,90,12,6,1,5,83,78},
{26,369,369,140,108,121,72,14,9,13,5,4,20,118,19,100,40,39,60,91,56,62,129,31,98,24,74,6,68},
{26,372,372,191,181,76,105,77,44,36,34,2,32,8,30,17,13,22,4,9,16,5,11,115,48,104,19,86,67},
{26,372,372,200,172,28,45,99,85,83,32,13,7,8,6,1,9,19,54,51,52,101,2,89,43,87,3,49,46},
{26,372,372,216,156,63,93,67,45,68,36,33,30,123,21,48,22,23,8,13,3,5,89,88,6,4,14,10,72},
{26,373,373,178,92,103,81,11,114,9,22,50,88,69,17,4,13,52,32,82,24,26,19,126,58,107,8,74,66},
{26,376,376,145,110,121,99,11,132,92,53,39,14,3,29,67,17,8,9,139,38,23,51,58,100,28,72,7,65},
{26,378,378,195,183,55,50,78,88,54,53,5,17,28,42,18,21,32,34,20,6,11,24,117,41,98,95,27,68},
{26,379,379,199,180,34,43,103,93,66,40,25,9,52,65,27,39,37,15,7,96,22,87,33,21,75,8,67,54},
{26,380,380,169,97,114,57,21,10,9,1,8,11,4,118,36,15,78,79,46,59,33,13,20,52,48,148,132,100},
{26,382,382,183,105,94,25,69,78,27,13,12,1,11,31,10,21,121,97,92,72,20,52,5,107,102,23,98,75},
{26,382,382,208,174,64,56,54,96,75,37,2,52,8,50,7,65,44,102,39,36,30,14,79,78,18,3,63,60},
{26,384,384,200,184,16,55,113,103,88,25,11,14,8,3,5,18,49,13,31,37,96,35,26,87,81,22,61,59},
{26,385,385,200,185,37,61,87,97,81,22,59,35,26,113,16,55,104,88,25,11,14,8,3,5,18,49,13,31},
{26,388,388,148,133,107,26,81,15,45,44,55,129,34,1,43,4,42,38,32,104,75,80,111,18,8,96,93,88},
{26,388,388,165,104,119,63,26,15,11,123,37,97,68,53,47,6,13,28,52,7,20,29,39,5,146,25,126,116},
{26,391,391,158,115,118,53,59,3,121,101,57,47,6,65,44,32,15,13,2,11,17,45,152,12,37,132,25,107},
{26,392,392,168,135,89,46,43,3,40,33,114,37,120,81,77,55,74,143,104,16,47,24,5,69,29,41,6,35},
{26,392,392,200,192,8,65,119,89,75,44,31,13,18,11,15,34,7,4,19,14,117,103,53,38,81,48,5,43},
{26,393,393,145,115,133,30,85,67,66,104,71,1,65,16,73,64,33,23,31,10,13,5,26,144,3,21,129,120},
{26,396,396,153,127,116,11,105,80,58,99,54,22,36,45,97,14,68,87,144,15,35,18,92,20,17,1,88,72},
{26,396,396,164,112,120,47,65,57,63,13,34,97,59,8,21,41,75,6,69,30,25,5,61,38,56,144,135,117},
{26,396,396,219,177,70,107,63,95,61,33,37,50,40,4,31,32,36,112,23,8,7,22,82,16,76,15,66,60},
{26,400,400,208,192,81,111,73,85,50,35,15,20,13,19,44,61,12,7,6,25,52,107,14,97,83,58,3,55},
{26,402,402,211,191,108,40,43,112,99,37,3,46,25,12,13,45,6,32,11,103,18,92,79,28,5,77,23,51},
{26,405,405,217,188,29,55,104,108,97,41,15,40,56,31,9,113,47,46,91,80,28,20,8,1,45,12,44,32},
{26,410,410,155,113,142,84,29,55,116,101,54,12,28,38,61,47,19,3,25,22,15,23,6,56,154,48,152,104},
{26,412,412,181,108,123,93,15,70,68,98,63,20,2,66,8,64,27,38,56,16,11,49,35,44,31,155,133,124},
{26,413,413,222,191,43,40,108,79,51,92,3,37,46,12,25,28,23,45,13,32,6,5,18,114,112,99,11,88},
{26,414,414,167,123,124,44,78,1,125,106,71,34,37,27,48,15,12,35,68,5,3,9,23,17,165,40,141,108},
{26,415,415,224,191,26,17,25,123,9,8,33,35,80,49,67,28,3,30,39,27,31,18,57,124,111,22,101,79},
{26,416,416,178,115,123,107,8,131,104,74,22,20,33,32,7,13,17,5,12,30,44,1,162,6,41,35,134,120},
{26,416,416,194,105,51,66,36,15,21,60,18,39,123,99,104,90,3,96,56,70,14,132,118,47,23,24,95,71},
{26,420,420,233,187,81,106,96,102,35,62,29,25,4,127,33,36,17,15,28,5,90,22,85,2,13,19,63,55},
{26,421,421,229,192,33,62,97,4,29,107,101,25,81,35,132,28,15,17,36,5,86,85,22,13,2,19,63,55},
{26,424,424,222,202,88,114,92,51,79,23,28,11,45,32,18,5,123,110,6,108,13,25,46,12,37,43,3,40},
{26,425,425,232,193,71,122,80,47,29,44,32,18,11,40,63,7,4,3,45,33,42,17,23,113,12,110,104,98},
{26,426,426,233,193,73,35,30,55,5,25,40,81,50,69,33,80,36,68,2,42,31,19,124,24,18,112,98,92},
{26,432,432,200,108,124,92,16,140,99,63,52,37,41,15,22,18,23,11,49,7,42,5,36,38,168,133,2,131},
{26,432,432,225,207,118,89,125,100,29,60,63,107,46,31,82,43,15,76,61,9,10,44,39,4,12,1,11,23},
{26,435,435,240,195,67,128,96,93,51,24,43,5,19,42,14,58,18,34,112,3,102,30,99,6,28,72,22,50},
{26,440,440,233,207,34,60,113,117,108,8,42,16,44,58,24,11,9,2,120,13,37,36,99,31,90,27,68,63},
{26,440,440,252,188,64,124,101,115,100,40,31,53,9,22,15,46,88,87,14,75,73,36,35,4,42,1,38,37},
{26,444,444,208,124,112,46,66,54,37,33,4,28,1,27,20,17,24,71,86,79,111,97,56,15,180,14,139,125},
{26,444,444,252,192,63,129,113,136,3,66,72,123,79,34,11,56,27,25,17,21,51,45,8,9,2,31,30,29},
{26,447,447,255,192,63,129,113,136,69,3,126,72,79,34,11,56,27,25,17,21,51,45,8,9,2,31,30,29},
{26,448,448,232,216,16,67,133,115,56,39,38,1,24,13,17,23,11,69,73,58,101,14,34,99,96,31,87,65},
{26,450,450,261,189,69,120,39,30,101,76,84,9,21,48,141,25,43,8,35,105,88,20,18,2,24,70,22,46},
{26,451,451,249,202,66,136,114,104,31,12,54,43,4,11,39,30,10,3,7,28,23,113,36,98,90,88,26,62},
{26,452,452,253,199,72,127,103,79,53,18,35,55,26,62,56,126,25,44,36,96,7,6,19,13,84,14,76,70},
{26,452,452,256,196,74,122,92,80,41,43,26,48,3,23,39,2,28,20,36,134,8,35,9,27,12,116,104,98},
{26,452,452,256,196,83,113,92,80,46,38,17,36,30,8,28,2,19,34,20,143,7,48,14,41,12,116,104,89},
{26,456,456,231,225,111,114,126,105,35,58,120,3,117,99,27,12,23,1,11,18,10,8,32,62,26,2,30,28},
{26,456,456,231,225,111,114,126,105,35,58,120,3,117,99,27,12,23,1,11,28,30,62,18,10,8,2,32,26},
{26,458,458,240,218,89,129,117,64,59,5,46,8,69,39,58,45,1,21,19,18,111,101,16,2,93,23,85,68},
{26,460,460,237,223,34,72,117,110,107,20,31,23,8,15,39,54,33,17,22,21,12,9,120,3,116,5,113,111},
{26,464,464,201,162,101,50,51,49,1,52,124,38,59,20,8,116,85,4,48,12,32,7,73,66,31,178,147,139},
{26,471,471,237,234,34,99,101,110,96,31,65,14,138,61,45,2,43,60,124,16,37,18,17,77,1,76,19,56},
{26,471,471,263,208,55,153,107,113,98,15,37,36,53,110,101,6,95,39,1,22,13,17,21,9,4,57,56,52},
{26,472,472,195,118,159,77,41,200,115,68,89,47,21,110,162,37,50,113,78,22,8,2,6,20,13,14,63,56},
{26,475,475,242,233,39,85,109,98,61,53,30,23,46,12,64,37,20,4,16,41,66,24,36,135,133,116,25,91},
{26,478,478,246,232,14,110,108,99,65,96,34,31,2,45,61,136,60,43,133,17,18,37,16,77,76,1,19,56},
{26,484,484,196,175,113,62,51,11,40,122,97,29,132,64,69,27,37,25,71,1,70,17,10,7,187,24,156,141},
{26,484,484,229,106,149,63,43,57,135,26,37,15,11,4,23,78,19,103,54,59,55,49,5,68,200,64,152,132},
{26,484,484,263,221,100,121,99,76,41,47,35,6,53,79,21,23,64,24,142,122,40,37,3,29,84,81,26,55},
{26,485,485,294,191,67,124,36,31,5,26,84,61,99,91,70,80,23,38,107,51,100,10,92,45,90,2,49,47},
{26,487,487,275,212,63,149,124,105,109,23,126,64,37,4,33,103,88,36,70,22,14,5,16,43,8,11,30,27},
{26,491,491,206,143,142,1,141,63,81,134,117,18,99,61,80,17,168,31,151,10,51,41,28,52,4,24,96,76},
{26,492,492,224,123,145,101,22,167,121,65,51,88,14,37,56,23,48,87,180,147,30,15,33,45,27,6,93,72},
{26,492,492,271,221,98,123,92,41,31,52,55,10,21,51,73,25,54,19,16,39,35,148,129,14,12,27,115,100},
{26,493,493,253,240,13,45,22,21,41,98,74,88,104,1,20,23,4,57,72,60,14,155,46,56,40,136,106,96},
{26,494,494,249,245,92,72,81,104,57,88,26,31,63,9,46,44,21,5,16,157,43,141,2,42,8,40,114,82},
{26,495,495,234,115,146,84,31,177,32,52,12,20,114,81,30,9,21,72,51,33,91,8,85,172,147,89,2,87},
{26,496,496,251,245,99,146,124,127,16,14,26,43,2,12,18,38,121,3,118,30,21,22,41,105,88,1,23,64},
{26,497,497,195,164,138,26,112,121,69,105,90,52,17,35,94,27,212,59,65,28,12,16,23,37,7,30,153,132},
{26,497,497,208,164,125,39,37,49,25,12,44,65,71,23,61,48,130,101,21,80,6,74,112,29,188,38,159,150},
{26,497,497,229,127,141,113,14,155,116,80,33,22,35,56,38,17,4,31,21,10,201,53,6,47,36,44,152,144},
{26,498,498,285,213,72,141,97,68,123,69,29,39,66,144,116,10,36,13,9,4,1,20,90,12,5,14,78,70},
{26,499,499,207,144,148,64,76,4,152,124,82,1,65,24,19,33,5,14,29,47,94,42,40,199,2,38,168,132}
};


//【座標圧縮】O(n log n)
/*
* 大きさ n の多重集合 a を 0 以上 |a| 未満の範囲に座標圧縮した結果を a_cp に格納し，その要素数を返す．
* また xs[j] に圧縮された座標 j に対応する元の座標を格納する．
*
* a に重複する要素がなければ，a_cp[i] は a[i] が昇順で何番目かを表し，
* xs[j] は昇順で j 番目の要素が何かを表す．
*/
template <class T>
int coordinate_compression(const vector<T>& a, vi& a_cp, vector<T>* xs = nullptr) {
	// verify : https://atcoder.jp/contests/abc036/tasks/abc036_c

	int n = sz(a);
	if (xs == nullptr) xs = new vector<T>;

	// *xs : a の x 座標のユニークな昇順列
	*xs = a;
	uniq(*xs);

	// a[i] が xs において何番目かを求める．
	a_cp.resize(n);
	rep(i, n) a_cp[i] = lbpos(*xs, a[i]);

	return sz(*xs);
}


int main() {
//	input_from_file("input.txt");
//	output_to_file("output.txt");
	
	int m = sz(ans);

	int n;
	cin >> n;

	vi a(n);
	cin >> a;

	if (n == 1) {
		cout << a[0] << endl;
		rep(i, a[0]) {
			rep(j, a[0]) cout << 'A';
			cout << endl;
		}
		return 0;
	}

	rep(j, m) {
		if (ans[j][0] != n) continue;

		vi b;
		repi(k, 3, sz(ans[j]) - 1) b.push_back(ans[j][k]);

		vi sb(b);
		sort(all(sb));
		if (a != sb) continue;

		vi bc;
		coordinate_compression(b, bc);

		int L = ans[j][1];
		vvc res(L, vc(L, -1));
		
		int pt = 0;
		rep(i, L) rep(j, L) {
			if (res[i][j] != -1) continue;

			rep(u, b[pt]) rep(v, b[pt]) {
				res[i + u][j + v] = 'A' + bc[pt];
			}
			pt++;
		}

		cout << L << endl;
		rep(i, L) {
			rep(j, L) cout << res[i][j];
			cout << endl;
		}
		return 0;
	}

	EXIT(-1);
}