結果
| 問題 | No.3743 World Mapper |
| コンテスト | |
| ユーザー |
 lif4635
|
| 提出日時 | 2026-09-19 17:54:07 |
| 言語 | PyPy3 (7.3.23 + ACL) |
| 結果 |
RE
不安定
|
| 実行時間 | - |
| コード長 | 24,645 bytes |
| 記録 | |
| コンパイル時間 | 80 ms |
| コンパイル使用メモリ | 89,612 KB |
| 実行使用メモリ | 86,032 KB |
| 最終ジャッジ日時 | 2026-09-19 17:54:30 |
| 合計ジャッジ時間 | 6,298 ms |
|
ジャッジサーバーID （参考情報） |
judge4_0 / judge1_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| 部分点1 | 10 % | RE * 4 |
| 部分点2 | 10 % | RE * 9 |
| 部分点3 | 10 % | RE * 14 |
| 部分点4 | 10 % | RE * 19 |
| 部分点5 | 10 % | RE * 24 |
| 部分点6 | 10 % | RE * 29 |
| 部分点7 | 10 % | RE * 34 |
| 部分点8 | 10 % | RE * 39 |
| 部分点9 | 10 % | RE * 44 |
| 満点 | 10 % | RE * 49 |
| 合計 | 5 * 0% = 0 点 |
ソースコード
# input
import sys
input = sys.stdin.readline
II = lambda : int(input())
MI = lambda : map(int, input().split())
LI = lambda : [int(a) for a in input().split()]
SI = lambda : input().rstrip()
LLI = lambda n : [[int(a) for a in input().split()] for _ in range(n)]
LSI = lambda n : [input().rstrip() for _ in range(n)]
MI_1 = lambda : map(lambda x:int(x)-1, input().split())
LI_1 = lambda : [int(a)-1 for a in input().split()]
mod = 998244353
inf = 1001001001001001001
ordalp = lambda s : ord(s)-65 if s.isupper() else ord(s)-97
ordallalp = lambda s : ord(s)-39 if s.isupper() else ord(s)-97
yes = lambda : print("Yes")
no = lambda : print("No")
yn = lambda flag : print("Yes" if flag else "No")
prinf = lambda ans : print(ans if ans < 1000001001001001001 else -1)
alplow = "abcdefghijklmnopqrstuvwxyz"
alpup = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
alpall = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
URDL = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)}
DIR_4 = [[-1,0],[0,1],[1,0],[0,-1]]
DIR_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]
DIR_BISHOP = [[-1,1],[1,1],[1,-1],[-1,-1]]
prime60 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]
sys.set_int_max_str_digits(0)
# sys.setrecursionlimit(10**6)
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
from collections import defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
DD = defaultdict
BSL = bisect_left
BSR = bisect_right
p = 2503
# p = 2503
# a = []
# for i in range(p - 1):
# a.append(i + (p - 1) * ((i - pow(3, i, p)) % p))
# for i in range(1, 5000):
# b = [(x * i) % (p * (p - 1)) for x in a]
# b.sort()
# ok = [0] * (p - 1)
# for i in range(p - 1):
# x = (b[(i+99) % (p - 1)] - b[i]) % (p * (p - 1))
# if x <= 3 * 10 ** 5:
# ok[i] = 1
# s = None
# for i in range(p - 1):
# if all(ok[i % (p - 1)] for i in range(i, i + 2500)):
# s = i
# break
# if s != None:
# break
# print(s, a)
a = [6260004, 6257503, 6244994, 6202461, 6069856, 5667035, 4453566, 808153, 2391920, 875709, 2584576, 1443665, 4278432, 252715, 695570, 2019129, 5984800, 5351795, 3447774, 3993211, 5624516, 4250919, 125122, 267737, 690576, 1954087, 5739614, 4566177, 1040860, 2984915, 2549568, 1238521, 3562880, 4268445, 117628, 185183, 382842, 970813, 2729720, 1738929, 5024056, 2349419, 583008, 1541275, 4411070, 490437, 1248544, 3517859, 4058292, 5674585, 4255952, 6257553, 5994844, 5201711, 2817306, 1921591, 5491946, 3672993, 4473634, 608045, 1531284, 4295995, 60110, 6134967, 5567014, 3858149, 4989054, 2114257, 6009872, 5166699, 2632174, 1286099, 3505374, 3895687, 5061620, 2291907, 240268, 342851, 645594, 1548817, 4253480, 6099957, 5371876, 3182627, 2872380, 1936633, 5386892, 3207651, 2927428, 2081753, 5802228, 4433635, 322850, 510501, 1068448, 2737283, 1476276, 3950755, 5106680, 2306943, 165232, 6260105, 5752200, 4223479, 5894816, 4641315, 875806, 2099285, 5764716, 4230991, 5887316, 4588779, 688162, 1506317, 3955776, 5036641, 2011724, 5456979, 3262726, 2937467, 1956684, 5271835, 2687270, 1191075, 2959990, 1999223, 5374422, 2970001, 2014238, 5404449, 3045064, 2224409, 6019944, 4876531, 1441286, 3655557, 4030858, 5151755, 2246934, 6052477, 4939088, 1593915, 4078402, 5264351, 2554686, 683191, 1326206, 3250245, 2754850, 1263659, 3047586, 2131855, 5642162, 3643065, 3903274, 4678895, 738246, 1436305, 3525476, 3525477, 3520474, 3500459, 3435408, 3235249, 2629766, 808311, 1601446, 3975845, 4831530, 1131073, 2549708, 538101, 760780, 1423811, 3407898, 3092647, 2141888, 5547111, 3232762, 2547215, 485568, 558127, 770798, 1403805, 3297820, 2712353, 950946, 1924225, 4839056, 1053531, 2216962, 5702249, 3628092, 3663121, 3763202, 4058439, 4939144, 1313747, 2957562, 1621495, 3870794, 4351179, 5787328, 3828263, 4208568, 5344477, 2484692, 162837, 5717278, 3588077, 3457974, 3062659, 1871708, 4556355, 80278, 5434559, 2704878, 773335, 1236206, 2619813, 503122, 410549, 127824, 5537149, 2972600, 1536453, 3485512, 3065177, 1799166, 4258633, 5369522, 2434677, 6150148, 4766543, 610722, 663265, 815888, 1268751, 2622334, 415571, 52782, 5221915, 1936790, 4601421, 65296, 5239433, 1969320, 4678987, 277970, 5857431, 3803290, 3898367, 4178592, 5014261, 1253756, 2492247, 6202714, 4804097, 603240, 520675, 267974, 5767371, 3473038, 2847539, 966036, 1579027, 3412994, 2647383, 345544, 5960033, 4010976, 4421305, 5647286, 3057717, 1546510, 3270389, 2174514, 5144389, 1523996, 3182823, 1891792, 4276199, 5161908, 1551523, 3240374, 2039415, 4694038, 127889, 5211954, 1671625, 3570644, 3000189, 1283818, 2392205, 5712360, 3142807, 1691648, 3595671, 3040228, 1368893, 2612388, 75361, 4984286, 918537, 1241296, 2204567, 5089374, 1213777, 2106992, 4781631, 275530, 5539739, 2539842, 6060157, 4091084, 4441365, 5487202, 2357201, 5487204, 2347195, 5447174, 2217093, 5046856, 1006127, 1403946, 2592397, 6152744, 4303767, 5014336, 878531, 991122, 1323889, 2317184, 5292063, 1686682, 3390545, 2234622, 5024353, 863528, 901059, 1008646, 1326401, 2274660, 5114431, 1103726, 1591617, 3050284, 1158773, 1741740, 3485635, 2449808, 5599827, 2519866, 5799989, 3110340, 1298893, 2122052, 4586523, 5712424, 2822615, 410688, 5694913, 2755064, 193017, 5026882, 735953, 383172, 5582329, 2387276, 5322123, 1596646, 2940221, 703434, 250573, 5149490, 1053717, 1286404, 1979459, 4053618, 4008583, 3868472, 3443133, 2162110, 4576541, 5552322, 2212153, 4711652, 5942637, 3368080, 1901909, 3760896, 3070345, 993686, 1021209, 1098772, 1326455, 2004498, 4033621, 3853478, 3308043, 1666732, 3000299, 733488, 190555, 4819256, 6175341, 3976084, 3635813, 2609994, 5790037, 2800148, 87981, 4471486, 5091983, 685962, 6250411, 4151234, 4111203, 3986104, 3605801, 2459886, 5279641, 1208888, 1516635, 2434870, 5184569, 903648, 580891, 5870120, 2945283, 428272, 5397245, 1511640, 2374831, 4959398, 183081, 4636642, 5467307, 1691790, 2885245, 198098, 4656663, 5502340, 1771859, 3100422, 818599, 230630, 4724223, 5674984, 2259755, 4534074, 5089519, 488342, 5467323, 1611742, 2565005, 5419788, 1454119, 2077118, 3941109, 3265570, 1233947, 1396578, 1879465, 3323120, 1386573, 1834432, 3173003, 921204, 423307, 5187116, 686019, 5965240, 3010379, 403296, 5102053, 405800, 5099553, 388288, 5037005, 190632, 4434025, 4634186, 5229663, 748582, 6087851, 3313134, 1246483, 1304030, 1471665, 1969564, 3458255, 1656816, 2509999, 5064542, 198153, 4381498, 4401515, 4456560, 4616689, 5092070, 250701, 4509106, 4754303, 5484888, 1409131, 1701866, 2575065, 5189656, 503411, 5227188, 605995, 5524928, 1489203, 1902034, 3135521, 568470, 5387323, 1051358, 563469, 5357302, 946277, 233208, 4351501, 4176362, 3645939, 2049664, 3518339, 1656852, 2329891, 4344002, 4118823, 3438280, 1391645, 1509240, 1857019, 2895350, 6005337, 2805280, 5725115, 1954602, 3163069, 520958, 5114631, 103126, 3851123, 2565096, 4964515, 5895260, 2419983, 4514158, 4529171, 4569204, 4684297, 5024570, 6040383, 2820310, 5680097, 1729440, 2397475, 4396574, 4126359, 3310708, 858749, 6022878, 2722741, 5342336, 671103, 5439916, 953831, 15582, 3458335, 1256576, 908799, 6122968, 2972951, 6042906, 2722753, 5282300, 430923, 4659304, 4814429, 5274798, 388393, 4511690, 4351563, 3866176, 2405009, 4279008, 3633493, 1691942, 2124789, 3418324, 1031417, 128196, 3676033, 1789526, 2387505, 4176436, 3275717, 568554, 4967071, 5632604, 1361691, 1068958, 185753, 3793638, 2087275, 3225686, 373407, 4336576, 3696065, 1769526, 2247409, 3676052, 1694469, 2007220, 2940467, 5735202, 1589389, 1671956, 1914651, 2637730, 4801961, 5027142, 5697679, 1441778, 1194081, 445984, 4459193, 3968802, 2492623, 4321586, 3540963, 1194088, 410963, 4319088, 3513445, 1091510, 83205, 3315790, 483527, 4506744, 4046377, 2660270, 4759449, 4789474, 4874543, 5124744, 5870341, 1839620, 2267463, 3545986, 1114043, 75714, 3218227, 115748, 3328317, 436006, 4279079, 3278280, 270877, 3768674, 1732047, 1879666, 2317517, 3626064, 1284193, 516080, 4469241, 3798706, 1782095, 1989762, 2607757, 4456736, 3736161, 1569430, 1326737, 593652, 4651897, 4296614, 3225759, 8188, 2875481, 5209848, 5945437, 1884692, 2222463, 3230770, 6250685, 2780412, 4889599, 4949648, 5124789, 5645206, 938945, 5602674, 801337, 5179838, 5785323, 1334266, 501101, 4259106, 3003103, 5492594, 431049, 4028926, 2292539, 3340878, 218383, 3370904, 298449, 3601090, 978995, 5632716, 801355, 5089784, 5425053, 163348, 3160745, 5885424, 1529443, 981506, 5595195, 643738, 4571879, 3826284, 1584493, 1116620, 5970501, 1739620, 1566983, 1044066, 5732815, 1006538, 5610219, 628738, 4466807, 3450996, 398557, 3761246, 1319295, 250942, 3303383, 6193194, 2332609, 3270860, 6080607, 1979830, 2197505, 2845524, 4784575, 4334216, 2978133, 5167384, 5467625, 100836, 2782981, 4561904, 3631161, 833926, 4962227, 4817112, 4376761, 3050702, 5330025, 5900482, 1344341, 195924, 3008173, 5177408, 5417601, 6133174, 2012381, 2170008, 2637883, 4036502, 1964847, 2007382, 2129981, 2492772, 3576139, 558728, 4026501, 1899802, 1777205, 1404408, 281011, 3168320, 5562735, 215962, 2958155, 4917222, 4526911, 3350972, 6080655, 1739686, 1236785, 5985582, 1439449, 321056, 3223377, 5662828, 451163, 3598680, 511213, 3768818, 1011615, 5260012, 5475185, 6115698, 1769725, 1251812, 5955573, 1274332, 6013121, 1436964, 228499, 2860604, 4489407, 3108304, 5222495, 5297556, 5517733, 6173258, 1872321, 1489516, 336095, 3133332, 5257531, 5362616, 5672865, 336100, 3108317, 5157456, 5037361, 4672070, 3571191, 263548, 2860625, 4384344, 2687989, 3856424, 1094217, 5327602, 5497739, 6003144, 1251847, 5780468, 573807, 3736336, 693905, 4086618, 1734739, 936602, 4799691, 3858940, 1031681, 5069910, 4654579, 3403580, 5908083, 891574, 4624559, 3293496, 5557807, 6083228, 1391979, 6100744, 1434515, 6218340, 1777291, 974150, 4822227, 3836440, 874073, 4506978, 2875675, 4239266, 2062527, 1789810, 966653, 4754682, 3588751, 85952, 2097561, 1864876, 1161815, 5310132, 5225065, 4964858, 4179231, 1817344, 989183, 4762200, 3551233, 6175832, 1519611, 70954, 1982483, 1449558, 6108283, 1291934, 5625399, 6095776, 1239395, 5452764, 5562853, 5888114, 596385, 3503710, 5958173, 791544, 4074169, 1392026, 5865603, 493810, 3160943, 4894830, 3828979, 626420, 3538749, 6008224, 886631, 4304364, 2027545, 1454588, 5993217, 816580, 4069181, 1296966, 5500327, 5580392, 5815581, 253636, 2350313, 2372832, 2435383, 2618030, 3160965, 4784764, 3388649, 5457804, 5397757, 5212610, 4652163, 2965816, 4164275, 1492140, 5995741, 714020, 3651369, 6195904, 1299491, 5392764, 5142565, 4386962, 2115147, 1557202, 6140867, 1099338, 4757263, 3201020, 4789791, 3288592, 5042495, 4036692, 1014277, 4467038, 2295303, 2037598, 1259477, 5182614, 4422007, 2135180, 1532199, 5980756, 533903, 2975856, 4034203, 941732, 4184325, 1382086, 5495375, 5305224, 4729765, 2998382, 4061733, 984274, 4271903, 1604772, 6123385, 886700, 3959157, 646510, 3228575, 4707258, 2875795, 3638906, 5923233, 246196, 1997597, 984288, 4201861, 1324562, 5212671, 4346980, 1744901, 196164, 1807453, 373808, 2330373, 1932556, 734099, 3396228, 5115103, 4004216, 666549, 3173554, 4427057, 1920054, 656545, 3123518, 4256925, 1389634, 5307767, 4532148, 2200285, 1462196, 5505429, 5105110, 3899147, 276252, 1927573, 614024, 2930877, 3613924, 5658059, 5522952, 5112625, 3876638, 163671, 1544776, 5683085, 5567994, 5217715, 4161872, 989337, 3991738, 468923, 2420484, 2007655, 764162, 3291183, 4604734, 2277875, 1554798, 5643067, 5377856, 4577217, 2170294, 1207025, 4574718, 2147779, 1124462, 4312011, 1344640, 4962533, 3286194, 4514677, 1932614, 443925, 2235358, 1342145, 4920006, 3123571, 3991766, 328839, 1860064, 186227, 1422216, 5125177, 3704042, 5698137, 5412910, 4552223, 1965156, 461455, 2207852, 1179531, 4352068, 1339661, 4822446, 2740783, 2753294, 2785821, 2878396, 3151115, 3964266, 136207, 1172036, 4274517, 1051942, 3904223, 6193554, 531529, 2327966, 1449765, 5072662, 3411335, 4684854, 2237899, 1154534, 4161939, 654136, 2650733, 2373012, 1534843, 5277836, 3976797, 68674, 864311, 3246216, 4124419, 491516, 2112813, 709192, 2755829, 2628228, 2240419, 1071986, 3824187, 5813278, 5513039, 4607316, 1885141, 6238622, 506541, 2092810, 584105, 2315490, 1242133, 4279562, 861831, 3128644, 3661571, 5255346, 3769159, 5568098, 4697403, 2080312, 486539, 1962720, 123751, 864344, 3081117, 3463924, 4607339, 1770072, 5778277, 5272874, 3751659, 5445514, 4259567, 696720, 2528185, 1755068, 5693217, 4977646, 2825927, 2628270, 2030293, 231356, 1092045, 3669106, 5132777, 3256278, 3884281, 5763284, 5132781, 3236266, 3804221, 5503080, 4332145, 814334, 2780907, 2413114, 1304729, 4237074, 504091, 1825148, 5783313, 5127790, 3156215, 3498990, 4522309, 1324754, 4252095, 504100, 1780121, 5603178, 4542331, 1354784, 4312149, 654226, 2200463, 571662, 1942759, 6051044, 5845881, 5225386, 3358895, 4016922, 5985997, 5625710, 4539843, 1277236, 4009421, 5938464, 5458081, 4011926, 5930961, 5420554, 3884327, 5533146, 4212091, 243920, 859413, 2700886, 1957793, 5986014, 5540659, 4199588, 171369, 606718, 1907759, 5805876, 4970209, 2458202, 1179681, 3601618, 4599917, 1327302, 4029463, 5868434, 5117835, 2861032, 2348123, 804390, 2430691, 1042082, 3133755, 3141262, 3158777, 3206316, 3343927, 3751754, 4970229, 2358142, 779381, 2300598, 596737, 1742654, 5175399, 2943616, 2505767, 1187214, 3489055, 4127066, 6036093, 5495662, 3869363, 5247966, 3116263, 2978654, 2560821, 1302316, 3784301, 4962744, 2230561, 291512, 731865, 2047918, 5991071, 5290512, 3183829, 3121280, 2928627, 2345662, 591761, 1587558, 4569943, 987080, 2758497, 1805236, 5202953, 2866086, 2112985, 6111182, 5575755, 3964468, 5388107, 3391512, 3659227, 4457366, 584271, 1484992, 4182149, 6006108, 5210473, 2818562, 1900329, 5403130, 3381515, 3574170, 4147129, 5861000, 4735101, 1352398, 3724295, 4572474, 849499, 2200580, 6248817, 5863510, 4702583, 1214796, 3271441, 3173864, 2876127, 1977910, 5540759, 3699288, 4432375, 364124, 679377, 1620130, 4437383, 359124, 644353, 1495034, 4042071, 5415670, 3268955, 3086310, 2533369, 869540, 2135553, 5928586, 4777667, 1319904, 3466621, 3639260, 4152171, 5685898, 4019567, 5278074, 2786083, 1567610, 4169691, 5708422, 4057103, 5360646, 3003763, 2190614, 6008667, 4932808, 1700225, 4522482, 459235, 789500, 1775289, 4727650, 1054715, 2555916, 792007, 1757780, 4650093, 797014, 1757783, 4635084, 736969, 1562630, 4034607, 5183026, 2360771, 151506, 6043717, 4927826, 1575147, 4037116, 5155511, 2243184, 6026209, 4845266, 1297431, 3173932, 2535923, 616890, 1117291, 2613488, 834567, 1755304, 4512509, 254106, 6261409, 5490794, 3173943, 2480890, 396725, 401730, 411739, 436760, 506817, 711982, 1322471, 3148932, 2360803, 6253916, 5403237, 2846194, 1432565, 3449178, 3231505, 2573480, 594399, 914656, 1870421, 4732710, 789559, 1480112, 3546765, 3479212, 3271547, 2643546, 754537, 1345010, 3111423, 2143150, 5495831, 3023856, 1865431, 4647656, 464313, 434290, 339215, 48984, 5435791, 2803688, 1164879, 2505952, 261659, 6048786, 4617643, 319208, 6206415, 5075512, 1677797, 4004658, 4717729, 589430, 724539, 1124860, 2320817, 5903682, 4122259, 5035490, 1507671, 3444220, 2986355, 1607754, 3729451, 3827030, 4114761, 4972948, 1279997, 2721150, 777097, 1202438, 2473455, 18994, 5175617, 1852962, 4405003, 5793614, 3691935, 3644398, 3496781, 3048924, 1700347, 3912116, 4279911, 5378290, 2405915, 6008796, 4287421, 5380796, 2393409, 5951254, 4094771, 4782822, 579463, 489392, 214173, 5646016, 3149021, 1915536, 4472581, 5876204, 3819561, 3907132, 4164839, 4932954, 969787, 1600292, 3486801, 2878816, 1049855, 1820472, 4127317, 4780340, 471897, 66574, 5108105, 1440174, 2956387, 1237514, 2338395, 5636032, 2998925, 1345104, 2641141, 261740, 5643543, 2996428, 1312583, 2518548, 6131437, 4440086, 5623533, 2906362, 1012349, 1587810, 3309187, 2205806, 5153163, 1465216, 2921381, 1022364, 1582813, 3259154, 2020665, 4562698, 5921285, 3729534, 3411781, 2453516, 5836221, 3454318, 2566109, 6158982, 4407583, 5410886, 2153283, 4900480, 612053, 266778, 5488453, 2360954, 5498463, 2380972, 5548505, 2521086, 5958835, 3742064, 3349251, 2165806, 4872971, 464448, 6021391, 3899696, 3792111, 3464350, 2476061, 5768694, 3116575, 1417718, 2578647, 6056428, 3959753, 3927228, 3824647, 3511898, 2568645, 5996386, 3749591, 3266706, 1813045, 3709562, 3131601, 1392712, 2433545, 5551038, 2373499, 5360888, 1793037, 3609490, 2791337, 331872, 5473483, 2105792, 4522725, 5506012, 2188361, 4755414, 6189061, 4222490, 4580277, 5648632, 2586185, 5918850, 3386827, 2048258, 4290051, 4747918, 6116513, 3954786, 3727105, 3039056, 969903, 1019944, 1165061, 1595406, 2881435, 472010, 5763741, 2846410, 351917, 5388444, 1705501, 3176678, 1322697, 2018254, 4099919, 4077402, 4004845, 3782168, 3109131, 1085014, 1270163, 1820604, 3466921, 2138360, 4410177, 4958116, 334421, 5245848, 1187605, 1532882, 2563707, 5651176, 2383565, 5100738, 722239, 106748, 4517775, 5220838, 1062515, 1107552, 1237657, 1622966, 2773887, 6221644, 4034897, 3732156, 2818927, 74234, 4360161, 4687924, 5666207, 2333544, 4855561, 6154100, 3782205, 2924020, 344459, 5125782, 677227, 6114074, 3632091, 2443642, 5135795, 682236, 6104071, 3577052, 2253495, 4540324, 5133299, 644712, 5961463, 3119192, 849879, 299440, 4905623, 6194154, 3792235, 2843978, 6256707, 3964876, 3346883, 1487898, 2168443, 4205072, 4047447, 3569566, 2130917, 4072470, 3629617, 2296052, 4552857, 5055760, 296957, 4803060, 5791351, 2488712, 5100801, 407050, 5108309, 419562, 5135833, 492122, 5343501, 1105114, 909959, 319488, 4805575, 5733818, 2251035, 4322692, 4270151, 4107522, 3614629, 2130944, 3937389, 3089212, 539675, 5411070, 1232731, 1217720, 1167681, 1012558, 542183, 5388558, 1135159, 894968, 169389, 4250152, 3962423, 3094230, 484645, 5175896, 457125, 5083324, 169397, 4210128, 3802303, 2573822, 5145879, 332032, 4673003, 5165898, 377071, 4793102, 5511177, 1397890, 1578035, 2113464, 3714745, 2251076, 4117569, 3449536, 1440431, 1670616, 2356165, 4407806, 4295217, 3952444, 2919119, 6076644, 3019201, 104372, 3879891, 2676430, 5323547, 734880, 5751391, 2008400, 3299433, 905020, 6241787, 3459564, 1370395, 1360388, 1325361, 1215274, 880007, 6131706, 3094279, 239498, 4195161, 3532132, 1538039, 1813260, 2633917, 5090882, 6194265, 3236902, 622313, 5298552, 534745, 5025836, 5969091, 2531344, 4738109, 5090892, 6144235, 3036752, 6234309, 3296962, 742421, 5598804, 1375429, 1225310, 769947, 5661358, 1543067, 1708200, 2198593, 3664766, 1795773, 2446294, 4392851, 3965010, 2676481, 5068394, 5976621, 2433790, 4325303, 3732330, 1948405, 2854130, 5566299, 1172788, 512261, 4788180, 5085919, 5974130, 2371251, 4082620, 2949215, 5806500, 1848337, 2493854, 4425399, 3952522, 2528885, 4515474, 4207729, 3279488, 489759, 4640578, 4563017, 4325328, 3607255, 1448030, 1227855, 562324, 4823231, 5075934, 5829037, 1820834, 2316231, 3797416, 1973459, 2759088, 5110969, 5899100, 1995981, 2806630, 5233571, 6246882, 3019303, 5856572, 1838361, 2303734, 3694847, 1600674, 1575655, 1495592, 1250397, 509806, 4545533, 4122696, 2849179, 5286128, 66957, 3191956, 36935, 3091878, 5989195, 2151128, 3156933, 6169342, 2676551, 4718184, 4575571, 4142726, 2839185, 5186062, 5959181, 2011026, 2686567, 4708184, 4505523, 3892534, 2048561, 2774142, 4945879, 5193578, 5931669, 1878430, 2238719, 3314580, 274651, 3674870, 1345509, 614926, 4680677, 4347912, 3344611, 329702, 3804981, 1700800, 1645757, 1475622, 960211, 5671478, 1012755, 5819098, 1445603, 845124, 5301187, 6139358, 2386359, 3647368, 1162883, 6229434, 2636563, 4377956, 3334623, 199618, 3314609, 129564, 3094435, 5721536, 1072821, 5909188, 1625765, 1295502, 299707, 3569822, 850149, 5211136, 5764079, 1155396, 6111859, 2188724, 2939325, 5186122, 5659001, 810126, 5046013, 5223656, 5751579, 1067836, 5799119, 1200444, 6186931, 2353868, 3374685, 169624, 3074447, 5521404, 332257, 3547328, 662523, 4528114, 3594869, 790128, 4895911, 4683242, 4040229, 2106184, 2561549, 3922638, 1738393, 1443158, 552447, 4137814, 2363897, 3299646, 6101887, 1978592, 2128713, 2574070, 3905135, 1630818, 1065367, 5626514, 517431, 3972694, 1808465, 1573278, 862711, 4988510, 4835889, 4373020, 2979407, 5056068, 5018539, 4900946, 4543161, 3464800, 224711, 3024450, 5156155, 5283758, 5661561, 527458, 3907661, 1518252, 607525, 4132844, 2178783, 2574100, 3755045, 1030368, 5376343, 5884250, 1140459, 5691598, 552491, 3917682, 1483237, 437402, 3557397, 387364, 3397271, 6159480, 1916089, 1705922, 1070415, 5421394, 5944313, 1245558, 5931805, 1198022, 5779185, 730150, 4365557, 2741760, 4127869, 2018684, 1948629, 1733458, 1082939, 5388882, 5776693, 672614, 4142889, 2023696, 1923617, 1618374, 697639, 4192934, 2148801, 2273902, 2644199, 3750084, 800227, 4470662, 2951949, 4653310, 3489881, 6257094, 2028715, 1863584, 1363185, 6119488, 1595873, 545034, 3650017, 434948, 3309747, 5666632, 207269, 2611692, 3557449, 127208, 2356491, 2776828, 4032833, 1533336, 292345, 2826872, 4162941, 1903636, 1383221, 6079476, 1375717, 6046952, 1268133, 5714188, 259829, 2679264, 3670057, 374924, 3009531, 4645840, 3287255, 5469000, 5746723, 312380, 2791863, 3962800, 1208099, 5464002, 5701693, 147254, 2266449, 2356522, 2621735, 3412368, 5779261, 349922, 2844417, 4060390, 1440797, 6102024, 1293181, 5649164, 6187095, 1533376, 92225, 2026272, 1560901, 159782, 2213925, 2108842, 1788587, 822816, 4183003, 1733546, 642675, 3627562, 52205, 1846140, 960433, 4560812, 2831931, 3902788, 847847, 4203030, 1738561, 602654, 3452433, 5734258, 49715, 1778598, 697735, 3712646, 227361, 2291512, 2216453, 1986270, 1290715, 5461550, 5444037, 5386492, 5208851, 4670922, 3052129, 4453250, 2389101, 2454154, 2644307, 3209760, 4901113, 3707660, 122295, 1886206, 910427, 4240590, 1701061, 339974, 2514213, 2769418, 3530027, 5806848, 107293, 1791140, 575169, 3184756, 4746005, 3162240, 4668445, 2919548, 3930357, 695272, 3510023, 5686764, 5949475, 470096, 2814471, 3580084, 5871917, 217398, 2036353, 1225706, 5051265, 3997924, 832895, 3857814, 402553, 2556776, 2751933, 3332398, 5068787, 4010442, 830401, 3810284, 219915, 1968814, 947999, 4143054, 1198201, 4883648, 3409971, 5246440, 4488335, 2209014, 1628551, 6144662, 900471, 3950410, 570209, 2949612, 3820309, 164888, 1718631, 112348, 1550999, 5861946, 2263, 1205726, 4811109, 3097240, 4213133, 1293300, 5053807, 3805310, 54813, 1323328, 5123867, 3995466, 605257, 2954636, 3735261, 6072130, 552719, 2776998, 3182323, 4393292, 1758687, 112372, 1430927, 5381586, 4703545, 2664416, 2804529, 3219862, 4460855, 1916322, 540223, 2669426, 2789523, 3144808, 4205657, 1120692, 4385803, 1651118, 5967069, 122398, 1370897, 5111388, 3802843, 6134708, 600285, 2779528, 3049745, 3855390, 4813, 973088, 3872907, 42346, 1070669, 4150632, 860503, 3510122, 5191467, 3967990, 292553, 1786248, 6262327, 898040, 3587691, 5389132, 4525943, 1931370, 405151, 2083994, 853011, 3417562, 4843703, 2854614, 3144847, 4010540, 340107, 1848814, 107423, 1140750, 4235725, 990632, 3775359, 5862028, 5854523, 5827002, 5739433, 5471720, 4663575, 2234134, 1203311, 4368342, 1333417, 4748648, 2464323, 1868848, 77417, 960624, 3605239, 5271572, 4003059, 192514, 1280885, 4540992, 1791295, 6062210, 82431, 925606, 3450125, 4756170, 2406793, 1616162, 5501769, 4628572, 2003975, 387684, 1796311, 6017186, 6149793, 280102, 1453541, 4968852, 2984767, 3290012, 4200741, 665416, 2579447, 2054028, 472765, 1986476, 260097, 1338460, 4568543, 1728774, 5729473, 5201552, 3612783, 5103976, 3310043, 4185744, 545335, 2144114, 672939, 2516914, 1781327, 5832066, 5454265, 4315856, 895623, 3154930, 3665339, 5191560, 3502711, 4693664, 1999011, 172552, 950675, 3280038, 4000615, 6157340, 97497, 700480, 2504423, 1648740, 5339191, 3880526, 5762031, 5139034, 3265037, 3900546, 5802067, 5239118, 3545265, 4721206, 1981517, 19950, 392749, 1506140, 4841307, 2316790, 1000739, 3310086, 3970615, 5947196, 5609427, 4591114, 1531169, 4871340, 2361835, 1090820, 3535275, 4601128, 1531175, 4841322, 2241745, 700514, 2334321, 968230, 3127457, 3337626, 3963127, 5834624, 5181603, 3217534, 3582827, 4673700, 1678807, 5214134, 3290097, 3775486, 5226647, 3312618, 3828031, 5369264, 3725451, 5051512, 2762183, 2151696, 315229, 1063328, 3302619, 3752980, 5099057, 2869776, 2439433, 1143398, 3512793, 4353466, 607973, 1891500, 5737075, 4743782, 1758897, 5324248, 3490283, 4245888, 245191, 763106, 2311845, 690550, 2084165]
s = 0
n = II()
# print(i)
a = []
for i in range(2500):
a.append((b[(s + i) % (p - 1)] - b[s]) % (p * (p - 1)))
# print(i, s, a)
g = [[0] * n for i in range(n)]
for i in range(n):
if i & 1:
for j in range(n):
g[i][j] = a[i*n + j]
else:
for j in range(n):
g[i][~j] = a[i*n + j]
for i in range(n - 1):
a = [abs(g[i][j] - g[i+1][j]) for j in range(n)]
print(*a)
for i in range(n):
a = [abs(g[i][j] - g[i][j+1]) for j in range(n - 1)]
print(*a)