結果
| 問題 |
No.1953 ８
|
| ユーザー |
 ecottea
|
| 提出日時 | 2025-07-16 22:54:31 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 32 ms / 2,000 ms |
| コード長 | 37,036 bytes |
| コンパイル時間 | 9,829 ms |
| コンパイル使用メモリ | 580,904 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-07-16 22:54:45 |
| 合計ジャッジ時間 | 14,664 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#ifndef HIDDEN_IN_VS // 折りたたみ用
// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS
// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;
// 型名の短縮
using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）
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);
int DX[4] = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
int DY[4] = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;
// 入出力高速化
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##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）
#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#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 powi(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 int getb(T set, int i) { return (set >> i) & T(1); }
template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod
// 演算子オーバーロード
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 = modint998244353;
using mint = static_modint<(int)1e9+7>;
//using mint = modint; // mint::set_mod(m);
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;
#endif
#ifdef _MSC_VER // 手元環境（Visual Studio）
#include "local.hpp"
#else // 提出用（gcc）
int mute_dump = 0;
int frac_print = 0;
#if __has_include(<atcoder/all>)
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; }
}
#endif
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) : 32; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }
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 dump(...)
#define dumpel(v)
#define dump_math(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す
#endif
/*
愚直を書く．別に C++ で書く必要はないので Mathematica 上で用意する．
wgt = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
ans = Accumulate@
Table[Total[wgt[[# + 1]] & /@ IntegerDigits[i, 10]], {i, 0,
100000}];
data = Association@
Table[key -> ans[[FromDigits[key, 10] + 1]], {len, 0, 5}, {key,
Tuples[Range[0, 9], len]}];
これを全自動スライド bitDP 学習器にぶち込んで係数列を自動生成する．
さすがに時間がかかりすぎるので，係数列のスパース性を仮定して無理やり高速化する．
*/
ull solve(vi ds) {
using vull = vector<ull>;
using vvull = vector<vull>;
// -------------------- 生成器からの出力を貼る --------------------
vvl coef_cp{ {-100, 108, 7917, -24663, 16658}, {-100, 106, 7765, -24178, 16327}, {-100, 104, 7613, -23693, 15996}, {-100, 102, 7461, -23208, 15665}, {-100, 100, 7308, -22721, 15333}, {-100, 98, 7156, -22236, 15002}, {-100, 96, 7003, -21749, 14670}, {-100, 94, 6851, -21264, 14339}, {-100, 92, 6697, -20775, 14006}, {-100, 90, 6544, -20288, 13674}, {-100, 89, 6468, -20046, 13509}, {-100, 88, 6393, -19806, 13345}, {-100, 87, 6318, -19566, 13181}, {-100, 86, 6243, -19326, 13017}, {-100, 85, 6167, -19084, 12852}, {-100, 84, 6092, -18844, 12688}, {-100, 83, 6016, -18602, 12523}, {-100, 82, 5941, -18362, 12359}, {-100, 81, 5864, -18118, 12193}, {-100, 80, 5788, -17876, 12028}, {-100, 79, 5712, -17634, 11863}, {-100, 78, 5637, -17394, 11699}, {-100, 77, 5562, -17154, 11535}, {-100, 76, 5487, -16914, 11371}, {-100, 75, 5411, -16672, 11206}, {-100, 74, 5336, -16432, 11042}, {-100, 73, 5260, -16190, 10877}, {-100, 72, 5185, -15950, 10713}, {-100, 71, 5108, -15706, 10547}, {-100, 70, 5032, -15464, 10382}, {-100, 69, 4956, -15222, 10217}, {-100, 68, 4881, -14982, 10053}, {-100, 67, 4806, -14742, 9889}, {-100, 66, 4731, -14502, 9725}, {-100, 65, 4655, -14260, 9560}, {-100, 64, 4580, -14020, 9396}, {-100, 63, 4504, -13778, 9231}, {-100, 62, 4429, -13538, 9067}, {-100, 61, 4352, -13294, 8901}, {-100, 60, 4276, -13052, 8736}, {-100, 59, 4199, -12808, 8570}, {-100, 58, 4123, -12566, 8405}, {-100, 57, 4047, -12324, 8240}, {-100, 56, 3971, -12082, 8075}, {-100, 55, 3894, -11838, 7909}, {-100, 54, 3818, -11596, 7744}, {-100, 53, 3741, -11352, 7578}, {-100, 52, 3665, -11110, 7413}, {-100, 51, 3587, -10864, 7246}, {-100, 50, 3510, -10620, 7080}, {-100, 49, 3434, -10378, 6915}, {-100, 48, 3359, -10138, 6751}, {-100, 47, 3284, -9898, 6587}, {-100, 46, 3209, -9658, 6423}, {-100, 45, 3133, -9416, 6258}, {-100, 44, 3058, -9176, 6094}, {-100, 43, 2982, -8934, 5929}, {-100, 42, 2907, -8694, 5765}, {-100, 41, 2830, -8450, 5599}, {-100, 40, 2754, -8208, 5434}, {-100, 39, 2677, -7964, 5268}, {-100, 38, 2601, -7722, 5103}, {-100, 37, 2525, -7480, 4938}, {-100, 36, 2449, -7238, 4773}, {-100, 35, 2372, -6994, 4607}, {-100, 34, 2296, -6752, 4442}, {-100, 33, 2219, -6508, 4276}, {-100, 32, 2143, -6266, 4111}, {-100, 31, 2065, -6020, 3944}, {-100, 30, 1988, -5776, 3778}, {-100, 29, 1912, -5534, 3613}, {-100, 28, 1837, -5294, 3449}, {-100, 27, 1762, -5054, 3285}, {-100, 26, 1687, -4814, 3121}, {-100, 25, 1611, -4572, 2956}, {-100, 24, 1536, -4332, 2792}, {-100, 23, 1460, -4090, 2627}, {-100, 22, 1385, -3850, 2463}, {-100, 21, 1308, -3606, 2297}, {-100, 20, 1232, -3364, 2132}, {-100, 19, 1154, -3118, 1965}, {-100, 18, 1077, -2874, 1799}, {-100, 17, 1000, -2630, 1633}, {-100, 16, 923, -2386, 1467}, {-100, 15, 845, -2140, 1300}, {-100, 14, 768, -1896, 1134}, {-100, 13, 690, -1650, 967}, {-100, 12, 613, -1406, 801}, {-100, 11, 534, -1158, 633}, {-100, 10, 456, -912, 466}, {-100, 9, 379, -668, 300}, {-100, 8, 303, -426, 135}, {-100, 7, 227, -184, -30}, {-100, 6, 151, 58, -195}, {-100, 5, 74, 302, -361}, {-100, 4, -2, 544, -526}, {-100, 3, -79, 788, -692}, {-100, 2, -155, 1030, -857}, {-100, 1, -233, 1276, -1024}, {-100, 0, -310, 1520, -1190}, {-100, 0, -310, 1519, -1189}, {-100, 0, -309, 1516, -1187}, {-100, 0, -308, 1513, -1185}, {-100, 0, -307, 1510, -1183}, {-100, 0, -307, 1509, -1182}, {-100, 0, -306, 1506, -1180}, {-100, 0, -306, 1505, -1179}, {-100, 0, -305, 1502, -1177}, {-100, 0, -306, 1503, -1177}, {-100, 0, -306, 1502, -1176}, {-100, 0, -305, 1499, -1174}, {-100, 0, -303, 1494, -1171}, {-100, 0, -301, 1489, -1168}, {-100, 0, -299, 1484, -1165}, {-100, 0, -298, 1481, -1163}, {-100, 0, -296, 1476, -1160}, {-100, 0, -295, 1473, -1158}, {-100, 0, -293, 1468, -1155}, {-100, 0, -293, 1467, -1154}, {-100, 0, -292, 1464, -1152}, {-100, 0, -291, 1461, -1150}, {-100, 0, -289, 1456, -1147}, {-100, 0, -287, 1451, -1144}, {-100, 0, -285, 1446, -1141}, {-100, 0, -284, 1443, -1139}, {-100, 0, -282, 1438, -1136}, {-100, 0, -281, 1435, -1134}, {-100, 0, -279, 1430, -1131}, {-100, 0, -279, 1429, -1130}, {-100, 0, -278, 1426, -1128}, {-100, 0, -277, 1423, -1126}, {-100, 0, -275, 1418, -1123}, {-100, 0, -273, 1413, -1120}, {-100, 0, -271, 1408, -1117}, {-100, 0, -270, 1405, -1115}, {-100, 0, -268, 1400, -1112}, {-100, 0, -267, 1397, -1110}, {-100, 0, -265, 1392, -1107}, {-100, 0, -265, 1391, -1106}, {-100, 0, -264, 1388, -1104}, {-100, 0, -264, 1387, -1103}, {-100, 0, -263, 1384, -1101}, {-100, 0, -262, 1381, -1099}, {-100, 0, -261, 1378, -1097}, {-100, 0, -261, 1377, -1096}, {-100, 0, -260, 1374, -1094}, {-100, 0, -260, 1373, -1093}, {-100, 0, -259, 1370, -1091}, {-100, 0, -260, 1371, -1091}, {-100, 0, -260, 1370, -1090}, {-100, 0, -259, 1367, -1088}, {-100, 0, -257, 1362, -1085}, {-100, 0, -255, 1357, -1082}, {-100, 0, -253, 1352, -1079}, {-100, 0, -252, 1349, -1077}, {-100, 0, -250, 1344, -1074}, {-100, 0, -249, 1341, -1072}, {-100, 0, -247, 1336, -1069}, {-100, 0, -247, 1335, -1068}, {-100, 0, -246, 1332, -1066}, {-100, 0, -246, 1331, -1065}, {-100, 0, -245, 1328, -1063}, {-100, 0, -244, 1325, -1061}, {-100, 0, -243, 1322, -1059}, {-100, 0, -243, 1321, -1058}, {-100, 0, -242, 1318, -1056}, {-100, 0, -242, 1317, -1055}, {-100, 0, -241, 1314, -1053}, {-100, 0, -242, 1315, -1053}, {-100, 0, -242, 1314, -1052}, {-100, 0, -241, 1311, -1050}, {-100, 0, -239, 1306, -1047}, {-100, 0, -237, 1301, -1044}, {-100, 0, -235, 1296, -1041}, {-100, 0, -234, 1293, -1039}, {-100, 0, -232, 1288, -1036}, {-100, 0, -231, 1285, -1034}, {-100, 0, -229, 1280, -1031}, {-100, 0, -229, 1279, -1030}, {-100, 0, -228, 1276, -1028}, {-100, 0, -229, 1277, -1028}, {-100, 0, -229, 1276, -1027}, {-100, 0, -229, 1275, -1026}, {-100, 0, -229, 1274, -1025}, {-100, 0, -230, 1275, -1025}, {-100, 0, -230, 1274, -1024}, {-100, 0, -231, 1275, -1024}, {-100, 0, -231, 1274, -1023}, {-100, 0, -233, 1277, -1024}, {-100, 0, -234, 1278, -1024}, {-100, 0, -234, 1277, -1023}, {-100, 0, -233, 1274, -1021}, {-100, 0, -232, 1271, -1019}, {-100, 0, -231, 1268, -1017}, {-100, 0, -231, 1267, -1016}, {-100, 0, -230, 1264, -1014}, {-100, 0, -230, 1263, -1013}, {-100, 0, -229, 1260, -1011}, {-100, 0, -230, 1261, -1011}, {-100, 0, -230, 1260, -1010}, {-100, 0, -230, 1259, -1009}, {-100, 0, -229, 1256, -1007}, {-100, 0, -228, 1253, -1005}, {-100, 0, -227, 1250, -1003}, {-100, 0, -227, 1249, -1002}, {-100, 0, -226, 1246, -1000}, {-100, 0, -226, 1245, -999}, {-100, 0, -225, 1242, -997}, {-100, 0, -226, 1243, -997}, {-100, 0, -226, 1242, -996}, {-100, 0, -225, 1239, -994}, {-100, 0, -223, 1234, -991}, {-100, 0, -221, 1229, -988}, {-100, 0, -219, 1224, -985}, {-100, 0, -218, 1221, -983}, {-100, 0, -216, 1216, -980}, {-100, 0, -215, 1213, -978}, {-100, 0, -213, 1208, -975}, {-100, 0, -213, 1207, -974}, {-100, 0, -212, 1204, -972}, {-100, 0, -211, 1201, -970}, {-100, 0, -209, 1196, -967}, {-100, 0, -207, 1191, -964}, {-100, 0, -205, 1186, -961}, {-100, 0, -204, 1183, -959}, {-100, 0, -202, 1178, -956}, {-100, 0, -201, 1175, -954}, {-100, 0, -199, 1170, -951}, {-100, 0, -199, 1169, -950}, {-100, 0, -198, 1166, -948}, {-100, 0, -197, 1163, -946}, {-100, 0, -195, 1158, -943}, {-100, 0, -193, 1153, -940}, {-100, 0, -191, 1148, -937}, {-100, 0, -190, 1145, -935}, {-100, 0, -188, 1140, -932}, {-100, 0, -187, 1137, -930}, {-100, 0, -185, 1132, -927}, {-100, 0, -185, 1131, -926}, {-100, 0, -184, 1128, -924}, {-100, 0, -184, 1127, -923}, {-100, 0, -183, 1124, -921}, {-100, 0, -182, 1121, -919}, {-100, 0, -181, 1118, -917}, {-100, 0, -181, 1117, -916}, {-100, 0, -180, 1114, -914}, {-100, 0, -180, 1113, -913}, {-100, 0, -179, 1110, -911}, {-100, 0, -180, 1111, -911}, {-100, 0, -180, 1110, -910}, {-100, 0, -179, 1107, -908}, {-100, 0, -177, 1102, -905}, {-100, 0, -175, 1097, -902}, {-100, 0, -173, 1092, -899}, {-100, 0, -172, 1089, -897}, {-100, 0, -170, 1084, -894}, {-100, 0, -169, 1081, -892}, {-100, 0, -167, 1076, -889}, {-100, 0, -167, 1075, -888}, {-100, 0, -166, 1072, -886}, {-100, 0, -166, 1071, -885}, {-100, 0, -165, 1068, -883}, {-100, 0, -164, 1065, -881}, {-100, 0, -163, 1062, -879}, {-100, 0, -163, 1061, -878}, {-100, 0, -162, 1058, -876}, {-100, 0, -162, 1057, -875}, {-100, 0, -161, 1054, -873}, {-100, 0, -162, 1055, -873}, {-100, 0, -162, 1054, -872}, {-100, 0, -161, 1051, -870}, {-100, 0, -159, 1046, -867}, {-100, 0, -157, 1041, -864}, {-100, 0, -155, 1036, -861}, {-100, 0, -154, 1033, -859}, {-100, 0, -152, 1028, -856}, {-100, 0, -151, 1025, -854}, {-100, 0, -149, 1020, -851}, {-100, 0, -149, 1019, -850}, {-100, 0, -148, 1016, -848}, {-100, 0, -149, 1017, -848}, {-100, 0, -149, 1016, -847}, {-100, 0, -149, 1015, -846}, {-100, 0, -149, 1014, -845}, {-100, 0, -150, 1015, -845}, {-100, 0, -150, 1014, -844}, {-100, 0, -151, 1015, -844}, {-100, 0, -151, 1014, -843}, {-100, 0, -153, 1017, -844}, {-100, 0, -154, 1018, -844}, {-100, 0, -154, 1017, -843}, {-100, 0, -153, 1014, -841}, {-100, 0, -152, 1011, -839}, {-100, 0, -151, 1008, -837}, {-100, 0, -151, 1007, -836}, {-100, 0, -150, 1004, -834}, {-100, 0, -150, 1003, -833}, {-100, 0, -149, 1000, -831}, {-100, 0, -150, 1001, -831}, {-100, 0, -150, 1000, -830}, {-100, 0, -150, 999, -829}, {-100, 0, -149, 996, -827}, {-100, 0, -148, 993, -825}, {-100, 0, -147, 990, -823}, {-100, 0, -147, 989, -822}, {-100, 0, -146, 986, -820}, {-100, 0, -146, 985, -819}, {-100, 0, -145, 982, -817}, {-100, 0, -146, 983, -817}, {-100, 0, -146, 982, -816}, {-100, 0, -145, 979, -814}, {-100, 0, -143, 974, -811}, {-100, 0, -141, 969, -808}, {-100, 0, -139, 964, -805}, {-100, 0, -138, 961, -803}, {-100, 0, -136, 956, -800}, {-100, 0, -135, 953, -798}, {-100, 0, -133, 948, -795}, {-100, 0, -133, 947, -794}, {-100, 0, -132, 944, -792}, {-100, 0, -131, 941, -790}, {-100, 0, -129, 936, -787}, {-100, 0, -127, 931, -784}, {-100, 0, -125, 926, -781}, {-100, 0, -124, 923, -779}, {-100, 0, -122, 918, -776}, {-100, 0, -121, 915, -774}, {-100, 0, -119, 910, -771}, {-100, 0, -119, 909, -770}, {-100, 0, -118, 906, -768}, {-100, 0, -117, 903, -766}, {-100, 0, -115, 898, -763}, {-100, 0, -113, 893, -760}, {-100, 0, -111, 888, -757}, {-100, 0, -110, 885, -755}, {-100, 0, -108, 880, -752}, {-100, 0, -107, 877, -750}, {-100, 0, -105, 872, -747}, {-100, 0, -105, 871, -746}, {-100, 0, -104, 868, -744}, {-100, 0, -104, 867, -743}, {-100, 0, -103, 864, -741}, {-100, 0, -102, 861, -739}, {-100, 0, -101, 858, -737}, {-100, 0, -101, 857, -736}, {-100, 0, -100, 854, -734}, {-100, 0, -100, 853, -733}, {-100, 0, -99, 850, -731}, {-100, 0, -100, 851, -731}, {-100, 0, -100, 850, -730}, {-100, 0, -99, 847, -728}, {-100, 0, -97, 842, -725}, {-100, 0, -95, 837, -722}, {-100, 0, -93, 832, -719}, {-100, 0, -92, 829, -717}, {-100, 0, -90, 824, -714}, {-100, 0, -89, 821, -712}, {-100, 0, -87, 816, -709}, {-100, 0, -87, 815, -708}, {-100, 0, -86, 812, -706}, {-100, 0, -86, 811, -705}, {-100, 0, -85, 808, -703}, {-100, 0, -84, 805, -701}, {-100, 0, -83, 802, -699}, {-100, 0, -83, 801, -698}, {-100, 0, -82, 798, -696}, {-100, 0, -82, 797, -695}, {-100, 0, -81, 794, -693}, {-100, 0, -82, 795, -693}, {-100, 0, -82, 794, -692}, {-100, 0, -81, 791, -690}, {-100, 0, -79, 786, -687}, {-100, 0, -77, 781, -684}, {-100, 0, -75, 776, -681}, {-100, 0, -74, 773, -679}, {-100, 0, -72, 768, -676}, {-100, 0, -71, 765, -674}, {-100, 0, -69, 760, -671}, {-100, 0, -69, 759, -670}, {-100, 0, -68, 756, -668}, {-100, 0, -69, 757, -668}, {-100, 0, -69, 756, -667}, {-100, 0, -69, 755, -666}, {-100, 0, -69, 754, -665}, {-100, 0, -70, 755, -665}, {-100, 0, -70, 754, -664}, {-100, 0, -71, 755, -664}, {-100, 0, -71, 754, -663}, {-100, 0, -73, 757, -664}, {-100, 0, -74, 758, -664}, {-100, 0, -74, 757, -663}, {-100, 0, -73, 754, -661}, {-100, 0, -72, 751, -659}, {-100, 0, -71, 748, -657}, {-100, 0, -71, 747, -656}, {-100, 0, -70, 744, -654}, {-100, 0, -70, 743, -653}, {-100, 0, -69, 740, -651}, {-100, 0, -70, 741, -651}, {-100, 0, -70, 740, -650}, {-100, 0, -71, 741, -650}, {-100, 0, -71, 740, -649}, {-100, 0, -71, 739, -648}, {-100, 0, -71, 738, -647}, {-100, 0, -72, 739, -647}, {-100, 0, -72, 738, -646}, {-100, 0, -73, 739, -646}, {-100, 0, -73, 738, -645}, {-100, 0, -75, 741, -646}, {-100, 0, -76, 742, -646}, {-100, 0, -76, 741, -645}, {-100, 0, -75, 738, -643}, {-100, 0, -74, 735, -641}, {-100, 0, -73, 732, -639}, {-100, 0, -73, 731, -638}, {-100, 0, -72, 728, -636}, {-100, 0, -72, 727, -635}, {-100, 0, -71, 724, -633}, {-100, 0, -72, 725, -633}, {-100, 0, -72, 724, -632}, {-100, 0, -72, 723, -631}, {-100, 0, -71, 720, -629}, {-100, 0, -70, 717, -627}, {-100, 0, -69, 714, -625}, {-100, 0, -69, 713, -624}, {-100, 0, -68, 710, -622}, {-100, 0, -68, 709, -621}, {-100, 0, -67, 706, -619}, {-100, 0, -68, 707, -619}, {-100, 0, -68, 706, -618}, {-100, 0, -68, 705, -617}, {-100, 0, -67, 702, -615}, {-100, 0, -66, 699, -613}, {-100, 0, -65, 696, -611}, {-100, 0, -65, 695, -610}, {-100, 0, -64, 692, -608}, {-100, 0, -64, 691, -607}, {-100, 0, -63, 688, -605}, {-100, 0, -64, 689, -605}, {-100, 0, -64, 688, -604}, {-100, 0, -65, 689, -604}, {-100, 0, -65, 688, -603}, {-100, 0, -65, 687, -602}, {-100, 0, -65, 686, -601}, {-100, 0, -66, 687, -601}, {-100, 0, -66, 686, -600}, {-100, 0, -67, 687, -600}, {-100, 0, -67, 686, -599}, {-100, 0, -69, 689, -600}, {-100, 0, -70, 690, -600}, {-100, 0, -70, 689, -599}, {-100, 0, -69, 686, -597}, {-100, 0, -68, 683, -595}, {-100, 0, -67, 680, -593}, {-100, 0, -67, 679, -592}, {-100, 0, -66, 676, -590}, {-100, 0, -66, 675, -589}, {-100, 0, -65, 672, -587}, {-100, 0, -66, 673, -587}, {-100, 0, -66, 672, -586}, {-100, 0, -67, 673, -586}, {-100, 0, -67, 672, -585}, {-100, 0, -67, 671, -584}, {-100, 0, -67, 670, -583}, {-100, 0, -68, 671, -583}, {-100, 0, -68, 670, -582}, {-100, 0, -69, 671, -582}, {-100, 0, -69, 670, -581}, {-100, 0, -71, 673, -582}, {-100, 0, -72, 674, -582}, {-100, 0, -72, 673, -581}, {-100, 0, -71, 670, -579}, {-100, 0, -70, 667, -577}, {-100, 0, -69, 664, -575}, {-100, 0, -69, 663, -574}, {-100, 0, -68, 660, -572}, {-100, 0, -68, 659, -571}, {-100, 0, -67, 656, -569}, {-100, 0, -68, 657, -569}, {-100, 0, -68, 656, -568}, {-100, 0, -70, 659, -569}, {-100, 0, -71, 660, -569}, {-100, 0, -72, 661, -569}, {-100, 0, -73, 662, -569}, {-100, 0, -75, 665, -570}, {-100, 0, -76, 666, -570}, {-100, 0, -78, 669, -571}, {-100, 0, -79, 670, -571}, {-100, 0, -82, 675, -573}, {-100, 0, -84, 678, -574}, {-100, 0, -85, 679, -574}, {-100, 0, -85, 678, -573}, {-100, 0, -85, 677, -572}, {-100, 0, -85, 676, -571}, {-100, 0, -86, 677, -571}, {-100, 0, -86, 676, -570}, {-100, 0, -87, 677, -570}, {-100, 0, -87, 676, -569}, {-100, 0, -89, 679, -570}, {-100, 0, -90, 680, -570}, {-100, 0, -90, 679, -569}, {-100, 0, -89, 676, -567}, {-100, 0, -88, 673, -565}, {-100, 0, -87, 670, -563}, {-100, 0, -87, 669, -562}, {-100, 0, -86, 666, -560}, {-100, 0, -86, 665, -559}, {-100, 0, -85, 662, -557}, {-100, 0, -86, 663, -557}, {-100, 0, -86, 662, -556}, {-100, 0, -85, 659, -554}, {-100, 0, -83, 654, -551}, {-100, 0, -81, 649, -548}, {-100, 0, -79, 644, -545}, {-100, 0, -78, 641, -543}, {-100, 0, -76, 636, -540}, {-100, 0, -75, 633, -538}, {-100, 0, -73, 628, -535}, {-100, 0, -73, 627, -534}, {-100, 0, -72, 624, -532}, {-100, 0, -71, 621, -530}, {-100, 0, -69, 616, -527}, {-100, 0, -67, 611, -524}, {-100, 0, -65, 606, -521}, {-100, 0, -64, 603, -519}, {-100, 0, -62, 598, -516}, {-100, 0, -61, 595, -514}, {-100, 0, -59, 590, -511}, {-100, 0, -59, 589, -510}, {-100, 0, -58, 586, -508}, {-100, 0, -57, 583, -506}, {-100, 0, -55, 578, -503}, {-100, 0, -53, 573, -500}, {-100, 0, -51, 568, -497}, {-100, 0, -50, 565, -495}, {-100, 0, -48, 560, -492}, {-100, 0, -47, 557, -490}, {-100, 0, -45, 552, -487}, {-100, 0, -45, 551, -486}, {-100, 0, -44, 548, -484}, {-100, 0, -44, 547, -483}, {-100, 0, -43, 544, -481}, {-100, 0, -42, 541, -479}, {-100, 0, -41, 538, -477}, {-100, 0, -41, 537, -476}, {-100, 0, -40, 534, -474}, {-100, 0, -40, 533, -473}, {-100, 0, -39, 530, -471}, {-100, 0, -40, 531, -471}, {-100, 0, -40, 530, -470}, {-100, 0, -39, 527, -468}, {-100, 0, -37, 522, -465}, {-100, 0, -35, 517, -462}, {-100, 0, -33, 512, -459}, {-100, 0, -32, 509, -457}, {-100, 0, -30, 504, -454}, {-100, 0, -29, 501, -452}, {-100, 0, -27, 496, -449}, {-100, 0, -27, 495, -448}, {-100, 0, -26, 492, -446}, {-100, 0, -26, 491, -445}, {-100, 0, -25, 488, -443}, {-100, 0, -24, 485, -441}, {-100, 0, -23, 482, -439}, {-100, 0, -23, 481, -438}, {-100, 0, -22, 478, -436}, {-100, 0, -22, 477, -435}, {-100, 0, -21, 474, -433}, {-100, 0, -22, 475, -433}, {-100, 0, -22, 474, -432}, {-100, 0, -21, 471, -430}, {-100, 0, -19, 466, -427}, {-100, 0, -17, 461, -424}, {-100, 0, -15, 456, -421}, {-100, 0, -14, 453, -419}, {-100, 0, -12, 448, -416}, {-100, 0, -11, 445, -414}, {-100, 0, -9, 440, -411}, {-100, 0, -9, 439, -410}, {-100, 0, -8, 436, -408}, {-100, 0, -9, 437, -408}, {-100, 0, -9, 436, -407}, {-100, 0, -9, 435, -406}, {-100, 0, -9, 434, -405}, {-100, 0, -10, 435, -405}, {-100, 0, -10, 434, -404}, {-100, 0, -11, 435, -404}, {-100, 0, -11, 434, -403}, {-100, 0, -13, 437, -404}, {-100, 0, -14, 438, -404}, {-100, 0, -14, 437, -403}, {-100, 0, -13, 434, -401}, {-100, 0, -12, 431, -399}, {-100, 0, -11, 428, -397}, {-100, 0, -11, 427, -396}, {-100, 0, -10, 424, -394}, {-100, 0, -10, 423, -393}, {-100, 0, -9, 420, -391}, {-100, 0, -10, 421, -391}, {-100, 0, -10, 420, -390}, {-100, 0, -11, 421, -390}, {-100, 0, -11, 420, -389}, {-100, 0, -11, 419, -388}, {-100, 0, -11, 418, -387}, {-100, 0, -12, 419, -387}, {-100, 0, -12, 418, -386}, {-100, 0, -13, 419, -386}, {-100, 0, -13, 418, -385}, {-100, 0, -15, 421, -386}, {-100, 0, -16, 422, -386}, {-100, 0, -16, 421, -385}, {-100, 0, -15, 418, -383}, {-100, 0, -14, 415, -381}, {-100, 0, -13, 412, -379}, {-100, 0, -13, 411, -378}, {-100, 0, -12, 408, -376}, {-100, 0, -12, 407, -375}, {-100, 0, -11, 404, -373}, {-100, 0, -12, 405, -373}, {-100, 0, -12, 404, -372}, {-100, 0, -12, 403, -371}, {-100, 0, -11, 400, -369}, {-100, 0, -10, 397, -367}, {-100, 0, -9, 394, -365}, {-100, 0, -9, 393, -364}, {-100, 0, -8, 390, -362}, {-100, 0, -8, 389, -361}, {-100, 0, -7, 386, -359}, {-100, 0, -8, 387, -359}, {-100, 0, -8, 386, -358}, {-100, 0, -8, 385, -357}, {-100, 0, -7, 382, -355}, {-100, 0, -6, 379, -353}, {-100, 0, -5, 376, -351}, {-100, 0, -5, 375, -350}, {-100, 0, -4, 372, -348}, {-100, 0, -4, 371, -347}, {-100, 0, -3, 368, -345}, {-100, 0, -4, 369, -345}, {-100, 0, -4, 368, -344}, {-100, 0, -5, 369, -344}, {-100, 0, -5, 368, -343}, {-100, 0, -5, 367, -342}, {-100, 0, -5, 366, -341}, {-100, 0, -6, 367, -341}, {-100, 0, -6, 366, -340}, {-100, 0, -7, 367, -340}, {-100, 0, -7, 366, -339}, {-100, 0, -9, 369, -340}, {-100, 0, -10, 370, -340}, {-100, 0, -10, 369, -339}, {-100, 0, -9, 366, -337}, {-100, 0, -8, 363, -335}, {-100, 0, -7, 360, -333}, {-100, 0, -7, 359, -332}, {-100, 0, -6, 356, -330}, {-100, 0, -6, 355, -329}, {-100, 0, -5, 352, -327}, {-100, 0, -6, 353, -327}, {-100, 0, -6, 352, -326}, {-100, 0, -7, 353, -326}, {-100, 0, -7, 352, -325}, {-100, 0, -7, 351, -324}, {-100, 0, -7, 350, -323}, {-100, 0, -8, 351, -323}, {-100, 0, -8, 350, -322}, {-100, 0, -9, 351, -322}, {-100, 0, -9, 350, -321}, {-100, 0, -11, 353, -322}, {-100, 0, -12, 354, -322}, {-100, 0, -12, 353, -321}, {-100, 0, -11, 350, -319}, {-100, 0, -10, 347, -317}, {-100, 0, -9, 344, -315}, {-100, 0, -9, 343, -314}, {-100, 0, -8, 340, -312}, {-100, 0, -8, 339, -311}, {-100, 0, -7, 336, -309}, {-100, 0, -8, 337, -309}, {-100, 0, -8, 336, -308}, {-100, 0, -10, 339, -309}, {-100, 0, -11, 340, -309}, {-100, 0, -12, 341, -309}, {-100, 0, -13, 342, -309}, {-100, 0, -15, 345, -310}, {-100, 0, -16, 346, -310}, {-100, 0, -18, 349, -311}, {-100, 0, -19, 350, -311}, {-100, 0, -22, 355, -313}, {-100, 0, -24, 358, -314}, {-100, 0, -25, 359, -314}, {-100, 0, -25, 358, -313}, {-100, 0, -25, 357, -312}, {-100, 0, -25, 356, -311}, {-100, 0, -26, 357, -311}, {-100, 0, -26, 356, -310}, {-100, 0, -27, 357, -310}, {-100, 0, -27, 356, -309}, {-100, 0, -29, 359, -310}, {-100, 0, -30, 360, -310}, {-100, 0, -30, 359, -309}, {-100, 0, -29, 356, -307}, {-100, 0, -28, 353, -305}, {-100, 0, -27, 350, -303}, {-100, 0, -27, 349, -302}, {-100, 0, -26, 346, -300}, {-100, 0, -26, 345, -299}, {-100, 0, -25, 342, -297}, {-100, 0, -26, 343, -297}, {-100, 0, -26, 342, -296}, {-100, 0, -25, 339, -294}, {-100, 0, -23, 334, -291}, {-100, 0, -21, 329, -288}, {-100, 0, -19, 324, -285}, {-100, 0, -18, 321, -283}, {-100, 0, -16, 316, -280}, {-100, 0, -15, 313, -278}, {-100, 0, -13, 308, -275}, {-100, 0, -13, 307, -274}, {-100, 0, -12, 304, -272}, {-100, 0, -11, 301, -270}, {-100, 0, -9, 296, -267}, {-100, 0, -7, 291, -264}, {-100, 0, -5, 286, -261}, {-100, 0, -4, 283, -259}, {-100, 0, -2, 278, -256}, {-100, 0, -1, 275, -254}, {-100, 0, 1, 270, -251}, {-100, 0, 1, 269, -250}, {-100, 0, 2, 266, -248}, {-100, 0, 3, 263, -246}, {-100, 0, 5, 258, -243}, {-100, 0, 7, 253, -240}, {-100, 0, 9, 248, -237}, {-100, 0, 10, 245, -235}, {-100, 0, 12, 240, -232}, {-100, 0, 13, 237, -230}, {-100, 0, 15, 232, -227}, {-100, 0, 15, 231, -226}, {-100, 0, 16, 228, -224}, {-100, 0, 16, 227, -223}, {-100, 0, 17, 224, -221}, {-100, 0, 18, 221, -219}, {-100, 0, 19, 218, -217}, {-100, 0, 19, 217, -216}, {-100, 0, 20, 214, -214}, {-100, 0, 20, 213, -213}, {-100, 0, 21, 210, -211}, {-100, 0, 20, 211, -211}, {-100, 0, 20, 210, -210}, {-100, 0, 21, 207, -208}, {-100, 0, 23, 202, -205}, {-100, 0, 25, 197, -202}, {-100, 0, 27, 192, -199}, {-100, 0, 28, 189, -197}, {-100, 0, 30, 184, -194}, {-100, 0, 31, 181, -192}, {-100, 0, 33, 176, -189}, {-100, 0, 33, 175, -188}, {-100, 0, 34, 172, -186}, {-100, 0, 34, 171, -185}, {-100, 0, 35, 168, -183}, {-100, 0, 36, 165, -181}, {-100, 0, 37, 162, -179}, {-100, 0, 37, 161, -178}, {-100, 0, 38, 158, -176}, {-100, 0, 38, 157, -175}, {-100, 0, 39, 154, -173}, {-100, 0, 38, 155, -173}, {-100, 0, 38, 154, -172}, {-100, 0, 39, 151, -170}, {-100, 0, 41, 146, -167}, {-100, 0, 43, 141, -164}, {-100, 0, 45, 136, -161}, {-100, 0, 46, 133, -159}, {-100, 0, 48, 128, -156}, {-100, 0, 49, 125, -154}, {-100, 0, 51, 120, -151}, {-100, 0, 51, 119, -150}, {-100, 0, 52, 116, -148}, {-100, 0, 51, 117, -148}, {-100, 0, 51, 116, -147}, {-100, 0, 51, 115, -146}, {-100, 0, 51, 114, -145}, {-100, 0, 50, 115, -145}, {-100, 0, 50, 114, -144}, {-100, 0, 49, 115, -144}, {-100, 0, 49, 114, -143}, {-100, 0, 47, 117, -144}, {-100, 0, 46, 118, -144}, {-100, 0, 46, 117, -143}, {-100, 0, 47, 114, -141}, {-100, 0, 48, 111, -139}, {-100, 0, 49, 108, -137}, {-100, 0, 49, 107, -136}, {-100, 0, 50, 104, -134}, {-100, 0, 50, 103, -133}, {-100, 0, 51, 100, -131}, {-100, 0, 50, 101, -131}, {-100, 0, 50, 100, -130}, {-100, 0, 48, 103, -131}, {-100, 0, 47, 104, -131}, {-100, 0, 46, 105, -131}, {-100, 0, 45, 106, -131}, {-100, 0, 43, 109, -132}, {-100, 0, 42, 110, -132}, {-100, 0, 40, 113, -133}, {-100, 0, 39, 114, -133}, {-100, 0, 36, 119, -135}, {-100, 0, 34, 122, -136}, {-100, 0, 33, 123, -136}, {-100, 0, 33, 122, -135}, {-100, 0, 33, 121, -134}, {-100, 0, 33, 120, -133}, {-100, 0, 32, 121, -133}, {-100, 0, 32, 120, -132}, {-100, 0, 31, 121, -132}, {-100, 0, 31, 120, -131}, {-100, 0, 29, 123, -132}, {-100, 0, 28, 124, -132}, {-100, 0, 27, 125, -132}, {-100, 0, 27, 124, -131}, {-100, 0, 27, 123, -130}, {-100, 0, 27, 122, -129}, {-100, 0, 26, 123, -129}, {-100, 0, 26, 122, -128}, {-100, 0, 25, 123, -128}, {-100, 0, 25, 122, -127}, {-100, 0, 23, 125, -128}, {-100, 0, 22, 126, -128}, {-100, 0, 21, 127, -128}, {-100, 0, 21, 126, -127}, {-100, 0, 21, 125, -126}, {-100, 0, 21, 124, -125}, {-100, 0, 20, 125, -125}, {-100, 0, 20, 124, -124}, {-100, 0, 19, 125, -124}, {-100, 0, 19, 124, -123}, {-100, 0, 17, 127, -124}, {-100, 0, 16, 128, -124}, {-100, 0, 14, 131, -125}, {-100, 0, 13, 132, -125}, {-100, 0, 12, 133, -125}, {-100, 0, 11, 134, -125}, {-100, 0, 9, 137, -126}, {-100, 0, 8, 138, -126}, {-100, 0, 6, 141, -127}, {-100, 0, 5, 142, -127}, {-100, 0, 2, 147, -129}, {-100, 0, 0, 150, -130}, {-100, 0, -1, 151, -130}, {-100, 0, -1, 150, -129}, {-100, 0, -1, 149, -128}, {-100, 0, -1, 148, -127}, {-100, 0, -2, 149, -127}, {-100, 0, -2, 148, -126}, {-100, 0, -3, 149, -126}, {-100, 0, -3, 148, -125}, {-100, 0, -5, 151, -126}, {-100, 0, -6, 152, -126}, {-100, 0, -8, 155, -127}, {-100, 0, -9, 156, -127}, {-100, 0, -10, 157, -127}, {-100, 0, -11, 158, -127}, {-100, 0, -13, 161, -128}, {-100, 0, -14, 162, -128}, {-100, 0, -16, 165, -129}, {-100, 0, -17, 166, -129}, {-100, 0, -20, 171, -131}, {-100, 0, -22, 174, -132}, {-100, 0, -23, 175, -132}, {-100, 0, -23, 174, -131}, {-100, 0, -23, 173, -130}, {-100, 0, -23, 172, -129}, {-100, 0, -24, 173, -129}, {-100, 0, -24, 172, -128}, {-100, 0, -25, 173, -128}, {-100, 0, -25, 172, -127}, {-100, 0, -27, 175, -128}, {-100, 0, -28, 176, -128}, {-100, 0, -31, 181, -130}, {-100, 0, -33, 184, -131}, {-100, 0, -35, 187, -132}, {-100, 0, -37, 190, -133}, {-100, 0, -40, 195, -135}, {-100, 0, -42, 198, -136}, {-100, 0, -45, 203, -138}, {-100, 0, -47, 206, -139}, {-100, 0, -51, 213, -142}, {-100, 0, -54, 218, -144}, {-100, 0, -56, 221, -145}, {-100, 0, -57, 222, -145}, {-100, 0, -58, 223, -145}, {-100, 0, -59, 224, -145}, {-100, 0, -61, 227, -146}, {-100, 0, -62, 228, -146}, {-100, 0, -64, 231, -147}, {-100, 0, -65, 232, -147}, {-100, 0, -68, 237, -149}, {-100, 0, -70, 240, -150}, {-100, 0, -71, 241, -150}, {-100, 0, -71, 240, -149}, {-100, 0, -71, 239, -148}, {-100, 0, -71, 238, -147}, {-100, 0, -72, 239, -147}, {-100, 0, -72, 238, -146}, {-100, 0, -73, 239, -146}, {-100, 0, -73, 238, -145}, {-100, 0, -75, 241, -146}, {-100, 0, -76, 242, -146}, {-100, 0, -76, 241, -145}, {-100, 0, -75, 238, -143}, {-100, 0, -74, 235, -141}, {-100, 0, -73, 232, -139}, {-100, 0, -73, 231, -138}, {-100, 0, -72, 228, -136}, {-100, 0, -72, 227, -135}, {-100, 0, -71, 224, -133}, {-100, 0, -72, 225, -133}, {-100, 0, -72, 224, -132}, {-100, 0, -72, 223, -131}, {-100, 0, -71, 220, -129}, {-100, 0, -70, 217, -127}, {-100, 0, -69, 214, -125}, {-100, 0, -69, 213, -124}, {-100, 0, -68, 210, -122}, {-100, 0, -68, 209, -121}, {-100, 0, -67, 206, -119}, {-100, 0, -68, 207, -119}, {-100, 0, -68, 206, -118}, {-100, 0, -68, 205, -117}, {-100, 0, -67, 202, -115}, {-100, 0, -66, 199, -113}, {-100, 0, -65, 196, -111}, {-100, 0, -65, 195, -110}, {-100, 0, -64, 192, -108}, {-100, 0, -64, 191, -107}, {-100, 0, -63, 188, -105}, {-100, 0, -64, 189, -105}, {-100, 0, -64, 188, -104}, {-100, 0, -65, 189, -104}, {-100, 0, -65, 188, -103}, {-100, 0, -65, 187, -102}, {-100, 0, -65, 186, -101}, {-100, 0, -66, 187, -101}, {-100, 0, -66, 186, -100}, {-100, 0, -67, 187, -100}, {-100, 0, -67, 186, -99}, {-100, 0, -69, 189, -100}, {-100, 0, -70, 190, -100}, {-100, 0, -70, 189, -99}, {-100, 0, -69, 186, -97}, {-100, 0, -68, 183, -95}, {-100, 0, -67, 180, -93}, {-100, 0, -67, 179, -92}, {-100, 0, -66, 176, -90}, {-100, 0, -66, 175, -89}, {-100, 0, -65, 172, -87}, {-100, 0, -66, 173, -87}, {-100, 0, -66, 172, -86}, {-100, 0, -67, 173, -86}, {-100, 0, -67, 172, -85}, {-100, 0, -67, 171, -84}, {-100, 0, -67, 170, -83}, {-100, 0, -68, 171, -83}, {-100, 0, -68, 170, -82}, {-100, 0, -69, 171, -82}, {-100, 0, -69, 170, -81}, {-100, 0, -71, 173, -82}, {-100, 0, -72, 174, -82}, {-100, 0, -72, 173, -81}, {-100, 0, -71, 170, -79}, {-100, 0, -70, 167, -77}, {-100, 0, -69, 164, -75}, {-100, 0, -69, 163, -74}, {-100, 0, -68, 160, -72}, {-100, 0, -68, 159, -71}, {-100, 0, -67, 156, -69}, {-100, 0, -68, 157, -69}, {-100, 0, -68, 156, -68}, {-100, 0, -70, 159, -69}, {-100, 0, -71, 160, -69}, {-100, 0, -72, 161, -69}, {-100, 0, -73, 162, -69}, {-100, 0, -75, 165, -70}, {-100, 0, -76, 166, -70}, {-100, 0, -78, 169, -71}, {-100, 0, -79, 170, -71}, {-100, 0, -82, 175, -73}, {-100, 0, -84, 178, -74}, {-100, 0, -85, 179, -74}, {-100, 0, -85, 178, -73}, {-100, 0, -85, 177, -72}, {-100, 0, -85, 176, -71}, {-100, 0, -86, 177, -71}, {-100, 0, -86, 176, -70}, {-100, 0, -87, 177, -70}, {-100, 0, -87, 176, -69}, {-100, 0, -89, 179, -70}, {-100, 0, -90, 180, -70} };
vi idx{ 11, 20, 109, 110, 111 };
vvull coef(1000, vull(111));
rep(i, 1000) rep(j, 5) coef[i][idx[j] - 1] = (ull)coef_cp[i][j];
vull dp = { 1, 1, 1, 1, 1, 2, 2, 3, 3, 5, 6, 1, 1, 1, 1, 2, 2, 3, 3, 5, 6, 7, 7, 7, 7, 8, 8, 9, 9, 11, 12, 13, 13, 13, 13, 14, 14, 15, 15, 17, 18, 19, 19, 19, 19, 20, 20, 21, 21, 23, 24, 26, 27, 28, 29, 31, 32, 34, 35, 38, 40, 41, 41, 41, 41, 42, 42, 43, 43, 45, 46, 48, 49, 50, 51, 53, 54, 56, 57, 60, 62, 63, 63, 63, 63, 64, 64, 65, 65, 67, 68, 71, 73, 75, 77, 80, 82, 85, 87, 91, 94, 96, 97, 98, 99, 101, 102, 104, 105, 108, 110 };
int B = 2;
int kind = 10;
// --------------------------------------------------------------
// ここ以降は書き換えなくて良い．
repe(d, ds) {
vull ndp;
ndp.reserve(sz(dp));
int offset = 1; int w = 1;
rep(b, B) {
ndp.insert(ndp.end(), dp.begin() + (offset + d * w), dp.begin() + (offset + (d + 1) * w));
w *= kind;
offset += w;
}
int k0 = d * w;
int k1 = (d + 1) * w - 1;
repi(k, k0, k1) {
ull tmp = 0;
rep(t, sz(dp)) tmp += dp[t] * coef[k][t];
ndp.push_back(tmp);
}
dp = move(ndp);
//dump(dp);
}
return dp[0];
}
//【めぐる式二分探索】O(log|ok - ng|)
/*
* 条件 okQ() を満たす要素 ok と満たさない要素 ng との境界を二分探索する．
* 境界に隣り合うような条件を満たす要素（ok 側）の位置を返す．
* debug_mode = true にして実行すると手元では単調かどうかチェックしながら全探索する．
*/
template <class T, class FUNC>
T meguru_search(T ok, T ng, const FUNC& okQ, bool debug_mode = false) {
// 参考 : https://twitter.com/meguru_comp/status/697008509376835584
// verify : https://atcoder.jp/contests/typical90/tasks/typical90_a
Assert(ok != ng);
#ifdef _MSC_VER
// 単調かどうか自信がないとき用
if (debug_mode) {
T step = ok < ng ? 1 : -1; T res = ok; bool is_ok = true;
for (T i = ok; i != ng + step; i += step) {
auto b = (i == ok ? true : i == ng ? false : okQ(i));
if (b) {
if (!is_ok) {
cout << "not monotony!" << endl;
for (T i = ok; i != ng + step; i += step) {
auto b = (i == ok ? true : i == ng ? false : okQ(i));
cout << i << " : " << b << endl;
}
exit(1);
}
}
else {
if (is_ok) res = i - step;
is_ok = false;
}
}
return res;
}
#endif
// 境界が決定するまで
while (abs(ok - ng) > 1) {
// 区間の中間
T mid = (ok + ng) / 2;
// 中間が OK かどうかに応じて区間を縮小する．
if (okQ(mid)) ok = mid;
else ng = mid;
}
return ok;
/* okQ の定義の雛形
auto okQ = [&](ll x) {
return true || false;
};
*/
}
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
// zikken();
//【方法】
// 愚直を書いて集めた学習データをもとにスライド bitDP のコードを自動生成する．
ll K;
cin >> K;
auto okQ = [&](ll n) {
vi ds;
while (n > 0) {
ds.push_back(n % 10);
n /= 10;
}
reverse(all(ds));
return solve(ds) - 1 <= K;
};
ll n = meguru_search(0LL, INFL, okQ);
dump("n:", n);
ll n0 = n;
vi ds;
while (n > 0) {
ds.push_back(n % 10);
n /= 10;
}
reverse(all(ds));
if (solve(ds) - 1 != K) EXIT(-1);
EXIT(n0);
}