結果

問題 No.3067 ドーパミン
ユーザー ecotteaecottea
提出日時 2022-09-22 23:33:46
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 24 ms / 2,000 ms
コード長 36,909 bytes
コンパイル時間 4,888 ms
コンパイル使用メモリ 258,064 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-23 20:40:50
合計ジャッジ時間 6,981 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 20 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 24 ms
4,376 KB
testcase_05 AC 24 ms
4,376 KB
testcase_06 AC 24 ms
4,376 KB
testcase_07 AC 19 ms
4,376 KB
testcase_08 AC 19 ms
4,376 KB
testcase_09 AC 5 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 2 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 vl = vector<ll>;		using vvl = vector<vl>;		using vvvl = vector<vvl>;
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 = 4004004004004004004LL;
double EPS = 1e-12;

// 入出力高速化
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);} // 強制終了

// 汎用関数の定義
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, 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; }

// 手元環境（Visual Studio）
#ifdef _MSC_VER
#include "local.hpp"
// 提出用（gcc）
#else
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 input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) while (1) cout << "OLE"; }
#endif

#endif // 折りたたみ用


//--------------AtCoder 専用--------------
#include <atcoder/all>
using namespace atcoder;

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

istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>;
//----------------------------------------


uint64_t a[29][29] = {
	{26426630, 14176228, 70225397, 44568705, 999301162, 613823, 57558942, 6718464, 959574529, 8573184, 134689, 2216425, 4200522, 7203856, 69022813, 7581311, 15539364, 210227181, 2244004, 16, 2206093, 5044516, 13189336, 42558358, 8695519, 31703281, 26789, 15546355, 55241078},
	{1624593, 4096, 77369616, 15054400, 66564, 528529, 496474, 5803281, 1020100, 25083945, 365267, 147456, 46444225, 31124641, 49266361, 30976, 94249, 149504965, 126493740, 268324, 17172736, 4656964, 27242468, 14175225, 34969, 1, 335241, 297493504, 22},
	{163489349, 134689, 8499552, 1686714, 3910187, 1359556, 4673318, 4804864, 4243600, 20684304, 14984641, 1700416, 549799368, 10150596, 174292804, 59979027, 6682225, 701932036, 8185286, 33373729, 1089, 2310400, 746011, 2656900, 8262810, 7776048, 2665831, 228251664, 52228131},
	{8847786, 1387684, 12086765, 35809765, 1372589, 15034928689, 13542866, 1079521, 7371068, 18757561, 78747876, 674041, 14055201, 30177375, 1774670, 1156, 22393459, 96179780, 22945292, 3663396, 69569752, 4835601, 3622220, 14025025, 1796519, 20116222, 270281, 25921, 4641882},
	{23132378, 537822481, 16935461, 2682934, 26829, 1985682721, 31888057, 9205156, 29537021, 24453909, 2085136, 34128964, 36864, 1590121, 5825787, 9388096, 3721, 2160900, 27393512, 177936989, 24324624, 26718561, 632510440, 484416, 46494896, 1602807, 20710695, 6765201, 240912624},
	{6458152, 544644, 29584, 267289, 16597476, 4225, 16702741, 14010049, 290463849, 391876, 10824100, 2815002, 75583386, 24007569, 11934592, 5564881, 37356544, 27878400, 62884230, 9891025, 10751841, 70756, 21822368, 5340721, 3385600, 15069924, 755161, 66049, 34263464},
	{5289938, 59431026, 4436148, 2459909, 82318684, 135443615, 11567240, 1909924, 23438537, 6874884, 10309523, 6012304, 17306338, 16703569, 12550896, 1, 196764677, 19847025, 13270937, 912402436, 227933151, 83759104, 2127319, 109175272, 13312734, 150289362, 341673, 20861726, 16442173},
	{105625, 49284, 355511025, 5329, 2832489, 135424, 266505625, 2989441, 9320809, 9991921, 147158694, 762068, 90383049, 18809569, 35074930, 28558814, 23833924, 11971600, 3013468, 91795079, 58430736, 4928400, 4, 3829849, 24542116, 62001, 9205156, 486334809, 13623481},
	{189127223, 14231187, 810000, 19321, 2, 135982167, 2582788, 7119501, 17847173828676242, 320510680554088, 24500379597492841, 334679191532383085, 6735482919480050, 25933343445080586, 21581617288276224, 41614577724152196, 3597896227441156, 237585195915605692, 819992478029118938, 5757151873740873, 34435069922004544, 2639126666849761, 20697314316134544, 81401057719394436, 455170744392893683, 96265958776, 20235491812777081, 7849195739570642, 17840524156980625},
	{13446889, 1476403776, 3341584, 31526786, 25172287, 1158046189, 4579600, 25614112, 18858594792906801, 97157512044087075, 8583768499201352, 51493082149240384, 438751524920563634, 58952187204511225, 980182635911571118, 10075279945981636, 242043483614867200, 1619512685727048, 987654321, 3013484410315369, 996411698904838542, 75727024186510096, 301910512736450, 15674484116928400, 768397452398157811, 19963682742652609, 83431307510937961, 723951695885999821, 1863130896000000},
	{24751326, 126736, 2603, 128444901, 216225, 2563131, 6058408, 14400, 14514459050969667, 65452835104725289, 4705736451472063, 81838777463450176, 10215129739505625, 24164303213566562, 60818182376684329, 166164519662083547, 54121438461461904, 10960800704100, 197320728219753648, 53490783932878009, 13052192158008481, 3514063554328, 6586200247646464, 14357311204712004, 22392822139274596, 273691129333161620, 51318159687273924, 4294967295, 66239079090333444},
	{289444, 18032320, 1375929, 9541921, 29944006, 11818835, 24285184, 1267876, 1680616261902400, 682098571722780488, 42525278968633472, 1895221345539600, 18504876111496, 4971008326922884, 34238445270232225, 70336000388259904, 17753028175440100, 61355174571854289, 119486243513795735, 43017139676983692, 115787985820277906, 37923540629626276, 85227135481523161, 384899706937321, 640502598789352953, 54976877278105225, 30148468695324736, 42583120954411682, 625274180063289},
	{23256069, 166627824, 212521, 7581530, 788544, 158404, 591444, 2430481, 166489929220005075, 363678664205484500, 3893172962927616, 244292675374420285, 16516049594, 79587262356501025, 200319175346305, 5725709599469095, 909850551074439044, 29884214442716, 86106059968832281, 9052519712983, 12822709891134025, 2557629320887207, 76781391744530263, 27745041930946752, 139887330317390908, 7471053610679, 15397813751724450, 8934659158102276, 6373212089760000},
	{75076, 839056, 649636, 929296, 31856709, 152631276, 1296, 1874161, 441795208155625, 87294051753326224, 23955110561676996, 3077505470622361, 38052544446336996, 39483196955179264, 17052155233289288, 838650461448390679, 63849192232536529, 33386595476480064, 20857620209805625, 11482694980044800, 22413160832037, 904498782032672, 31600666494972169, 480585181487065767, 10711320985800000, 6853331223952801, 76952279604702121, 53499522076331769, 66902225380076025},
	{7284601, 40804, 6403088, 1908576, 8905675, 64451368, 32959066, 4594852, 700979222216448, 72391696405561, 249235754127863009, 18034898498972480, 214540232815821675, 10493327086311364, 1211948378541698, 63293971988192849, 79079938665518025, 30002580549000900, 20213036921669868, 440358011814681, 12142518898028738, 1317773832873, 145378292978492523, 268899993881842510, 8694488293177600, 9363491351568225, 3333969266605156, 3142515396608449, 6927987983135296},
	{28875783, 63313849, 98, 497959225, 99443411, 12349867, 4583881, 236185569, 4131012615886116, 88126642124697124, 46851542330613241, 389977705427968567, 5192488383919929, 9095481533214756, 44225459404448448, 8096640288456889, 863708975349920813, 8729195724488, 128278530496733952, 38980992562576, 575715187374087, 7555995436702441, 13016829527525041, 64909617320248281, 371187618412900, 458059557857457548, 151893297101051427, 8444045934420100, 2196289721455},
	{101422375, 17424, 4803047, 106777563, 66049, 1490841, 13235, 37717705, 2879563665572356, 248494562623992428, 59768428885432, 33668074851561518, 12944083456996624, 373304264186349620, 12067964591986944, 497459113230000, 51646658535216144, 385560227813799821, 56431741344023447, 14503568615186562, 20987490164877604, 44824557514641147, 21249562281111616, 22898250232735684, 687089336786186322, 93010719039717675, 37942418315930769, 9149335897857319, 6774285701990401},
	{887068, 719104, 13521433, 567009, 1740944, 111325652, 160000, 1, 618817863602500, 912376554654012642, 3485714869443249, 75202055056264761, 975883560728816, 54081332683984225, 28650939147769689, 269395903678875627, 24939760786725625, 1399263898173696, 315758749752103691, 86065914704689262, 54491145232558225, 30, 34952213805837512, 1145141919893819, 93202136725531392, 36619012555787200, 49638592773434401, 34683260682611776, 891461160011827816},
	{36258077, 7744262, 13121607, 241081, 43811161, 6561, 12463011, 146635284, 101142234966475125, 70369247778144676, 67054732739140800, 2181050394259796, 41992642470892096, 77860086961231, 4369026725729689, 442319349884812766, 85041307549191184, 572574447321821935, 15559475510834423, 621668740882338891, 61659251010780267, 244199158881186963, 38438769139320050, 402473450810500989, 11514303747481746, 86941720193486596, 494038417687500, 517578421606074367, 1981507943278125},
	{12496430, 14641, 301948074, 3374569, 1085438916, 8094025, 25431849, 28999756, 15634300383542416, 7011729609833200, 3271575591389166, 2961134977456898, 26214160354378134, 22884291725251401, 2636061467648498, 40730155979608225, 85184600333280100, 9811779310189476, 682799486007364097, 21048509037967849, 94597344048818, 7434072567060624, 28601896405386304, 1126344009980401, 1635787795694847, 14357827881815716, 5655219729428025, 43783684710633169, 117853083392256},
	{224268983, 8100, 2426935, 8221786, 39106164, 81804852, 38632446, 16085719, 289651500760801, 68976389989876356, 57509482629577104, 9569637300177529, 16241050200450248, 80629740089767696, 3247482525045858, 486027415615521983, 5305078307, 19273068647840484, 376078473239836584, 471833858297169, 759108028415330539, 168580987666223405, 11416607275983845, 1400498632087296, 818920040381264156, 47647505633683396, 67476178712103529, 885711495574548219, 7330469664258244},
	{70879561, 34562641, 13579225, 4120900, 864900, 25, 14830368400, 23804641, 60397750160226675, 22616367371786881, 262514612128063743, 27323415249565681, 71853425689600, 354953931130768257, 161506726698908748, 3141592, 15352404996642328, 437827184169977451, 95903827767595575, 6692224744628361, 458073500457423692, 34175319272131041, 65283664546649124, 56646875076481600, 325704327140256980, 85580428588003584, 1015381220312209, 15513415681496769, 27541931405317128},
	{541716, 1350101, 27687184, 34776788, 480304, 38664013, 6021357, 3693479076, 320510680554107, 7711426804972900, 63640521214732900, 243155991349334173, 7410280467, 798994276313222182, 14848812597335616, 346161961289200500, 3179437618706568, 188262607181153967, 8738053451459378, 480332570033640505, 319809179126721310, 21990540397558084, 8932091665293228, 5791746060804484, 327673847425552348, 16957305696848400, 71037, 7700298501747687, 654046406097561},
	{4585394, 4393216, 169, 912025, 23409, 2916, 107014526, 2235025, 114514889464364387, 6444427738513303, 186137373704056428, 101, 19805185135112882, 20749448323769344, 30624752200501264, 2387988575702500, 6342404796729800, 22517554322601009, 243808716399151788, 35370913185406096, 1090525197129722, 9958513517691904, 57462737073238225, 24465581212641529, 1356919184887, 199226537104, 43622417726918416, 82548526671008836, 545262598564949},
	{2514932, 2856100, 3654569, 22970664, 925190, 3949242649, 16360651, 4571044, 28445577015209778, 338531447264966017, 66104653246495504, 58335142948462864, 24853322266508450, 619367882862427888, 1635787795694847, 3838101249160582, 569777233319585974, 26281435622041800, 127080750563260160, 296370435991154627, 396399699423758925, 563098692628060687, 21845133628648445, 756929056527999348, 6939328541811, 1529582713614400, 11489535756594018, 124611992446268047, 64604841155430976},
	{23717148, 1478656, 86032008, 3659753, 901237061, 155451024, 2263363952, 492884401, 34616216652321312, 138935911001462575, 1757031777164, 56309785053455241, 80127670138522, 699361563546396371, 1329535273360849, 960024969482731314, 3153897190265761, 67197727645310025, 408881930759706320, 13763018258878088, 39276911332513156, 34350353280741289, 19393374894969604, 33777763154496, 5873125849687684, 43579670220100, 645424593523264, 23972129236613538, 583767613286288014},
	{483, 189888400, 950476, 56248, 20915772, 103684, 9934918, 1890625, 37132469487932641, 19094389629316875, 964440414643586376, 3996248116333225, 42304996680786225, 54526, 273079343794295695, 917653059853096840, 27235567625280400, 7924014716794225, 2290283839787638, 202109440910400, 33257762809752100, 13107080177189067, 3, 36603489333907456, 2686010748428772, 878515888582, 291263422844662922, 334188698502708405, 7992151162964224},
	{17123620, 2414916, 236196, 207849889, 60516, 2637376, 48782711, 87025, 893, 204492526206016647, 542205425934485500, 474927570439200, 757359645583469827, 2181050394259444, 3074805610037, 11608214876513476, 3614048134225, 80263898822145600, 13878657083622, 39002661112555396, 28983092315164488, 19434932572737529, 854151322844516288, 85368513111356836, 29884214442763, 38134795503192976, 92462224886672368, 49412142999826929, 127697463132569643},
	{235492693, 28956667, 55209494, 21233244, 27346710, 38716356, 13941653, 47524, 464643937840190647, 72335929757839609, 75449813273514436, 17540331879846724, 33110907312216845, 69339424173087601, 839245612879765668, 13789290677797452, 45243154122001924, 44734576953261001, 1019002827782088, 31691722466499481, 45050869053610000, 218571815228469132, 12303992406108488, 3491729380994449, 392367542219582771, 59975021587672324, 551, 26332309569251912, 21039442803488}
};

// x の約数全ての XOR を返す
uint64_t f(uint64_t x) {
	uint64_t s = 0;
	for (uint64_t i = 1; i <= x; i++) {
		if (x % i) continue;
		s ^= i;
	}
	return s;
}

// (x + 1) % 2 を返す
uint64_t g(uint64_t x) {
	if (x == 0) return 1;
	if (x == 1) return 0;
	
	// 山 x を山 i と山 x-i に分割した場合の nimber を計算している．
	vb t(x << 1); // bool[] から vb に変更した
	for (uint64_t i = 1; i < x; i++) {
		t[g(i) ^ g(x - i)] = 1;
	}
	for (uint64_t i = 0; ; i++) {
		if (!t[i]) return i;
	}
}

int main_c(void) {
	for (int i = 0; i < 29; i++) {
		for (int j = 0; j < 29; j++) {
			putchar(g(f(a[i][j])) ? '#' : ' ');
		}
		putchar('\n');
	}
	return 0;
}


void zikken() {
	int n = 20;
	
	vi dp(n);
	dp[0] = 1;
	dp[1] = 0;

	repi(x, 2, n - 1) {
		vb t(x * 2LL);
		for (int i = 1; i < x; i++) {
			t[dp[i] ^ dp[x - i]] = 1;
		}
		for (int i = 0; ; i++) {
			if (!t[i]) {
				dp[x] = i;
				break;
			}
		}
	}

	dump_list(dp);

	exit(0);
}
/*
{1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0}
1×n の板チョコゲームだと思えば，折れる箇所が 1 つずつ減っていくのでそれはそう．
*/


//【有限体 F_p 上の計算（64 bit）】
/*
* 有限体 F_p 上ので様々な計算を行う．
*
* 制約 : p は素数，コンパイラは gcc
*/
#ifdef _MSC_VER
#define __int128 ll // デバッグ用
#endif
struct mll {
	__int128 v;
	static __int128 MOD;

	// コンストラクタ
	mll() : v(0) {};
	mll(const mll& a) = default;
	mll(const int& a) : v(safe_mod(a)) {};
	mll(const ll& a) : v(safe_mod(a)) {};

	// 代入
	mll& operator=(const mll& a) { v = a.v; return *this; }
	mll& operator=(const int& a) { v = safe_mod(a); return *this; }
	mll& operator=(const ll& a) { v = safe_mod(a); return *this; }

	// 入出力
	friend istream& operator>> (istream& is, mll& x) { ll tmp; is >> tmp; x.v = safe_mod(tmp); return is; }
	friend ostream& operator<< (ostream& os, const mll& x) { os << (ll)x.v; return os; }

	// 非負 mod
	template <class T> static __int128 safe_mod(T a) { return ((a % MOD) + MOD) % MOD; }

	// 比較
	bool operator==(const mll& b) const { return v == b.v; }
	bool operator==(const int& b) const { return v == safe_mod(b); }
	bool operator==(const ll& b) const { return v == safe_mod(b); }
	friend bool operator==(const int& a, const mll& b) { return b == a; }
	friend bool operator==(const ll& a, const mll& b) { return b == a; }

	// 演算
	mll& operator+=(const mll& b) { v = safe_mod(v + b.v); return *this; }
	mll& operator-=(const mll& b) { v = safe_mod(v - b.v); return *this; }
	mll& operator*=(const mll& b) { v = safe_mod(v * b.v); return *this; }
	mll& operator/=(const mll& b) { *this *= b.inv(); return *this; }
	mll operator+(const mll& b) const { mll a = *this; return a += b; }
	mll operator-(const mll& b) const { mll a = *this; return a -= b; }
	mll operator*(const mll& b) const { mll a = *this; return a *= b; }
	mll operator/(const mll& b) const { mll a = *this; return a /= b; }
	mll operator-() const { mll a = *this; return a *= -1; }

	// int との演算
	mll& operator+=(const int& b) { v = safe_mod(v + b); return *this; }
	mll& operator-=(const int& b) { v = safe_mod(v - b); return *this; }
	mll& operator*=(const int& b) { v = safe_mod(v * b); return *this; }
	mll& operator/=(const int& b) { *this *= mll(b).inv(); return *this; }
	mll operator+(const int& b) const { mll a = *this; return a += b; }
	mll operator-(const int& b) const { mll a = *this; return a -= b; }
	mll operator*(const int& b) const { mll a = *this; return a *= b; }
	mll operator/(const int& b) const { mll a = *this; return a /= b; }
	friend mll operator+(const int& a, const mll& b) { return b + a; }
	friend mll operator-(const int& a, const mll& b) { return -(b - a); }
	friend mll operator*(const int& a, const mll& b) { return b * a; }
	friend mll operator/(const int& a, const mll& b) { return mll(a) * b.inv(); }

	// ll との演算
	mll& operator+=(const ll& b) { v = safe_mod(v + b); return *this; }
	mll& operator-=(const ll& b) { v = safe_mod(v - b); return *this; }
	mll& operator*=(const ll& b) { v = safe_mod(v * b); return *this; }
	mll& operator/=(const ll& b) { *this *= mll(b).inv(); return *this; }
	mll operator+(const ll& b) const { mll a = *this; return a += b; }
	mll operator-(const ll& b) const { mll a = *this; return a -= b; }
	mll operator*(const ll& b) const { mll a = *this; return a *= b; }
	mll operator/(const ll& b) const { mll a = *this; return a /= b; }
	friend mll operator+(const ll& a, const mll& b) { return b + a; }
	friend mll operator-(const ll& a, const mll& b) { return -(b - a); }
	friend mll operator*(const ll& a, const mll& b) { return b * a; }
	friend mll operator/(const ll& a, const mll& b) { return mll(a) * b.inv(); }

	// 累乗
	mll pow(ll d) const {
		mll res(1), pow2 = *this;
		while (d > 0) {
			if (d & 1) res *= pow2;
			pow2 *= pow2;
			d /= 2;
		}
		return res;
	}

	// 逆元
	mll inv() const { return pow(MOD - 2); }

	// 法の設定，確認
	static void set_mod(ll MOD_) { Assert(MOD_ > 0); MOD = MOD_; }
	static ll mod() { return (ll)MOD; }

	// 値の確認
	ll val() const { return (ll)safe_mod(v); }
};
__int128 mll::MOD;


//【素数判定】O((log n)^3)
/*
* n が素数かを返す．
*
* 利用：【有限体 F_p 上の計算（64 bit）】
*/
bool miller_rabin(ll n) {
	// 参考 : https://nyaannyaan.github.io/library/prime/fast-factorize.hpp.html
	// verify : https://algo-method.com/tasks/513

	//【方法】
	// p を奇素数とすると，任意の a=[1..p) についてフェルマーの小定理より
	//		a^(p-1) = 1 (mod p)
	// となる．これの平方根を考えていくと，
	//		p - 1 = 2^s d　（d : 奇数）
	// と表せば，
	//		a^d = 1 (mod p) or ∃r=[0..s), a^(2^r d) = -1 (mod p)
	// と書き直せる．
	// 
	// この対偶を用いて判定することをランダムに選んだ a で繰り返す．
	// n の範囲を限定するなら擬素数を生じない a を固定的に選べる．

	const vl as = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };

	if (n == 2 || n == 3 || n == 5 || n == 13 || n == 19 || n == 73 || n == 193
		|| n == 407521 || n == 299210837) return true;
	if (n == 1 || n % 2 == 0) return false;

	mll::set_mod(n);
	int s = 0; ll d = n - 1;
	while (d % 2 == 0) {
		s++;
		d /= 2;
	}

	repe(a, as) {
		mll powa = mll(a).pow(d);
		if (powa == 1 || powa == -1) goto LOOP_END;
		rep(r, s - 1) {
			powa *= powa;
			if (powa == 1) return false;
			if (powa == -1) goto LOOP_END;
		}
		return false;

	LOOP_END:;
	}

	return true;
}


//【約数検出】O(n^(1/4))
/*
* n の真の約数を何か 1 つ返す．
*
* 制約 : n は合成数
*
* 利用：【有限体 F_p 上の計算（64 bit）】
*/
ll pollard_rho(ll n) {
	// 参考 : https://qiita.com/Kiri8128/items/eca965fe86ea5f4cbb98
	// verify : https://algo-method.com/tasks/553

	//【方法】
	// 適当な定数 c をとり関数 f : Z/nZ → Z/nZ を
	//		f(x) = x^2 + c
	// と定める．
	//
	// 適当な初期値 x[0] = y[0] (= 2) から始め，Z/nZ 上の数列を漸化式
	//		x[i + 1] = f(x[i]), y[i + 1] = f(f(y[i]))
	// で定める．フロイドの循環検出法より，もし
	//		gcd(x[i] - y[i], n) = g ∈ [2..n-1]
	// であれば，これは f が Z/gZ（g は n の真の約数）で巡回したことを意味する．
	//
	// 実際には，
	//		x は r = (2 冪) 個ずつ進める（定数 1/2 倍）
	//		gcd の計算を m = n^(1/8) 程度個まとめて行う（gcd の log を落とす）
	// ことにより高速化を図る．

	if (!(n & 1)) return 2;

	int m = 1 << (msb(n) / 8);
	mll::set_mod(n); // n は合成数だが割り算は使わないので問題ない

	const int c_max = 99; // c を最大どこまで試すか
	repi(c, 1, c_max) {
		auto f = [&](mll x) { return x * x + c; };

		mll x, y = 2, y_bak;
		ll g = 1;
		int r = 1;

		// g = 1 である間は巡回未検出
		while (g == 1) {
			// x, y を r = 2^i だけ一気に進める．
			x = y;
			rep(hoge, r) y = f(y);

			// 次の r = 2^i 個をまとめて見る．
			for (int k = 0; k < r; k += m) {
				// 一気に掛けすぎて g = n となってしまった場合の復元用
				y_bak = y;

				// m 個ごとにまとめて見る．
				mll mul = 1;
				rep(i, min(m, r - k)) {
					y = f(y);

					// 複数個掛けておき，後でまとめて gcd を計算する．
					//（フロイドの循環検出法とは違い x を固定しているが，
					// 巡回は検出できるので問題ない．）
					mul *= x - y;
				}
				g = gcd(mul.val(), n);

				// g != 1 なら巡回を検出できたので次の処理へ
				if (g != 1) goto LOOP_END;
			}

			r *= 2;
		}

	LOOP_END:;
		// 一気に掛けすぎて g = n となってしまった（であろう）場合
		if (g == n) {
			// 復元用に残しておいた x, y_bak から再スタート
			g = 1;
			while (g == 1) {
				y_bak = f(y_bak);
				g = gcd((x - y_bak).val(), n);
			}
		}

		// g < n なら g が n の真の約数なのでそれを返す．
		if (g < n) return g;

		// g = n ならたまたま真の約数が全て同時検出されてしまったので，
		// 関数 f における定数項 c の値を別のものに取り替えて再挑戦．
	}

	// 複数個の c を試してなお失敗したなら諦める．
	return n;
}


//【素因数分解】O(n^(1/4))
/*
* n を素因数分解した結果を pps に格納する．
* pps[p] = d : n に素因数 p が d 個含まれていることを表す．
*
* 利用：【素数判定】,【約数検出】
*/
void factor_integer(ll n, map<ll, int>& pps) {
	// verify : https://algo-method.com/tasks/553

	pps.clear();
	if (n == 1) return;

	// 検出した約数を記録しておくキュー
	queue<ll> divs;
	divs.push(n);

	while (!divs.empty()) {
		ll d = divs.front();
		divs.pop();

		// 約数が素数なら素因数発見
		if (miller_rabin(d)) {
			pps[d]++;
		}
		// 約数が合成数なら新たな約数を 2 つ発見する
		else {
			ll d1 = pollard_rho(d);
			ll d2 = d / d1;
			divs.push(d1);
			divs.push(d2);
		}
	}
}


//【約数列挙】O(n^(1/4))
/*
* n の約数全てをリスト divs に昇順に格納する．
*
* 利用：【素因数分解】
*/
void divisors(ll n, vl& divs) {
	// verify : https://atcoder.jp/contests/chokudai_S002/tasks/chokudai_S002_j

	Assert(n > 0);

	map<ll, int> pps;
	factor_integer(n, pps);

	divs = vl({ 1 });
	repe(pp, pps) {
		ll p; int d;
		tie(p, d) = pp;

		vl powp(d);
		powp[0] = p;
		rep(i, d - 1) powp[i + 1] = powp[i] * p;

		int m = sz(divs);
		repir(j, m - 1, 0) {
			rep(i, d) {
				divs.push_back(divs[j] * powp[i]);
			}
		}
	}

	sort(all(divs));
}


// main_c() を高速化して 29×29 の QR コードを吐かせる．
void zikken2() {
	cout << "{\n";
	for (int i = 0; i < 29; i++) {
		cout << "{";
		for (int j = 0; j < 29; j++) {
			vl divs;
			divisors(a[i][j], divs);

			ll v = 0;
			repe(d, divs) v ^= d;

			cout << (!(v&1) ? '1' : '0');
			cout << (j < 28 ? "," : "}");
		}
		if (i < 28) cout << ",";
		cout << '\n';
	}
	cout << "}\n";

	exit(0);
}
/*
{
{1,1,1,1,1,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1},
{1,0,0,0,0,0,1,0,0,1,1,0,0,1,0,0,0,1,1,0,0,0,1,0,0,0,0,0,1},
{1,0,1,1,1,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,1,1,1,0,1},
{1,0,1,1,1,0,1,0,1,0,0,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1},
{1,0,1,1,1,0,1,0,1,1,0,0,0,0,1,0,0,0,1,1,0,0,1,0,1,1,1,0,1},
{1,0,0,0,0,0,1,0,0,0,0,1,1,1,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1},
{1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0,0,0,0,0,0,0,0},
{1,1,0,0,0,1,1,1,0,1,0,1,0,1,0,0,0,1,1,1,0,0,0,0,1,1,0,0,0},
{0,0,0,1,1,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,1,0},
{1,0,1,1,0,1,1,0,1,0,1,0,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0},
{0,1,0,0,1,1,0,0,0,1,0,0,1,0,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0},
{1,1,0,1,0,0,1,0,1,1,0,1,1,0,1,1,1,1,0,1,0,1,1,1,1,1,0,0,0},
{0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,1,1,0,0,0,0},
{0,0,1,1,1,1,1,1,1,0,1,1,1,0,0,1,0,0,1,0,0,1,1,1,0,0,0,0,0},
{1,0,0,0,1,1,0,1,0,0,0,1,0,0,1,0,1,0,1,0,1,0,0,0,0,1,1,0,1},
{1,0,1,1,0,0,1,1,0,1,1,1,0,1,0,1,0,1,1,0,0,1,0,0,1,1,0,1,0},
{1,0,1,0,1,1,0,0,0,1,0,0,1,0,0,1,0,0,1,1,0,1,1,1,1,1,0,0,1},
{1,1,1,0,0,0,1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,1,0,1,1,0,1,1,1},
{1,0,1,0,0,0,0,1,0,1,1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0},
{1,0,1,1,1,1,1,1,0,0,0,0,1,0,0,1,1,0,1,0,1,1,1,1,1,0,0,1,0},
{0,0,0,0,0,0,0,0,1,0,1,0,0,1,1,1,1,1,1,0,1,0,0,0,1,0,0,0,0},
{1,1,1,1,1,1,1,0,1,0,0,1,1,1,0,1,0,1,1,1,1,0,1,0,1,0,1,1,0},
{1,0,0,0,0,0,1,0,1,1,1,1,0,0,0,0,0,0,1,0,1,0,0,0,1,0,0,0,1},
{1,0,1,1,1,0,1,0,0,1,0,0,0,1,1,1,1,0,1,1,1,1,1,1,1,0,0,1,0},
{1,0,1,1,1,0,1,0,0,1,1,0,1,1,0,1,0,0,1,0,0,0,0,0,0,0,0,0,1},
{1,0,1,1,1,0,1,0,0,1,1,0,0,1,1,1,0,0,1,0,0,1,1,0,1,1,1,1,0},
{1,0,0,0,0,0,1,0,1,1,1,0,1,1,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1},
{1,1,1,1,1,1,1,0,1,0,0,0,1,0,1,1,0,0,0,0,0,1,0,0,1,0,1,0,0}
}

__L9_U
3__KB_
8____V
_2__P_
_D_1__
_J7___

6×6 で，文字に重複がないので，ADFGVX 暗号の換字表っぽい．
でもところどころ空白（'_' で表した）があり，まだ情報が足りていない感じがする．

また，そうだとしたら鍵文字の方も必要になるので探さないといけない．
*/


// a[i][j] が完全平方かどうかを調べて 29×29 の QR コードを吐かせる．
void zikken3() {
	cout << "{\n";
	for (int i = 0; i < 29; i++) {
		cout << "{";
		for (int j = 0; j < 29; j++) {
			map<ll, int> pps;
			factor_integer(a[i][j], pps);

			bool ok = true;
			repe(pp, pps) if (pp.second & 1) {
				ok = false;
				break;
			}

			cout << (!ok ? '1' : '0');
			cout << (j < 28 ? "," : "}");
		}
		if (i < 28) cout << ",";
		cout << '\n';
	}
	cout << "}\n";

	exit(0);
}
/*
{
{1,1,1,1,1,1,1,0,0,0,0,1,1,0,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1},
{1,0,0,0,0,0,1,0,0,1,1,0,0,1,0,0,0,1,1,0,0,0,1,0,0,0,0,0,1},
{1,0,1,1,1,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0,0,0,1,0,1,1,1,0,1},
{1,0,1,1,1,0,1,0,1,0,0,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1},
{1,0,1,1,1,0,1,0,1,1,0,0,0,0,1,0,0,0,1,1,0,0,1,0,1,1,1,0,1},
{1,0,0,0,0,0,1,0,0,0,0,1,1,1,1,0,0,0,1,0,0,0,1,0,0,0,0,0,1},
{1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0,0,0,0,0,0,0,0},
{1,1,0,0,1,1,1,1,1,1,0,1,1,1,0,0,0,1,1,1,0,0,0,0,1,1,0,1,0},
{0,0,0,1,1,1,0,1,0,1,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,0,1,0},
{1,0,1,1,0,1,1,0,1,0,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,1,0,1,0},
{0,1,0,0,1,1,0,0,0,1,1,0,1,0,0,0,0,0,1,1,1,0,0,0,1,0,0,1,0},
{1,1,0,1,0,0,1,0,1,1,0,1,1,0,1,1,1,1,0,1,0,1,1,1,1,1,1,0,0},
{0,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0,1,1,1,0,1,1,0,0,0,0},
{0,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,0,0,1,0,1,1,1,1,0,0,0,0,0},
{1,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,1,1,1,0,1,0,0,0,0,1,1,0,1},
{1,0,1,1,0,0,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0,1,0,0,1,1,0,1,0},
{1,0,1,0,1,1,0,0,0,1,0,0,1,0,0,1,0,0,1,1,0,1,1,1,1,1,0,0,1},
{1,1,1,0,0,0,1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1},
{1,0,1,0,0,0,0,1,0,1,1,1,1,0,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0},
{1,0,1,1,1,1,1,1,0,0,0,0,1,0,1,1,1,0,1,0,1,1,1,1,1,0,0,1,0},
{0,0,0,0,0,0,0,0,1,0,1,0,0,1,1,1,1,1,1,0,1,0,0,0,1,0,0,0,1},
{1,1,1,1,1,1,1,0,1,0,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,0,1,1,0},
{1,0,0,0,0,0,1,0,1,1,1,1,1,0,0,0,1,0,1,0,1,0,0,0,1,0,0,0,1},
{1,0,1,1,1,0,1,0,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0},
{1,0,1,1,1,0,1,0,1,1,1,0,1,1,0,1,0,0,1,1,0,0,0,0,0,0,0,1,1},
{1,0,1,1,1,0,1,0,0,1,1,0,0,1,1,1,0,0,1,0,0,1,1,0,1,1,1,1,0},
{1,0,0,0,0,0,1,0,1,1,1,1,1,1,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1},
{1,1,1,1,1,1,1,0,1,0,0,0,1,0,1,1,0,0,1,0,0,1,1,0,1,0,1,1,1}
}

QRコードをパソコンで読み取る
http://qrcode.red/

QRコードの読み取りに失敗しました

Boole@EvenQ@DivisorSigma[1, i] != 1 - Boole@IntegerQ@Sqrt@i となる i は 2 * j^2 型に限るので，
たまたまそれっぽく見えただけで QR コードにはなっていないのだろう．

やけに桁数が大きいから他にも情報が引き出せるのかと思ったのだが・・・
*/


//【魔方陣】O(?)
/*
* 一部の数字が書き込まれた方陣 a[0..n)[0..n) について，条件に合う魔方陣をそこに構築する（なければ空）
* 書き込まれる値は [1..n^2] とし，欠損値は 0 で表す．
*/
void find_magic_square(vvi& a) {
	int n = sz(a);

	int s = n * (n * n + 1) / 2;

	// 残っている数を記録する双方向リスト（0 番目は根として利用する）
	vi prv(n * n + 2), nxt(n * n + 2);
	iota(all(prv), -1);
	iota(all(nxt), 1);

	vi x_sum(n), x_cnt(n), y_sum(n), y_cnt(n);
	int d_sum = 0, d_cnt = 0, ad_sum = 0, ad_cnt = 0;

	rep(i, n) rep(j, n) {
		x_sum[i] += a[i][j];
		x_cnt[i] += a[i][j] != 0;

		y_sum[j] += a[i][j];
		y_cnt[j] += a[i][j] != 0;

		if (i == j) {
			d_sum += a[i][j];
			d_cnt += a[i][j] != 0;
		}

		if (i + j == n - 1) {
			ad_sum += a[i][j];
			ad_cnt += a[i][j] != 0;
		}

		if (a[i][j] != 0) {
			int v = a[i][j];
			nxt[prv[v]] = nxt[v];
			prv[nxt[v]] = prv[v];
		}
	}
	
	// (i, j): 注目位置
	function<bool(int, int)> dfs = [&](int x, int y) {
//		dump("----",x, y,"----"); dumpel(a); dump(x_sum); dump(x_cnt); dump(y_sum); dump(y_cnt); dump(d_sum, d_cnt, ad_sum, ad_cnt);
		
		if (x == n) return true;

		if (y == n) return dfs(x + 1, 0);

		if (a[x][y] != 0) return dfs(x, y + 1);

		vi is;
		if (x_cnt[x] == n - 1) is.push_back(s - x_sum[x]);
		if (y_cnt[y] == n - 1) is.push_back(s - y_sum[y]);
		if (x == y && d_cnt == n - 1) is.push_back(s - d_sum);
		if (x + y == n - 1 && ad_cnt == n - 1) is.push_back(s - ad_sum);

		uniq(is);
		if (sz(is) >= 2) return false;

		if (sz(is) == 1) {
			int i = is[0];
			if (i <= 0 || n * n < i) return false;
			if (prv[nxt[i]] != i) return false;

			a[x][y] = i;
			x_sum[x] += i; x_cnt[x]++;
			y_sum[y] += i; y_cnt[y]++;
			if (x == y) { d_sum += i; d_cnt++; }
			if (x + y == n - 1) { ad_sum += i; ad_cnt++; }
			nxt[prv[i]] = nxt[i];
			prv[nxt[i]] = prv[i];

			if (dfs(x, y + 1)) return true;

			a[x][y] = 0;
			x_sum[x] -= i; x_cnt[x]--;
			y_sum[y] -= i; y_cnt[y]--;
			if (x == y) { d_sum -= i; d_cnt--; }
			if (x + y == n - 1) { ad_sum -= i; ad_cnt--; }
			prv[nxt[i]] = i;
			nxt[prv[i]] = i;

			return false;
		}

		for (int i = nxt[0]; i <= n * n; i = nxt[i]) {
			a[x][y] = i;
			x_sum[x] += i; x_cnt[x]++;
			y_sum[y] += i; y_cnt[y]++;
			if (x == y) { d_sum += i; d_cnt++; }
			if (x + y == n - 1) { ad_sum += i; ad_cnt++; }
			nxt[prv[i]] = nxt[i];
			prv[nxt[i]] = prv[i];

			if (dfs(x, y + 1)) return true;

			a[x][y] = 0;
			x_sum[x] -= i; x_cnt[x]--;
			y_sum[y] -= i; y_cnt[y]--;
			if (x == y) { d_sum -= i; d_cnt--; }
			if (x + y == n - 1) { ad_sum -= i; ad_cnt--; }
			prv[nxt[i]] = i;
			nxt[prv[i]] = i;
		}

		return false;
	};

	if (!dfs(0, 0)) a.clear();
}


void check_find_magic_square() {
	vvi a{
		{0,3,0},
		{0,0,0},
		{0,0,2}
	};

	find_magic_square(a);

	dumpel(a);

	exit(0);
}


void zikken4() {
	vector<string> s = { 
		"__L9_U",
		"3__KB_",
		"8____V",
		"_2__P_",
		"_D_1__",
		"_J7___"
	};

	int n = 6;
	vvi a(n, vi(n));
	rep(i, n) rep(j, n) {
		if (s[i][j] == '_') a[i][j] = 0;
		else if (s[i][j] <= '9') a[i][j] = s[i][j] - '0' + 1;
		else a[i][j] = s[i][j] - 'A' + 11;
	}
	dumpel(a);

	find_magic_square(a);
	dumpel(a);

	exit(0);
}
/*
ADFGVX 暗号の換字表なら [0-9][A-Z] が各 1 度ずつ現れる．
なんか魔方陣っぽいので，魔方陣になるように他の空欄を埋めてみる．
[0-9] を [1-10] に，[A-Z] を [11-36] に対応させる．

0: 24 13 22 10 11 31
1: 4 33 36 21 12 5
2: 9 28 1 16 25 32
3: 34 3 15 27 26 6
4: 17 14 29 2 19 30
5: 23 20 8 35 18 7

これを ADFGVX 暗号の換字表に直す：

n c l 9 a u
3 w z k b 4
8 r 0 f o v
x 2 e q p 5
g d s 1 i t
m j 7 y h 6

これと何らかの鍵文字で
AAFVVAAFXADVAAVAVGFGVFFFVVAVDAVGAVAV
を復号してみる：

weasel →	zlgm8g01b1aion9nai
dopamine →	nxoranxorsigmafgai →	N XOR A[N] XOR Σf(g(A[i]))
hirakich →	3ggin89s0lbv1ag

出力すべきは
	N XOR A[N] XOR Σf(g(A[i]))
のようだ．

g(A[i]) は A[i] が奇数なら 0，偶数なら 1 を返す関数であり，f(0) = 0, f(1) = 1 なので，
Σf(g(A[i])) は A[1..N] に含まれる偶数の個数を意味する．

サンプル 1 だと，
	5 XOR 5 XOR 2 = 2
で一致しているのでこれで良さそう．
*/


int main() {
//	input_from_file("input.txt");
//	output_to_file("output.txt");
	
	int n;
	cin >> n;

	vi a(n);
	cin >> a;

	int cnt = 0;
	rep(i, n) cnt += a[i] % 2 == 0;

	int res = n ^ a[n - 1] ^ cnt;

	cout << res << endl;
}
0