情報活用編プラス
第3章「コンピュータとプログラミング」
IP02-11
実践プログラム④ 整列アルゴリズム 選択法
8. ✏️選択法を改善しよう ( 8 / 11 )
学習の目的
1. 選択法と改良版選択法の違い
2. 改良版選択法の仕組み
3. Pythonで改良版選択法のプログラムを完成させよう
4. 選択法と改良版選択法の効率の違いを確認しよう
これから、選択法のアルゴリズムを改善したいと思います。
改善てことは、並び替える時間が短くなるってことですか？
そのとおりです。並び替えの実行に必要な時間が短くなります。
どうやるんだろう⋯二分探索みたいに半分にしていくとか？
半分にして並び替えていくのであれば、それもう選択法とはよべないですね。
添字の操作は変えずに効率を良くする方法を考えましょう。
次のアプリは選択法で並べ替えをシミュレートしていますが、左がこれまでの選択法、右が改良版です。
２つとも再生ボタンを押して違いを比べてみましょう。
両方とも再生したら、比較回数は一緒だけど、交換回数が違う。改良版の方が少ない。
左の選択法は、最初に「35」と「12」を比較したあと交換しているんだけれど、改良版は交換していないんだよね。
気付いた？
気づかなかった。もう1回やってみよう。
改良版は交換回数が減っていることがわかりました。どのようにして交換回数を減らしているのか確認しましょう。
改良版選択法は交換回数を少なくすることで効率を上げています。交換を減らすとなぜ効率が上がるのでしょうか。
交換部分のフローチャート
フローチャートでわかるように、1回の交換で3命令が実行されています。交換が1回減ると単純に3命令実行する命令が減ります。
100回交換が減ると300命令減るってことですよね。
コンピュータは1秒間に何百万って命令実行するから、命令数が減ってもあまり実行時間に関係ないような気がします。
命令実行だけなら速いのですが、変数に代入などしているとメモリにアクセスするので遅くなります。
なるほど、じゃあ交換処理は変数に代入処理を3回している交換の回数が減ることは効果がありそうですね。
それでは、改良版選択法のアルゴリズムについて確認します。
新しい変数「min_index」を使用します。この変数は範囲内の最小値の添字を管理します。
次の配列データを並べ替えます。
これまでの選択法なら、ここで0番目と1番めの要素を交換していたよね。
交換はせず小さい方の添字を変数 min_index に代入してます。
次の比較に進みましょう。
あれ？隣同士を比較してるよね？これは交換法じゃないの？
いいところに気づきましたね。確かに隣同士を比較していますが、交換法ではありません。
でも基準としている位置が0番目から1番めに変わっています。
基準値の位置に注意して、次の手順を確認しましょう。
あっ！わかった。基準としているのは min_index だ！
なるほど！一番小さい値を探さなきゃだから、小さい値の添字を入れている min_index と比較しているのか。
よく気づきましたね。min_index と j を使って data[ min_index ] の要素と data[ j ] の要素を比較しています。
ここで、配列の最後まで比較をしました。一番小さい値は min_index 番目にある要素だとわかりました。
ということは、一番小さい値は配列の先頭にいれるから⋯変数 i 番目に入れればよいのかな？
はい、そうです。data[ i ]番目とdata[ min_index ]番目を交換します。
ここで、ようやく交換だ。全部と比較したら1回だけ交換するのですね。
そうですね。最小値が決まったら、iを1加算して次の最小値を探します。
同じ処理をすべての要素に対して繰り返して行います。
この手順を早速Pythonプログラムにしましょう。
次の改良版選択法のプログラムは（ａ）、（ｂ）、（ｃ）の3箇所が空欄になっています。
改良版の手順を確認しながら一緒に空欄を埋めていきましょう。
import random
import time
# 配列をランダムに生成する関数
def generate_array(size=10, low=1, high=100):
return random.sample(range(low, high+1), size) # 重複なし
# ===== メイン処理 =====
data = generate_array(10, 1, 100) # 配列を作成
print("ソート前の配列:", data)
n = len(data)
compare_count = 0
swap_count = 0
# 改良版選択法の開始
start = time.time()
for i in range(n - 1):
（ａ）
for j in range(i + 1, n):
compare_count += 1
if （ｂ）
（ｃ）
if min_index != i:
# temp変数で交換
temp = data[i]
data[i] = data[min_index]
data[min_index] = temp
swap_count += 1
end = time.time()
print("ソート後の配列:", data)
print("比較回数:", compare_count)
print("交換回数:", swap_count)
print("処理時間: {:.6f} 秒".format(end - start))
空欄（ａ）、（ｂ）、（ｃ）に命令を入れてプログラムを完成させてください。
各空欄は、命令一覧から選んで埋めましょう。
空欄（ａ）に入る命令を選んでください。
わからない場合はヒントを参考にしましょう。
下記から正しい命令を選んでください。
min_index = 0
min_index = 1
min_index = i
min_index = data[0]
空欄（ａ）に入る命令を答えてください。
空欄（ａ）は、比較する基準となる添字位置を設定する命令が入ります。
比較するのはどの位置の要素とだったか覚えてますか？
min_index番目と j 番目を比較していました。
空欄（ａ）の次の行で j には値が入るから min_index に値を入れれば良いってことですね。
空欄（ａ）には min_index の初期値が入ります。
外側の繰り返し処理の先頭で行う処理です。1回目、2回目、3回目の繰り返しを行うときの変数の内容を確認してみましょう。
1回めの繰り返し処理のときの変数の値
2回目の繰り返し処理のときの変数の値
3回目の繰り返し処理のときの変数の値
わかった！min_indexには、繰り返しの最初で確定していない範囲の先頭の添字の値が入るのね。
なるほど。そういうことであれば、iと同じ値だね。
空欄（ｂ）に入る命令を選んでください。
わからない場合はヒントを参考にしましょう。
下記から正しい命令を選んでください。
min_index < j :
data[i] < data[j] :
data[min_index] < data[i] :
data[min_index] > data[j] :
空欄（ｂ）に入る命令を答えてください。
空欄（ｂ）は、配列の中で最小の値を探すための比較が入ります。
改良版選択法では、現在の最小値よりも小さい値が配列に現れたら、交換せずその添字を残しておきます。
最小値がmin_indexに入っているから、min_indexと比べればいいのかな？
min_indexは添字だから、data[min_index]で配列の要素の値と配列のデータを比較しないといけないよね。
そっか、添字を比べても仕方ないもんな。min_index番目の要素の値と j 番目の要素の値を比較すればいいのか。
下記から正しい命令を選んでください。
min_index = 1
min_index = len(data)
min_index = i
min_index = j
空欄（ｃ）に入る命令を答えてください。
空欄（ｃ）は、空欄（ｂ）の条件が成立したときに実行される処理です。
空欄（ｂ）はより小さい値を探すための条件だから、小さい方の添字位置にmin_indexを更新しないとね。
うんうん。空欄（ｃ）には data[min_index] と data[ j ]を比較して data[ j ] が小さいときに、data[ j ]の添字を min_index に代入すればいいってことだね。
改良版選択法が実際にどのくらい効率が良くなったか調べます。
そのために選択法と改良版選択法の両方のプログラムで、同じデータを並べ替えを行ったときの処理時間を比べることにします。
スライド「選択法のプログラムを作ろう」の選択法のPythonプログラムと今回の改良版選択法のプログラムに次のデータをセットします。
プログラムを修正する行番号について
選択法、改良版選択法ともに16行目「
data = generate_array(20, 1, 100000) # 配列の作成」
を下記の命令に置き換えてください。
data = [24345, 34235, 20560, 45934, 26891, 40557, 1793, 59905, 6471, 96239, 2916, 84470, 36745, 89409, 85157, 54849, 56149, 74998, 24567, 50681, 19198, 35460, 455, 89832, 80840, 39658, 25544, 73351, 21806, 68403, 82708, 2950, 39773, 7697, 21218, 51058, 99198, 96338, 21166, 66896, 88038, 52476, 21894, 46910, 87707, 87643, 8248, 93716, 47557, 7504, 19946, 19272, 57499, 36046, 50405, 85542, 42499, 11379, 48894, 8516, 92476, 78523, 14672, 19616, 73642, 22588, 12915, 21794, 18299, 4802, 12096, 66558, 82780, 25095, 87621, 30947, 49986, 72978, 94979, 20639, 75603, 96235, 58931, 54598, 25924, 18137, 1014, 82598, 82221, 90822, 54442, 36619, 8051, 42697, 23970, 53125, 23918, 74806, 78229, 837, 5490, 7103, 46145, 94190, 31692, 26648, 24473, 96877, 77322, 98394, 94379, 46320, 46202, 81596, 22938, 74995, 60284, 36217, 24790, 11676, 12193, 79212, 63533, 85698, 69077, 97752, 51817, 69982, 30003, 8839, 43931, 87947, 13588, 21371, 28631, 67186, 98601, 33730, 29049, 6072, 76659, 48402, 46768, 1270, 11516, 99705, 86041, 64968, 85458, 90122, 6996, 70976, 52808, 50913, 51708, 95534, 36764, 477, 67744, 30004, 32330, 90395, 72949, 11254, 19599, 83709, 26029, 91619, 56910, 72812, 982, 45214, 28066, 82627, 79568, 87186, 55518, 14687, 35152, 92882, 32728, 57558, 86403, 45434, 6245, 36149, 4215, 70063, 97394, 6845, 32835, 20188, 76315, 95976, 24532, 96765, 83426, 5666, 75020, 10327, 13418, 83619, 45394, 46457, 33374, 36668, 9387, 71908, 9137, 8264, 60560, 78424, 47990, 17293, 15577, 89528, 6454, 79113, 45955, 34679, 94289, 58121, 45474, 4660, 39479, 20670, 64392, 68491, 65025, 49641, 84871, 84504, 41365, 86977, 41855, 73599, 21366, 71000, 18032, 52400, 69324, 91149, 71352, 69364, 20341, 14035, 27679, 61052, 44007, 65635, 56966, 82488, 8922, 15776, 68927, 15531, 45542, 52888, 55721, 60538, 57247, 15200, 55943, 51713, 60014, 25387, 96945, 81826, 92615, 57305, 76298, 73203, 87452, 85442, 77901, 5114, 74848, 79867, 34505, 54721, 80502, 38502, 24981, 78326, 79428, 92688, 48719, 74654, 36959, 25865, 39707, 96749, 15367, 87506, 22275, 83735, 11585, 91854, 44973, 37299, 60155, 95140, 99647, 35892, 62972, 16401, 64399, 92198, 37027, 16094, 49474, 84613, 98359, 58662, 93304, 67328, 37067, 36385, 18071, 37503, 17362, 47444, 36547, 19660, 35769, 74594, 77749, 51073, 52473, 63256, 43066, 83625, 31547, 42331, 77931, 27884, 43943, 51909, 14653, 54214, 26054, 79160, 23979, 29835, 7764, 28577, 83403, 84980, 93764, 98516, 69813, 53057, 31590, 55382, 66336, 7674, 33009, 65247, 96039, 26674, 95833, 58864, 93660, 60132, 35911, 42227, 6806, 54131, 48022, 54671, 2763, 81213, 41234, 79140, 50918, 81625, 93927, 18402, 32851, 62800, 1931, 42412, 57520, 94288, 93297, 6347, 5375, 86244, 72524, 51488, 37349, 53421, 74119, 96318, 57015, 79245, 5231, 73005, 15496, 21751, 22049, 75096, 80303, 24417, 7207, 21378, 25748, 7648, 11920, 39350, 36156, 4249, 98281, 88209, 40247, 91111, 5700, 84267, 28973, 23926, 90527, 67942, 8154, 29599, 75720, 6123, 11855, 88077, 28007, 24303, 59422, 36395, 14865, 94462, 54522, 80628, 99353, 82760, 91943, 58421, 86224, 98632, 50728, 2489, 38090, 81673, 67077, 75687, 80204, 39379, 76331, 99859, 23349, 83739, 20006, 60270, 39467, 44127, 86384, 79848, 71223, 4619, 99147, 91725, 49110, 14087, 64220, 44234, 11508, 37204, 87156, 50868, 36766, 22129, 40116, 52845, 30478, 66062, 73659, 55209, 84570, 3439, 83931, 60269, 9361, 42190, 59434, 54465, 43258, 38563, 35197, 92498, 42371, 64319, 69069, 91649, 18916, 23625, 49693, 17608, 27188, 73117, 79383, 96678, 21252, 96819, 80140, 12777, 43834, 72695, 13302, 25067, 4160, 75191, 75706, 18216, 42521, 94336, 10159, 42907, 69574, 40954, 37940, 13362, 58852, 59837, 33321, 48186, 32576, 61312, 35059, 58513, 88289, 36838, 10637, 11974, 99977, 69598, 22828, 7570, 45792, 28853, 71628, 98800, 45803, 20401, 7584, 76529, 72596, 91579, 21539, 96673, 92857, 85796, 31884, 55067, 1620, 5792, 42127, 43877, 41869, 61338, 87377, 26933, 82118, 62478, 41420, 72676, 83551, 85640, 45175, 79481, 75581, 99169, 44771, 7587, 19172, 67840, 11297, 27385, 67836, 30287, 77243, 80146, 44349, 31336, 51205, 70765, 47735, 8508, 30362, 9587, 20273, 14541, 85430, 79557, 8340, 51075, 32827, 28513, 91764, 40005, 10381, 13472, 7997, 60835, 63585, 67210, 51889, 56239, 89345, 29730, 71679, 71964, 22918, 86664, 15682, 35643, 25569, 42159, 93635, 17288, 46802, 23290, 51146, 48088, 20967, 10148, 39107, 7705, 55356, 5927, 42085, 47344, 44909, 56393, 23481, 27715, 23188, 59338, 24195, 37355, 35280, 16093, 21217, 60905, 16691, 79273, 8352, 60767, 97817, 45292, 61047, 63673, 20783, 92021, 17277, 28955, 82251, 57207, 10514, 49129, 20514, 69690, 91012, 59848, 38832, 69187, 90336, 89758, 22383, 29803, 54123, 7412, 75714, 26191, 59870, 77670, 32825, 71429, 71978, 34671, 63619, 88400, 26611, 16852, 26444, 10485, 83816, 61686, 22527, 19787, 70300, 41254, 83974, 68336, 66309, 8319, 62157, 53398, 61692, 37398, 20796, 98124, 25435, 5382, 10, 73257, 11932, 90582, 15052, 2253, 56422, 64429, 69912, 76776, 43183, 14770, 90391, 89793, 60935, 13966, 39143, 44499, 52376, 52609, 78006, 20685, 63338, 22115, 63348, 74376, 25884, 65595, 43779, 95699, 99751, 3922, 98024, 45889, 22098, 18298, 54855, 1275, 24627, 1007, 4116, 50034, 27360, 3335, 44586, 25422, 54650, 209, 67547, 4591, 1803, 22509, 90222, 71649, 18773, 56625, 67024, 88574, 99380, 54640, 95208, 57290, 38261, 90197, 67114, 51202, 44652, 5845, 94988, 91423, 2696, 60907, 7204, 69911, 1927, 60998, 13623, 85295, 64192, 77808, 53383, 43284, 68770, 53843, 30260, 15211, 24639, 71411, 41189, 2990, 26538, 96975, 33577, 45140, 57898, 66564, 79679, 92423, 34135, 98138, 37922, 54386, 91458, 33746, 97033, 40547, 25110, 68367, 98022, 73378, 94771, 38683, 46924, 67564, 84456, 29060, 40380, 87714, 2360, 4590, 42686, 24772, 5830, 44288, 73128, 62138, 7049, 72261, 10895, 62479, 31583, 6915, 31490, 8001, 19292, 43019, 42466, 5170, 59048, 94389, 12167, 39837, 38624, 20936, 24184, 16880, 81006, 54591, 6555, 47772, 27245, 26784, 31982, 66255, 35820, 95876, 96917, 23908, 71681, 5967, 66967, 27394, 23443, 38924, 85300, 64337, 28963, 40546, 17962, 22713, 55926, 72789, 46593, 60283, 25527, 60659, 75645, 58160, 98158, 16, 13467, 1342, 39158, 78700, 11788, 13343, 51641, 18369, 6041, 83146, 27999, 28701, 15320, 38230, 69519, 71034, 67304, 13792, 30538, 74270, 64611, 76377, 28944, 23645, 84533, 17260, 93177, 59791, 5065, 30660, 50358, 95046, 31051, 1747, 18663, 91719, 79128, 26330, 46920, 24158, 70891, 35945, 95097, 33496, 80931, 53002, 27696, 50428, 54379, 59189, 37325, 66389, 96062, 23694, 50952, 24309, 77003, 91410, 59644, 29911, 51315, 47154, 36179, 15622, 16199, 57776, 18412, 23302, 98202, 60845, 62070, 65561, 57336, 49586, 86759, 17866, 28140, 22277, 59479, 1494, 84402, 25444, 77284, 15169, 75986, 94845, 16663, 78120, 42487, 81192, 51381, 33514, 74033, 88551, 31227, 24355, 51754, 7291, 26544, 35625, 15308, 30839, 59134, 16295, 58588, 50819, 31665, 3815, 1170, 20389, 39539, 84703, 15340, 30365, 11477, 12320, 9793, 72193, 32260, 25581, 32995, 1171, 78958, 78767, 4986, 54135, 37583, 70967, 31102, 79163, 57235, 55714, 40783, 60766, 3635, 52921, 7533, 81260, 40122, 857, 94965, 50594, 93949, 60660, 72715, 92956, 99250, 59672, 41742, 5518, 46995, 28966, 13664, 65638, 91136, 55500, 75451, 49146, 1233, 18096, 41169, 86185, 29963, 98555, 95525, 26224, 56607, 2027, 62514, 77329, 31615, 51549, 5754, 289, 21995, 9442, 22997, 67761, 87053, 69995, 59168, 7617, 98784, 88165, 54974, 34030, 56199, 9620, 86682, 51085, 63208, 23857, 34386, 19500, 32858, 58159, 60926, 53226, 43748, 81436, 75070, 78714, 25764, 20129, 72218, 3321, 72701, 32142, 21195, 66721, 77084, 31647, 15501, 94021, 65802, 75773, 7782, 40583, 73908, 98797, 13133, 90760, 24083, 90328, 78174, 63336, 60812, 54922, 43193, 13599, 24462, 72603, 77769, 38928, 98769, 45647, 73622, 98689, 2614, 17116, 26237, 97876, 60840, 20343, 52986, 44490, 27536, 87007, 56011, 22889, 99608, 51193, 99641, 67013, 26065, 81444, 8874, 71806, 91158, 90544, 20787, 26498, 82325, 5532, 21840, 51801, 80164, 98269, 8575, 57531, 34076, 22792, 18401, 59445, 17939, 59283, 30778, 25064, 45594, 17813, 89220, 55167, 70279, 52164, 1928, 95409, 27357, 39693, 51628, 35188, 34906, 83219, 72367, 44965, 90749, 51871, 56642, 68051, 49125, 26287, 57355, 385, 85981, 58919, 6150, 3551, 83530, 42321, 93374, 28109, 14610, 37553, 24081, 21753, 73050, 17472, 71341, 72198, 63549, 83570, 56211, 46190, 82156, 85936, 53115, 65903, 70388, 4421, 13256, 23828, 60479, 93766, 54155, 61446, 25968, 50784, 40609, 58691, 93714, 70326, 101, 1060, 44551, 69781, 9575, 14589, 75073, 90871, 35336, 53096, 42809, 55718, 13313, 15392, 63401, 44365, 547, 2007, 60104, 33197, 48710, 87252, 44951, 14049, 11591, 24370, 58148, 33488, 56754, 29618, 99678, 59278, 22427, 83812, 19972, 56960, 91775, 82414, 27136, 14820, 76007, 67980, 9694, 62313, 57204, 84725, 86872, 15961, 27699, 27424, 74460, 97478, 84180, 53789, 11688, 33104, 95009, 28396, 91466, 64576, 17560, 87678, 42307, 81347, 64731, 36345, 82391, 92847, 1455, 60288, 63887, 43635, 88248, 30408, 56380, 44108, 82383, 27894, 53814, 18850, 29447, 77273, 59512, 82746, 61725, 85128, 22468, 80004, 17305, 9421, 72375, 87706, 22920, 77148, 22914, 54556, 10319, 26035, 55273, 81372, 66339, 21635, 6261, 88169, 34515, 47553, 40820, 26363, 25842, 2474, 76180, 43430, 8899, 85174, 38089, 24407, 6205, 22355, 62344, 24193, 59192, 20809, 26322, 98095, 1331, 21386, 58463, 53821, 7034, 83147, 55471, 42385, 69278, 39668, 230, 44836, 22520, 64159, 83186, 23000, 61231, 55489, 46561, 90049, 43897, 67216, 5315, 35859, 86157, 23427, 86519, 7271, 72158, 67355, 63797, 97692, 65736, 76120, 61254, 63636, 35847, 61419, 59346, 88114, 62881, 66200, 96135, 28606, 5701, 37633, 68432, 7822, 63381, 69207, 93782, 64358, 38259, 30896, 5433, 28685, 24501, 16711, 8281, 58251, 96376, 60500, 80471, 39138, 75498, 90976, 80617, 17354, 93045, 418, 42539, 29373, 18642, 34004, 1115, 18683, 91083, 60287, 43046, 85045, 27256, 48303, 29465, 75520, 77173, 35717, 99367, 84737, 73022, 1839, 97662, 52016, 94902, 75057, 50315, 85311, 50615, 52042, 51714, 82799, 36277, 34539, 15683, 30181, 25040, 84228, 67196, 6547, 7441, 2449, 39395, 56811, 26987, 55534, 8229, 52436, 13807, 71215, 493, 51601, 6442, 99909, 13719, 21224, 74251, 35784, 52840, 88333, 67372, 1365, 79130, 63275, 74680, 10221, 84923, 34755, 81327, 67502, 82138, 73743, 45808, 53966, 67178, 46114, 24852, 37669, 54356, 37138, 85341, 85656, 970, 82480, 17687, 63965, 86848, 67341, 62695, 77832, 57806, 71743, 38491, 43929, 34942, 95586, 2122, 12752, 96445, 37714, 40923, 41982, 11949, 97808, 88902, 11683, 92750, 70414, 50388, 78989, 21088, 18611, 79660, 32336, 17173, 27018, 92889, 55912, 8806, 79511, 58676, 827, 34102, 80824, 55216, 87575, 29741, 11178, 41045, 63183, 18033, 52738, 59248, 8468, 65864, 29287, 63037, 27055, 32073, 66616, 92788, 590, 41558, 28785, 62199, 85036, 14481, 57663, 33946, 56614, 71661, 24379, 2533, 39273, 19800, 58178, 82949, 4290, 21979, 80401, 74491, 58974, 44692, 75063, 50354, 94685, 56999, 49025, 88144, 61592, 880, 79371, 63496, 48390, 5164, 35399, 30833, 69875, 93622, 44932, 10017, 12998, 93737, 11495, 32783, 92190, 86336, 21812, 31822, 29706, 51412, 67075, 68073, 65893, 93594, 92332, 33833, 64111, 6603, 17270, 72690, 82432, 11175, 94626, 80386, 88241, 98356, 56865, 52602, 5988, 87248, 63610, 46845, 68393, 53974, 27384, 52891, 34458, 73141, 18703, 97794, 24111, 67880, 81589, 20551, 93154, 40589, 36417, 92189, 57775, 26961, 77346, 26643, 67401, 86676, 87040, 64369, 8671, 64758, 69819, 87666, 71866, 89641, 51935, 84524, 54761, 17875, 81843, 92413, 47585, 73059, 507, 41073, 69305, 47924, 75524, 83643, 62887, 25063, 84098, 62764, 9038, 3869, 64298, 65152, 54238, 70454, 22036, 51225, 50495, 19034, 53193, 26663, 34278, 64214, 88151, 74578, 46196, 25608, 55846, 95158, 52114, 21309, 84105, 18582, 36036, 90754, 7118, 74503, 66593, 73357, 33617, 88200, 91120, 42691, 1151, 48800, 25227, 76268, 21662, 79941, 50938, 17477, 9898, 5500, 74236, 13761, 87127, 44294, 15753, 50775, 80426, 7109, 18877, 35931, 25805, 66328, 51639, 10722, 71038, 57551, 39355, 75868, 18827, 80849, 88271, 64234, 67006, 43894, 67851, 8304, 45745, 7037, 91593, 81393, 25978, 92508, 78825, 95314, 9006, 93924, 37412, 28157, 22187, 8316, 39297, 35349, 19222, 25020, 87138, 68653, 35741, 66157, 63330, 81309, 59457, 31397, 80078, 54915, 68626, 67527, 50544, 96935, 41156, 79851, 62282, 18351, 54572, 86829, 82798, 11598, 76518, 74575, 15912, 581, 21234, 92894, 26422, 53433, 50229, 21071, 41089, 87908, 46962, 59787, 87179, 30747, 35536, 65004, 23698, 74147, 52742, 74536, 57597, 33760, 31970, 89554, 26270, 69618, 78459, 28073, 56858, 97636, 5596, 92346, 38715, 70869, 54095, 30248, 94234, 35159, 84310, 18161, 11997, 85653, 38551, 85671, 59022, 33297, 2213, 2724, 77692, 35872, 44535, 60043, 98888, 73687, 60034, 93173, 91676, 81305, 63931, 54927, 54341, 69246, 66567, 2709, 4577, 73903, 47419, 71176, 1169, 25831, 40004, 24766, 97052, 54665, 33199, 9117, 13485, 92723, 96902, 94058, 18788, 76812, 98830, 40652, 76372, 59667, 56468, 6112, 82313, 39649, 13806, 49681, 29057, 83010, 67155, 15629, 28548, 12485, 94334, 81692, 6022, 42148, 24623, 60060, 93279, 38607, 59246, 23535, 79298, 20797, 13299, 97051, 42837, 85457, 2389, 96913, 47052, 46554, 1735, 13066, 13123, 45091, 25666, 8414, 97027, 92983, 52422, 5144, 97672, 82689, 23421, 24909, 25818, 81817, 79544, 59555, 24865, 74371, 58190, 11052, 83368, 91084, 36843, 33910, 50434, 68171, 19712, 41066, 21488, 27438, 21899, 41113, 48949, 16263, 64436, 805, 96762, 82416, 79923, 22043, 74572, 10877, 62471, 45127, 50633, 69721, 10051, 4329, 58267, 98978, 528, 12929, 5871, 67286, 23881, 63836, 45963, 97167, 42943, 96136, 39523, 19670, 56808, 45502, 88423, 91688, 3364, 29626, 95612, 31072, 44271, 35471, 59498, 10836, 47859, 10144, 90257, 76450, 13735, 17754, 95008, 80003, 53044, 694, 60359, 19385, 86951, 82574, 75670, 62522, 46084, 89446, 69255, 89222, 68344, 55045, 43194, 48439, 72094, 12688, 6918, 12513, 31111, 67545, 83836, 99852, 17534, 4269, 64851, 27986, 96247, 23558, 7700, 87389, 12848, 40343, 37933, 41476, 6777, 32025, 18281, 84368, 33573, 70206, 86917, 17673, 60968, 54623, 71076, 8408, 19847, 12383, 19081, 70870, 98738, 51148, 39049, 75248, 96844, 35690, 44422, 58992, 34088, 5506, 90156, 30195, 46993, 57124, 49940, 7605, 17052, 21642, 22689, 7797, 47330, 2935, 78869, 33845, 93977, 78168, 7256, 26517, 28075, 60764, 52740, 10293, 81699, 23146, 61701, 50696, 86343, 68807, 52182, 98246, 74789, 48398, 67550, 54448, 36642, 9042, 15773, 63373, 79730, 53401, 4420, 62353, 18753, 30759, 81731, 41462, 30623, 42958, 72621, 85461, 32540, 17457, 61039, 86967, 68976, 35311, 47872, 79424, 56091, 99141, 96394, 80418, 26019, 35525, 40397, 56737, 15636, 56002, 3440, 99626, 61955, 91486, 42898, 47225, 53755, 82013, 84733, 13678, 93215, 36577, 82134, 47622, 97549, 70385, 86587, 78823, 53720, 91392, 86834, 29867, 94729, 23747, 96211, 93236, 67755, 42660, 47782, 81317, 3380, 16995, 61613, 80480, 44908, 22968, 43624, 58278, 12022, 25274, 12693, 74208, 69095, 83845, 84324, 75333, 80695, 87708, 11080, 76089, 70695, 95221, 80268, 53145, 2951, 8307, 83766, 35940, 40910, 43271, 29188, 40991, 28033, 76555, 94399, 89708, 77888, 53381, 45213, 96981, 13635, 84338, 92301, 71230, 50467, 46722, 17917, 36076, 45613, 78491, 70160, 50741, 37985, 41115, 88580, 65452, 29794, 33162, 2409, 32234, 9543, 57900, 2994, 45927, 37565, 25443, 21037, 2085, 71763, 78928, 50119, 26381, 36570, 96835, 60864, 3552, 48972, 68175, 50793, 46728, 63449, 69370, 30200, 46044, 4151, 45756, 20841, 24552, 63278, 10544, 43068, 68286, 17652, 84255, 63433, 46110, 83937, 68599, 4686, 3604, 60139, 79540, 61635, 6137, 32984, 94640, 53593, 88504, 69868, 6700, 94320, 66004, 5802, 29861, 74764, 33874, 26081, 45176, 2114, 68659, 78297, 45468, 48648, 15144, 20601, 59871, 48471, 51473, 20264, 62751, 88446, 93166, 51497, 25729, 81529, 9498, 80677, 35635, 58971, 47588, 76592, 58958, 22637, 84471, 37521, 86427, 83531, 20012, 75231, 86926, 84603, 11205, 85275, 22160, 29035, 60266, 53374, 94013, 54696, 86620, 16489, 7065, 92776, 8318, 9599, 49866, 37539, 46740, 79951, 88654, 83266, 6075, 89467, 45184, 73799, 30551, 8556, 2071, 98789, 39278, 52970, 18073, 96789, 21999, 34238, 83556, 1066, 32001, 32684, 50236, 28713, 13239, 8881, 62851, 26654, 19578, 41224, 2844, 5341, 30540, 86467, 25518, 50815, 18972, 20486, 17273, 82875, 14555, 75580, 52089, 21570, 396, 59585, 86037, 709, 30044, 66357, 11407, 85545, 8722, 99750, 73639, 65069, 68682, 99943, 738, 66699, 37682, 91880, 5162, 90365, 10541, 86138, 48414, 15548, 19392, 92748, 74879, 35750, 40338, 86765, 1573, 75993, 67672, 74113, 92323, 9057, 25890, 72507, 41884, 92375, 32589, 91852, 54627, 98186, 3782, 37442, 78570, 70920, 51768, 91119, 47969, 82222, 2438, 90078, 26010, 74133, 49037, 38152, 24652, 89441, 47253, 32669, 1845, 49547, 23229, 77620, 14347, 81855, 41668, 71680, 30175, 69808, 84407, 85405, 80654, 9096, 57784, 70572, 61212, 45249, 95249, 80732, 28237, 33363, 93071, 2806, 14022, 1672, 12802, 43496, 37988, 36931, 45590, 2008, 92652, 10127, 41659, 94880, 41341, 71957, 6417, 84482, 8000, 14924, 24664, 38383, 18316, 48966, 36860, 68693, 47421, 74183, 29295, 67860, 1347, 39306, 34285, 59565, 93062, 85247, 39614, 98609, 72860, 36880, 15072, 77693, 1508, 74196, 54629, 85816, 12904, 21946, 77112, 52924, 53372, 11988, 55300, 18436, 71244, 88449, 46650, 13145, 79850, 1613, 12420, 77795, 41228, 499, 11853, 34327, 12495, 37389, 54728, 89877, 6114, 61995, 2277, 22548, 52044, 33726, 10608, 4311, 99207, 37057, 27898, 21716, 82227, 21092, 12670, 96985, 18905, 59753, 55768, 58509, 87550, 31451, 5033, 25091, 89493, 92899, 48768, 17383, 53851, 74795, 69244, 5060, 98122, 1248, 93476, 76252, 41279, 16200, 73284, 77411, 18950, 80317, 12580, 13039, 74863, 81090, 54281, 31971, 71778, 99181, 71432, 43150, 82788, 1087, 46679, 50131, 16107, 69806, 70606, 19534, 67305, 74424, 339, 2699, 2391, 25626, 59310, 50609, 13745, 25926, 56243, 65984, 79121, 21442, 74254, 93048, 97595, 73882, 99652, 23255, 78757, 37079, 25710, 4780, 16782, 69031, 87107, 50035, 86291, 96002, 80456, 13322, 6937, 11867, 77659, 94166, 66413, 12367, 60443, 96041, 33968, 72557, 92471, 17855, 54925, 39458, 27960, 20295, 55308, 93894, 49133, 85158, 71099, 18271, 67504, 42363, 17089, 34202, 1316, 88626, 29607, 24251, 73382, 53936, 99220, 14482, 25078, 44117, 35790, 42632, 98973, 4033, 78170, 35560, 54527, 75936, 89811, 51027, 45710, 26710, 470, 21837, 21947, 42301, 16466, 5513, 90001, 46831, 10813, 95519, 86683, 17024, 3388, 78686, 95021, 17746, 2377, 20898, 6725, 60504, 47869, 43128, 47063, 67584, 71558, 74344, 80523, 40596, 64505, 92796, 35198, 98299, 33481, 25001, 57170, 20263, 89551, 96262, 12672, 71372, 33779, 47286, 22108, 573, 42902, 48557, 45637, 93132, 96621, 14220, 78420, 85469, 15171, 15563, 48371, 18786, 38147, 3361, 2186, 27643, 25815, 77473, 29821, 55020, 55544, 30794, 99286, 50843, 84972, 86201, 17482, 40838, 64427, 59036, 32615, 96984, 58943, 99455, 57830, 63340, 43411, 82917, 67342, 66696, 62337, 39362, 97557, 93612, 90171, 25931, 32530, 34246, 19955, 58280, 25210, 29811, 12730, 9864, 2899, 80500, 52433, 59495, 83384, 24787, 53060, 57102, 9851, 62036, 45424, 26197, 41214, 88966, 3195, 99863, 86970, 53511, 2730, 9441, 14262, 98375, 12138, 54301, 13084, 16911, 97195, 3541, 32979, 9231, 53384, 23572, 50974, 63430, 97892, 6178, 99400, 29696, 40427, 27808, 57560, 83678, 33616, 73177, 59169, 2331, 85103, 82351, 86417, 47375, 38299, 78253, 32144, 16726, 69137, 24842, 30332, 52804, 41210, 56946, 71540, 79939, 11424, 20953, 81687, 61791, 33816, 58044, 15975, 56338, 42252, 57150, 69448, 58752, 98822, 88384, 62853, 16301, 83892, 58470, 39110, 97422, 31641, 2083, 87564, 75569, 63456, 99221, 60936, 99186, 83170, 5225, 52958, 6023, 36823, 74635, 18354, 56668, 76660, 81690, 14484, 12533, 81564, 3096, 12549, 62957, 21158, 97738, 20548, 49298, 6253, 50934, 8130, 41595, 35659, 6659, 2650, 75445, 46302, 10820, 4785, 54033, 48870, 87049, 91554, 78337, 17008, 23530, 10062, 22636, 54685, 77816, 11267, 15694, 48271, 93582, 36055, 35628, 80158, 83183, 36760, 59405, 85471, 1478, 38462, 2565, 29451, 13330, 19625, 66613, 15370, 96710, 31898, 63047, 68062, 48389, 70868, 67363, 83659, 86533, 59601, 76722, 75845, 80848, 47987, 24120, 52842, 51174, 19851, 82213, 80890, 12166, 49451, 40276, 15298, 1800, 88767, 84178, 670, 23089, 74761, 70231, 22543, 40456, 99249, 7989, 88798, 51685, 52119, 87062, 82528, 89242, 49981, 52725, 2988, 87278, 9145, 49795, 75103, 69200, 21935, 75963, 20243, 87546, 97981, 40952, 97591, 50746, 18282, 60617, 99124, 24859, 24892, 80277, 87949, 21045, 57478, 42896, 33536, 8591, 54014, 94273, 41589, 13188, 22633, 44317, 59897, 86275, 74496, 52679, 34140, 48976, 47151, 40492, 70683, 50752, 4556, 40187, 28506, 66291, 11498, 84876, 90440, 17194, 13612, 31360, 80254, 43307, 42403, 23786, 8475, 49648, 89731, 10118, 1547, 12097, 91533, 31588, 8691, 29728, 32881, 98754, 33059, 55990, 56774, 57408, 22610, 65515, 75185, 5143, 67721, 63860, 8127, 56014, 28993, 4627, 70573, 25566, 97276, 1514, 84618, 32344, 87598, 58887, 60927, 60141, 40757, 45138, 91819, 11978, 90449, 27144, 39338, 88463, 93148, 90670, 28968, 49598, 85223, 59682, 46170, 66214, 22642, 42435, 76428, 8894, 5447, 3410, 21426, 70517, 27486, 4745, 73663, 95994, 33097, 46311, 71200, 63513, 90146, 17641, 94550, 4476, 46198, 27397, 45375, 92570, 77469, 44396, 88974, 36729, 89876, 65712, 96268, 94467, 78055, 73910, 99846, 49543, 65410, 4385, 41030, 76122, 14510, 88707, 44899, 24896, 3863, 53350, 94473, 7511, 10240, 66150, 25708, 50157, 39397, 16391, 84260, 19495, 59314, 97100, 26260, 62461, 49840, 35657, 85345, 23301, 83979, 31176, 66953, 75000, 32636, 67408, 62902, 15789, 92667, 27403, 35531, 59883, 97572, 64797, 81645, 7186, 93962, 6983, 38645, 61734, 54026, 53449, 30618, 67711, 88121, 49101, 95567, 57922, 3148, 93744, 91709, 44574, 91184, 66580, 9894, 63107, 62958, 82624, 95928, 62765, 7520, 44022, 30931, 25401, 48892, 20891, 10601, 39511, 15329, 77837, 9178, 6120, 30445, 99339, 17840, 31448, 25632, 27412, 94671, 2912, 30396, 1844, 34885, 98739, 65198, 99217, 80943, 52758, 5220, 65778, 42217, 58253, 99955, 22392, 95421, 58120, 57480, 52596, 61201, 17423, 19726, 16576, 67169, 30546, 99908, 92768, 18583, 14673, 91907, 53339, 89288, 3102, 74202, 44657, 89782, 65353, 16727, 68503, 45475, 37528, 6761, 81566, 22848, 37193, 82132, 74545, 71116, 32397, 40428, 22875, 94014, 88203, 10306, 97924, 96434, 52084, 72467, 20955, 53727, 88971, 17104, 51874, 90619, 90456, 58174, 46413, 10809, 68524, 64939, 80316, 87265, 32828, 1741, 99168, 38973, 47113, 28500, 62596, 99858, 10801, 50101, 55137, 35848, 9635, 35028, 77831, 51604, 83798, 1636, 53387, 25072, 70674, 8952, 7628, 25594, 93682, 10700, 86295, 64875, 72663, 88156, 43235, 89380, 28427, 1608, 70159, 36370, 85942, 84575, 18606, 9292, 23228, 74573, 1930, 90950, 37634, 14944, 74110, 12733, 99922, 97265, 92436, 84843, 91920, 65558, 64151, 16978, 62111, 22267, 50065, 94996, 64983, 54565, 11791, 70343, 92550, 40890, 50284, 89229, 47632, 32161, 10261, 1851, 51718, 31603, 18671, 40281, 78625, 97873, 62492, 98698, 94239, 52113, 21501, 71423, 10283, 40135, 26303, 6765, 6211, 10531, 8463, 7403, 16866, 16912, 24996, 30564, 12615, 59064, 24498, 95316, 16898, 96189, 39067, 6456, 89153, 55528, 20933, 66379, 99417, 18732, 17657, 11644, 43533, 84209, 18647, 90243, 4045, 50552, 65352, 52689, 12776, 86657, 75168, 85022, 61883, 22547, 9836, 72504, 77211, 66163, 35778, 24357, 96437, 99465, 40102, 17972, 50640, 76967, 97053, 92676, 76440, 92292, 25977, 71673, 72084, 11871, 69678, 94549, 83113, 50223, 79368, 43403, 70317, 49733, 73062, 69275, 18458, 12583, 5807, 28706, 52669, 15443, 90692, 100000, 85947, 63932, 84311, 97267, 46701, 66321, 60584, 40685, 12567, 96283, 39052, 34594, 75084, 79640, 46363, 34805, 81866, 13272, 41640, 16468, 48317, 18247, 30585, 39815, 73762, 84459, 80788, 2084, 92025, 62569, 7966, 26453, 48569, 14546, 55935, 90241, 62702, 54551, 52475, 30647, 89735, 44415, 80972, 22003, 95774, 55272, 16869, 42961, 95594, 43766, 31415, 38731, 57863, 59843, 5389, 56908, 79854, 40284, 8947, 25951, 79653, 63114, 73513, 30953, 52366, 24800, 73815, 98047, 17631, 14298, 40418, 37211, 92604, 39757, 31893, 21917, 46648, 22630, 93601, 42258, 19694, 80702, 74580, 42260, 65960, 29742, 38614, 10109, 64579, 93098, 51060, 29236, 2982, 76865, 64448, 6906, 72598, 27621, 13705, 51399, 21907, 39704, 11850, 58924, 87167, 48907, 31085, 45857, 5954, 59569, 84064, 74206, 60591, 27138, 59321, 83601, 28872, 1797, 79408, 85206, 57996, 39922, 55270, 12446, 84054, 94895, 27762, 25782, 76516, 64648, 97059, 80667, 22927, 88712, 2370, 90261, 9062, 1965, 39243, 22222, 28092, 54399, 83242, 29817, 11121, 56425, 36783, 1638, 21955, 1708, 61021, 5030, 31735, 69515, 3131, 93429, 32806, 18501, 99849, 34905, 25215, 29981, 88410, 63717, 62863, 66162, 24428, 19938, 98646, 85506, 31089, 85531, 8601, 5544, 18042, 49897, 99663, 81837, 6514, 54514, 53409, 91973, 85777, 76541, 37592, 91546, 63240, 59946, 61665, 54252, 68912, 87305, 29597, 34941, 83929, 76075, 4693, 10424, 41316, 80247, 50620, 8365, 99660, 22401, 64923, 43219, 12399, 84670, 18932, 52421, 75165, 4229, 49487, 78646, 6706, 65257, 33443, 57968, 1434, 19933, 72640, 11137, 92706, 68277, 48770, 37841, 67162, 91118, 49711, 86994, 83906, 93727, 49279, 80940, 81350, 5323, 4383, 79466, 99214, 65897, 41176, 33131, 96305, 89117, 45919, 46188, 95080, 17473, 51177, 85462, 40884, 99828, 31874, 48645, 65920, 1484, 30919, 67568, 14947, 21554, 52343, 47832, 38173, 24843, 22465, 77466, 99779, 40458, 90863, 47951, 16905, 65240, 35452, 31654, 63416, 94784, 1850, 28403, 90860, 61220, 96132, 33085, 55073, 82524, 72847, 59242, 36330, 64142, 35226, 45706, 30456, 79169, 62701, 97166, 54515, 18378, 16298, 30509, 82801, 78555, 64019, 95479, 22194, 8002, 81233, 36220, 15760, 54502, 50735, 77190, 85541, 30860, 3601, 72003, 44100, 51602, 97413, 81458, 21713, 1165, 73103, 92127, 47029, 43040, 29514, 28778, 18997, 82953, 95127, 57764, 45946, 1078, 26259, 80671, 3881, 19786, 1175, 89644, 62512, 16116, 59381, 96631, 41507, 61517, 20628, 66208, 37579, 69306, 95329, 26656, 53342, 55913, 72956, 35623, 42982, 12650, 44173, 54622, 57816, 96664, 24618, 47488, 40849, 40706, 15886, 23093, 1909, 26718, 70237, 7384, 8896, 91023, 5827, 67290, 8625, 50982, 6544, 83466, 84464, 63970, 32444, 56269, 36616, 23803, 96003, 32687, 20451, 13102, 80674, 70637, 41484, 35234, 45597, 85507, 13391, 41146, 12687, 17308, 87675, 51996, 78807, 21206, 62825, 40099, 86655, 17654, 16827, 66242, 17002, 62553, 32744, 44600, 66744, 96386, 89010, 31792, 42253, 82907, 78137, 46424, 3145, 88390, 27759, 40751, 58703, 6849, 32028, 73244, 46538, 23821, 71321, 6418, 60030, 31212, 20961, 77963, 78708, 47854, 18358, 77971, 11820, 35632, 87780, 90455, 47874, 11022, 27328, 4020, 4425, 36260, 10777, 4065, 74990, 94100, 21706, 75267, 40569, 22149, 9358, 78287, 36884, 93202, 63480, 99032, 36057, 7112, 71179, 61698, 30278, 52188, 13028, 65516, 59090, 40163, 11619, 65690, 76005, 24690, 60942, 28268, 72754, 30083, 18589, 75840, 12563, 52551, 86816, 10121, 77956, 90359, 18976, 44459, 72670, 75779, 48304, 98638, 80952, 19691, 69879, 14002, 41446, 25137, 74158, 46678, 36028, 42901, 94842, 65292, 85574, 37851, 53808, 63291, 83624, 77653, 9581, 2272, 73510, 81517, 49676, 4326, 9953, 68117, 72233, 86280, 57590, 67682, 11776, 30457, 39196, 54543, 19581, 26000, 30982, 91736, 97846, 19183, 38286, 67709, 59523, 24661, 62752, 89597, 81049, 14738, 39257, 25281, 53680, 64867, 58696, 58643, 85170, 2969, 9153, 11893, 57910, 90842, 92962, 17876, 37838, 92691, 1289, 16574, 89011, 13149, 81460, 33884, 82656, 37010, 73405, 16042, 5632, 27166, 90200, 9371, 8118, 79905, 48149, 51895, 45666, 44597, 64245, 70591, 25342, 8380, 96846, 69602, 74882, 11701, 5501, 71095, 68405, 38391, 2905, 25379, 80552, 72475, 57320, 86385, 34281, 1269, 7542, 82490, 60392, 91326, 34923, 624, 61646, 98363, 72342, 76072, 5140, 92063, 51263, 97929, 86448, 6829, 61817, 79338, 64075, 73013, 85598, 58893, 55387, 97080, 91385, 11347, 43832, 96926, 36813, 32533, 59275, 42367, 17984, 95302, 45233, 72488, 77225, 1395, 41079, 50001, 14066, 9458, 56804, 49778, 98939, 64907, 16145, 66878, 59557, 30165, 47636, 51828, 67164, 90303, 46436, 42508, 42422, 49523, 58875, 48406, 92043, 30978, 94301, 47991, 79238, 40680, 14760, 76603, 57561, 13492, 30086, 35835, 43247, 5576, 58925, 5272, 18676, 38885, 28675, 495, 30005, 43148, 59812, 44958, 84204, 38165, 34794, 56478, 47981, 35650, 94148, 61647, 73857, 2619, 88048, 81469, 64798, 80887, 64089, 27692, 81608, 2180, 88300, 54191, 33758, 37309, 68407, 77209, 58323, 68049, 29897, 45038, 70800, 459, 1510, 16063, 53181, 80625, 89160, 16183, 35992, 6259, 14279, 1190, 19508, 15077, 27082, 71697, 67895, 61945, 48323, 79630, 58526, 52588, 23551, 7222, 29640, 21187, 8583, 29216, 84041, 21133, 36369, 98405, 74666, 44366, 68704, 63973, 80027, 23636, 74698, 9861, 25598, 38074, 5685, 56700, 98422, 94477, 25870, 92795, 8924, 55905, 73809, 85031, 90459, 10537, 89840, 43883, 34749, 46057, 66853, 58176, 80352, 69418, 40586, 96832, 93024, 47778, 64655, 65970, 20839, 52041, 44556, 37353, 97199, 26179, 36100, 60468, 51925, 15642, 34011, 75163, 81777, 30570, 18426, 1196, 19466, 89371, 33870, 91313, 54449, 76850, 82852, 8153, 90088, 24286, 25366, 57942, 2930, 15067, 20146, 2054, 75105, 44008, 23893, 58772, 76311, 5319, 1686, 10710, 32274, 40179, 62285, 98742, 78565, 43440, 90721, 40295, 76881, 91512, 83025, 70023, 771, 22937, 10860, 95957, 25438, 93767, 29944, 91175, 95151, 59302, 35214, 77784, 36589, 17665, 17417, 75006, 65220, 40095, 95039, 32543, 68891, 76669, 54149, 69648, 218, 14025, 91620, 25737, 76182, 3028, 21722, 55368, 77830, 59349, 36019, 89120, 86958, 82183, 20993, 65534, 79570, 87547, 87371, 84295, 56472, 91891, 20138, 86033, 82843, 26408, 83198, 53301, 65151, 84715, 1992, 46237, 574, 98051, 92015, 44853, 68637, 18572, 53346, 93721, 77651, 48038, 63746, 63577, 82610, 55973, 90422, 71544, 53751, 73290, 11561, 34397, 37602, 51088, 64144, 89519, 4998, 40382, 91169, 50768, 91210, 62680, 87497, 86312, 70234, 31780, 21788, 50033, 86106, 5778, 85975, 9439, 27326, 60100, 94760, 64871, 40956, 26627, 46947, 82555, 88962, 89071, 34590, 7762, 69036, 46576, 63427, 14885, 21574, 75405, 46428, 68950, 38809, 66484, 6221, 56473, 32651, 43142, 78975, 73252, 80440, 93718, 38892, 83182, 65279, 98981, 52971, 39781, 60216, 77150, 53184, 43592, 75303, 42163, 1417, 30755, 95004, 32200, 31592, 22653, 86044, 50222, 42334, 53719, 18665, 59912, 99263, 47663, 12075, 33527, 75929, 19267, 91622, 61573, 62915, 94280, 8242, 45622, 65523, 46430, 30720, 38720, 56825, 41127, 35975, 20196, 99431, 93751, 85111, 30310, 15041, 91759, 17817, 77286, 4960, 54871, 49754, 6515, 64391, 99260, 34358, 39060, 31557, 18672, 30008, 41850, 89078, 58952, 96880, 97297, 35350, 62561, 50196, 79473, 32960, 35745, 89539, 31037, 98259, 24717, 37827, 93499, 84056, 79263, 81965, 46240, 98194, 9191, 8658, 10853, 78069, 3406, 6656, 38866, 57262, 64759, 18833, 59596, 13338, 97959, 4907, 52348, 29768, 45577, 37278, 7398, 73761, 26508, 5106, 88588, 14906, 93306, 91170, 9525, 77549, 20369, 80192, 93626, 7823, 42629, 72232, 55930, 77707, 62738, 83223, 87149, 83785, 91337, 13163, 53302, 21103, 47741, 63963, 65262, 45033, 66205, 89591, 43686, 73114, 57251, 4957, 73109, 16738, 87784, 65539, 27322, 48754, 35681, 90857, 17124, 65734, 10634, 37183, 46364, 98621, 67853, 1387, 14727, 2143, 92822, 26919, 49571, 35031, 83926, 67523, 54773, 61594, 21647, 33856, 21042, 43401, 51457, 97029, 52486, 29066, 49098, 66190, 3457, 71418, 57555, 19609, 96982, 81032, 19577, 2326, 15276, 68970, 68259, 11430, 40329, 95740, 21796, 36290, 73780, 75323, 62609, 56695, 56426, 79861, 65199, 87221, 43971, 87517, 35617, 7721, 37995, 91000, 45462, 5394, 34987, 86225, 23277, 97916, 75483, 7974, 76417, 43256, 19864, 49750, 54332, 28232, 52799, 9683, 66487, 11965, 15558, 76135, 29291, 92973, 88416, 26576, 13666, 43173, 43558, 44264, 71209, 32452, 15885, 20332, 88204, 87638, 56280, 7512, 99332, 61210, 556, 97428, 679, 81863, 71231, 52176, 62933, 20301, 59461, 4168, 36871, 54456, 99340, 79070, 61875, 37200, 34744, 43547, 93371, 98457, 83444, 37759, 38996, 34435, 64899, 72332, 90329, 57296, 15205, 91611, 74497, 66615, 96439, 20236, 86255, 62177, 74883, 52649, 93199, 75283, 41929, 59404, 42614, 27348, 78838, 52527, 11225, 59768, 91361, 76619, 40519, 44492, 79823, 78639, 2783, 26772, 84710, 806, 96365, 76936, 58255, 35735, 67451, 74498, 60833, 76107, 40275, 22747, 54680, 6923, 51149, 22200, 8385, 49179, 39858, 61780, 29827, 28121, 94901, 39036, 42075, 32464, 43621, 19608, 17618, 45560, 38964, 1816, 81414, 66672, 89317, 12003, 44052, 654, 39638, 55633, 37486, 43444, 71835, 29310, 41882, 98884, 93255, 20120, 71474, 45632, 39431, 40770, 85802, 26299, 12569, 69375, 32063, 16924, 78837, 18200, 95110, 98196, 98663, 6920, 39600, 45890, 42641, 6286, 20041, 20202, 85775, 68830, 49862, 56303, 329, 18882, 40815, 24253, 99752, 78675, 29540, 59402, 49749, 27162, 34347, 87837, 47461, 80672, 13685, 56200, 27347, 21555, 95216, 91675, 73559, 44533, 7242, 37341, 12859, 58934, 69780, 60285, 71510, 84085, 83015, 39390, 49726, 80378, 29674, 2198, 43314, 29719, 40104, 36538, 33113, 78265, 22996, 39799, 26468, 1321, 91755, 30869, 84141, 38609, 83449, 81800, 2099, 32154, 52941, 13925, 78484, 18472, 18628, 3326, 16657, 96778, 25654, 57153, 6380, 72499, 9580, 21357, 6623, 12042, 12646, 49486, 94897, 39877, 40611, 49182, 35104, 16388, 87327, 92801, 31744, 9559, 79232, 36074, 76624, 95073, 33417, 45001, 97783, 7191, 63239, 22264, 7710, 72559, 8577, 84466, 26957, 92679, 23892, 68439, 82639, 3848, 93853, 26637, 46047, 99960, 76956, 68291, 65122, 8509, 16609, 44003, 3783, 83560, 62511, 66586, 8315, 58413, 78828, 81076, 86671, 63569, 84438, 185, 22054, 88572, 60933, 52861, 92065, 33090, 46587, 90525, 6661, 22871, 62552, 20457, 25575, 67731, 82952, 46776, 88577, 8425, 71880, 9848, 66653, 60756, 64040, 78106, 19605, 68743, 6654, 79026, 19727, 9479, 54821, 65092, 51374, 81251, 30087, 33144, 41482, 25170, 96875, 96833, 45933, 9395, 30620, 9112, 29723, 4787, 63843, 4588, 37526, 29762, 66611, 48333, 81247, 22213, 8163, 11389, 36691, 41053, 22271, 65863, 75642, 66720, 63273, 99265, 29988, 72442, 5628, 36532, 1251, 28012, 40928, 64575, 87260, 9329, 65475, 22061, 90620, 98313, 43684, 41647, 8846, 50318, 4740, 59074, 66099, 97770, 38550, 6729, 85282, 49191, 9477, 65709, 44171, 96299, 116, 11935, 67168, 63850, 27236, 75293, 34788, 23150, 86988, 23682, 86172, 89162, 76314, 38271, 80412, 57035, 9211, 31791, 1450, 6743, 84129, 40806, 81957, 7955, 94571, 49092, 75368, 1458, 72360, 27514, 68388, 56381, 56405, 28080, 13247, 24201, 80019, 78116, 71997, 15183, 47473, 78426, 414, 26586, 18346, 32831, 78017, 57317, 23538, 90363, 22179, 84207, 41607, 9524, 3533, 77996, 51141, 17825, 83881, 62201, 45759, 61324, 5194, 45891, 61990, 75507, 72207, 83344, 551, 87625, 97224, 41584, 13796, 72873, 30710, 90312, 88983, 22205, 13844, 89584, 20352, 31710, 20746, 6247, 31788, 84372, 90503, 96045, 67912, 69752, 20032, 59490, 1466, 64250, 70191, 58593, 82492, 86220, 96004, 85490, 49119, 24133, 81499, 35133, 68410, 49650, 52517, 10794, 70426, 84501, 52975, 78819, 95570, 97750, 46333, 40846, 44776, 12289, 54472, 38464, 23570, 82125, 36501, 56855, 90733, 70381, 43568, 88813, 14929, 5963, 15675, 89008, 49168, 73306, 94429, 37541, 53587, 27877, 81474, 75066, 68888, 5237, 79198, 80889, 80979, 78577, 98250, 18516, 45965, 91229, 39981, 53704, 16101, 27490, 96150, 73705, 88804, 9801, 83059, 22193, 49737, 26240, 73883, 74182, 82539, 70510, 10478, 85386, 23444, 54546, 51676, 93158, 11131, 53303, 38249, 91838, 82076, 3466, 54662, 29432, 10950, 9531, 92866, 28419, 80951, 44656, 5906, 63916, 48292, 1348, 89945, 32674, 94168, 4682, 91878, 28749, 23365, 42456, 79742, 99991, 86879, 23841, 26429, 5983, 10027, 16181, 75741, 29301, 77978, 17905, 58365, 72315, 43494, 47628, 93001, 80419, 23542, 80941, 70564, 89393, 74006, 3110, 3947, 39094, 25129, 47360, 51671, 69514, 64645, 27807, 66723, 39776, 85098, 30637, 82291, 55028, 70438, 84662, 12973, 18215, 73164, 40498, 10158, 65720, 6942, 84153, 49868, 44484, 50174, 15596, 41618, 81558, 92480, 8331, 44617, 92630, 8777, 42596, 54261, 70804, 95025, 46120, 52702, 13116, 4711, 47127, 7663, 23001, 11180, 12517, 43963, 23284, 8738, 9306, 27405, 34055, 78448, 21113, 76688, 21584, 74926, 80919, 98781, 47740, 35615, 21585, 46584, 67957, 47463, 85766, 73023, 1518, 36368, 95828, 87336, 2953, 37253, 92490, 89866, 34371, 36246, 5191, 64355, 18220, 45197, 95854, 93507, 95260, 37218, 67647, 77366, 16527, 82074, 44444, 94366, 30864, 97556, 61126, 20756, 59727, 16696, 97202, 76670, 70488, 26111, 47613, 99401, 15424, 34148, 3777, 24470, 32014, 18214, 6752, 32137, 60534, 92341, 10807, 98397, 71434, 30363, 72517, 75902, 27067, 59080, 56052, 93905, 85050, 8137, 99742, 72031, 84341, 67490, 90304, 11348, 43450, 37146, 15342, 94746, 966, 88096, 38423, 52481, 57772, 21929, 14917, 89719, 50908, 21807, 54595, 9193, 22651, 42447, 11034, 42198, 49172, 29132, 24753, 58488, 69398, 61746, 33025, 58303, 55789, 40079, 31006, 74590, 38651, 14097, 24877, 23274, 27495, 19926, 37294, 40617, 51503, 69564, 61885, 75965, 36934, 15009, 98685, 79684, 36177, 95836, 30317, 68589, 347, 13747, 70067, 75913, 37903, 89541, 80286, 41955, 34249, 89561, 16537, 90858, 79917, 46609, 46939, 40616, 44469, 62537, 82107, 45020, 48558, 30081, 1021, 21568, 16971, 2622, 59460, 8776, 19747, 16270, 64303, 95841, 79628, 21651, 68213, 86948, 53378, 76880, 65991, 20183, 25493, 58292, 28265, 45994, 87137, 7521, 10025, 9091, 99974, 94692, 10552, 25246, 71263, 64438, 87097, 85719, 55307, 92841, 1695, 81097, 92328, 6444, 50089, 32393, 79346, 49302, 24854, 63759, 27791, 75131, 91881, 35148, 147, 86823, 95430, 14530, 49839, 37054, 81127, 81765, 75344, 37868, 88627, 87330, 19062, 79225, 26280, 29331, 54184, 52678, 42522, 50184, 95370, 74826, 1880, 6355, 47967, 21299, 93359, 27787, 49141, 68566, 16509, 61579, 42468, 40048, 32419, 48403, 47091, 84793, 52905, 23310, 87748, 46854, 38348, 46270, 80727, 22089, 57650, 32720, 84699, 14712, 59890, 33504, 36205, 8703, 38051, 68083, 11108, 3418, 93711, 26532, 81563, 9516, 62466, 60474, 50210, 52299, 76783, 53507, 79935, 48537, 3000, 12315, 59198, 66164, 9209, 85573, 14297, 84548, 58149, 20928, 80203, 46207, 20440, 41262, 92543, 89815, 49344, 39139, 1630, 40323, 60477, 37733, 15245, 67788, 48717, 32145, 78986, 70852, 60606, 3419, 14059, 13910, 39508, 45321, 62628, 9723, 50290, 96993, 74874, 7582, 21239, 54454, 71002, 64884, 70793, 82439, 13117, 73514, 67630, 46286, 5370, 16735, 74177, 77773, 43674, 98775, 57306, 97898, 22735, 33952, 66499, 48747, 77, 50745, 7565, 83389, 7789, 72590, 69326, 64308, 21266, 37745, 51161, 64491, 45833, 53321, 7763, 19602, 63764, 66483, 88561, 57040, 89690, 49195, 3293, 40182, 81124, 67172, 82761, 26634, 51564, 61509, 14226, 51903, 82791, 13774, 41718, 39670, 42621, 87825, 98908, 77419, 65095, 4821, 26783, 31862, 80086, 9125, 97859, 204, 27175, 72421, 92587, 37957, 14767, 71930, 44143, 26476, 72030, 9799, 87270, 84649, 83747, 62049, 74521, 94932, 11881, 83441, 99004, 67235, 70651, 55611, 94767, 57950, 97442, 46961, 29923, 45235, 97115, 67684, 2677, 34197, 36136, 35966, 86900, 97373, 32709, 72563, 80703, 61472, 87909, 70322, 7783, 87717, 77844, 11557, 70689, 27673, 31210, 34050, 88019, 34351, 6042, 4423, 33638, 97083, 8079, 60679, 83323, 38361, 89920, 57288, 12335, 32616, 84910, 85377, 53662, 71607, 84987, 6161, 37498, 20071, 46131, 15204, 10476, 42986, 56025, 46253, 76719, 29611, 37024, 12852, 95482, 51108, 74945, 87088, 17398, 65042, 46474, 87562, 92415, 35370, 98046, 55974, 50708, 12887, 37808, 51568, 82500, 71669, 40532, 46369, 7998, 95186, 20097, 34584, 36673, 37382, 10851, 71727, 69441, 64607, 63706, 68594, 98238, 38988, 93779, 91841, 48456, 18973, 92317, 22801, 83416, 70939, 38130, 13306, 93130, 40654, 67250, 72104, 87477, 67344, 81648, 80299, 26229, 48208, 67848, 21728, 10918, 78678, 77058, 21660, 23402, 94109, 38300, 56788, 34967, 50951, 8970, 47830, 78293, 16444, 20476, 81875, 52384, 37691, 93486, 15097, 7635, 24376, 71304, 29224, 61058, 67961, 85551, 35348, 14009, 1037, 65894, 46742, 5011, 16341, 93352, 55129, 6279, 38291, 51498, 7638, 80306, 99113, 53579, 47934, 53344, 90446, 89989, 27609, 6429, 39104, 92011, 5246, 3905, 82784, 18575, 3346, 73702, 17932, 60136, 68241, 11653, 25199, 47291, 20385, 23748, 97615, 91164, 16577, 56759, 39185, 77307, 97958, 67287, 54891, 49220, 9218, 19822, 2733, 88184, 10802, 64695, 33893, 24809, 93752, 41746, 16692, 78703, 62659, 93271, 11639, 79143, 93318, 84626, 74259, 8039, 78814, 69878, 82230, 60772, 11112, 94568, 21135, 81450, 44408, 10668, 75588, 45653, 90683, 78612, 75709, 56404, 35034, 53723, 374, 65887, 77029, 51857, 19250, 78415, 21778, 96853, 49517, 15467, 31728, 91235, 53474, 25171, 42904, 8851, 26618, 6587, 22086, 71067, 3645, 78336, 93600, 88365, 53749, 30929, 34791, 73637, 91906, 72162, 16699, 77167, 67296, 36269, 56432, 8803, 44651, 3919, 47397, 90509, 24578, 98177, 94516, 76578, 43231, 92388, 9033, 72501, 52715, 10659, 73730, 68121, 95459, 10490, 8795, 29490, 59746, 59842, 85337, 83362, 39012, 14396, 46633, 21687, 61645, 59388, 37556, 32317, 36555, 30244, 78979, 88483, 30221, 63216, 33343, 10965, 43714, 35928, 64541, 19204, 4952, 69686, 66759, 34503, 50767, 39740, 34265, 1574, 3334, 59324, 5465, 11861, 74837, 71265, 15686, 22321, 29175, 60523, 25322, 11325, 2626, 88628, 4691, 20411, 84941, 35705, 88900, 46511, 87951, 65858, 93246, 33570, 46739, 9382, 38486, 815, 32708, 12914, 11520, 80336, 42296, 87271, 39302, 15614, 15602, 25071, 12025, 43337, 21144, 54957, 74967, 23902, 51423, 13358, 51201, 46089, 25827, 65341, 69003, 74283, 69044, 39389, 3250, 18474, 21196, 97222, 78860, 56323, 15883, 74617, 64628, 87918, 30608, 47699, 50048, 62141, 46957, 57662, 50740, 75826, 85270, 66382, 84091, 12226, 99619, 71156, 39886, 15763, 5823, 75503, 41430, 38644, 66649, 88863, 12406, 97351, 53020, 69335, 92333, 44649, 46127, 64516, 13507, 14814, 47491, 25645, 10417, 60855, 65771, 14790, 98366, 47302, 79292, 52835, 79674, 91033, 39058, 47510, 64591, 70315, 24915, 68269, 15553, 95939, 64184, 12579, 73400, 80208, 16300, 28052, 74741, 66051, 7130, 55524, 99107, 65805, 46749, 63154, 51945, 2019, 28525, 26901, 15894, 2441, 69985, 30168, 67615, 87447, 64452, 5876, 16481, 89756, 17309, 56294, 38711, 80347, 22142, 8378, 3977, 63829, 3228, 66776, 87766, 41715, 72429, 38955, 98753, 16902, 9947, 16522, 48611, 9244, 55710, 36525, 94470, 8756, 97766, 63544, 85923, 63820, 95592, 45269, 62591, 46536, 80288, 17064, 78617, 13020, 94463, 99716, 63397, 66501, 80244, 35076, 8246, 62961, 70527, 34956, 55302, 92120, 65906, 86891, 68059, 83525, 74847, 82353, 71073, 41764, 16594, 78039, 66331, 85398, 51896, 93302, 5285, 9167, 88701, 9669, 97049, 47322, 71415, 64792, 45116, 15994, 49008, 23512, 93494, 12799, 6095, 15645, 14213, 94151, 82547, 65063, 18926, 65046, 86279, 56397, 49678, 22925, 25099, 42120, 45250, 80504, 37102, 93777, 8063, 38802, 45285, 50262, 26950, 20882, 29275, 48679, 4135, 5582, 63345, 19939, 33545, 3497, 97177, 7459, 62442, 77252, 83990, 84807, 59854, 38734, 73626, 12734, 67571, 5788, 33330, 91571, 8911, 66654, 66807, 19381, 51969, 10990, 74831, 82394, 20667, 267, 37430, 72211, 17280, 79082, 38989, 76546, 23002, 88624, 90668, 1159, 77362, 27200, 60844, 40088, 32525, 19741, 99180, 24812, 60465, 14573, 2610, 94196, 50790, 31056, 96353, 44283, 58874, 45740, 63546, 95960, 25704, 69001, 83653, 55997, 6824, 24367, 75104, 93345, 37110, 72115, 31354, 65100, 37106, 62135, 73613, 47409, 18297, 58029, 34897, 33717, 29863, 1015, 39643, 80812, 99577, 10631, 18072, 14391, 79910, 42889, 43264, 59714, 25882, 73281, 82210, 5739, 75716, 56363, 46512, 6039, 73993, 47629, 73601, 95526, 43788, 4285, 65337, 37404, 97220, 68408, 27677, 26650, 39414, 46634, 72604, 2256, 12410, 23259, 74865, 26726, 3464, 75142, 16502, 74027, 54081, 58358, 47088, 7751, 19463, 56567, 11698, 47792, 76451, 4844, 7333, 69757, 27557, 65525, 89114, 14869, 88513, 67379, 43390, 79400, 72276, 70285, 43225, 3737, 84371, 56739, 17742, 68772, 52399, 15743, 78196, 83821, 37381, 40627, 69320, 40883, 25275, 68043, 47767, 52637, 1769, 76614, 97975, 19657, 7846, 17196, 79768, 39901, 91258, 98154, 94327, 81121, 88942, 89195, 916, 24197, 25430, 62996, 83700, 96871, 1698, 39466, 1207, 17777, 44875, 27628, 29169, 86622, 21923, 44256, 8251, 75946, 5115, 64059, 91846, 69371, 80711, 93549, 87641, 52189, 36611, 41788, 88275, 93036, 94444, 23042, 24279, 11614, 86808, 76456, 33340, 52029, 87745, 91153, 64582, 85529, 59431, 61334, 96542, 17725, 8296, 84539, 76982, 53941, 12942, 52390, 49637, 65696, 50221, 23985, 87530, 48193, 67662, 74289, 60409, 59347, 10068, 67300, 16968, 75080, 61084, 95523, 85063, 69569, 26594, 66243, 65062, 8139, 74799, 24189, 55679, 87303, 98489, 26300, 56911, 6264, 31398, 25434, 7945, 23697, 94560, 19055, 1057, 97437, 89486, 25698, 10009, 20974, 61769, 7111, 16803, 68097, 16020, 53864, 45067, 80601, 3872, 11789, 48191, 48824, 25669, 71800, 45056, 46476, 73380, 12502, 73082, 98549, 44406, 81726, 98878, 45288, 64625, 61664, 82675, 98793, 21991, 74596, 34737, 16256, 59834, 26327, 19501, 30125, 8436, 21993, 35155, 41065, 77470, 90487, 33357, 10180, 80421, 36837, 38703, 90253, 85760, 95508, 79018, 95074, 56941, 39231, 826, 68484, 55211, 75001, 74893, 9730, 6766, 81290, 22525, 9719, 82565, 65650, 11552, 75455, 17042, 59993, 79173, 64335, 674, 15611, 61341, 42887, 88704, 52811, 99586, 76285, 12538, 79033, 58216, 70715, 11609, 20727, 78118, 75249, 47214, 44138, 56287, 39267, 32360, 60151, 95698, 80898, 71570, 43666, 80740, 41852, 60507, 98667, 56791, 59850, 89320, 15215, 52112, 38359, 77357, 38947, 37898, 87461, 89151, 42633, 25901, 86436, 60263, 29961, 17897, 61715, 5420, 89118, 32731, 71206, 84829, 21084, 71425, 69559, 10239, 15918, 42455, 41511, 76845, 26644, 12333, 9995, 60492, 92694, 57965, 29365, 65576, 73383, 55429, 58245, 43957, 82790, 75734, 70020, 25702, 88329, 61519, 56732, 32402, 72363, 90288, 84343, 45920, 89469, 15674, 10509, 41488, 85872, 63866, 6094, 39599, 86960, 10365, 1993, 38290, 77607, 42493, 33171, 11025, 84558, 3393, 48211, 50959, 36685, 24477, 96527, 80141, 33633, 94337, 11275, 85208, 65584, 38229, 67212, 53603, 35371, 30433, 47391, 6838, 7060, 577, 98028, 68683, 89367, 45738, 21597, 57212, 48007, 84481, 22180, 93207, 45671, 10856, 1076, 85904, 74300, 43036, 45355, 96206, 28220, 30692, 55074, 51077, 87612, 44588, 69560, 24392, 79324, 49823, 29498, 37335, 56214, 85003, 6631, 64007, 17376, 51724, 96595, 53687, 3174, 29001, 76714, 71288, 47954, 35150, 32795, 1072, 34536, 48987, 10117, 33326, 41918, 99192, 98539, 66658, 34260, 97208, 85571, 51510, 72945, 86190, 41057, 45042, 77227, 8066, 36206, 79934, 42755, 28379, 8046, 72257, 55360, 95045, 25397, 14038, 33234, 29694, 94657, 99365, 73149, 21936, 5839, 34772, 88570, 87856, 96382, 77528, 62956, 40240, 40076, 62932, 44333, 69708, 48233, 29952, 93123, 81413, 23870, 23883, 58911, 7303, 46718, 17094, 9041, 40144, 965, 16921, 94165, 20741, 66385, 57876, 94257, 12015, 50382, 32236, 30981, 58135, 67081, 97915, 47316, 15648, 90169, 76395, 43033, 83565, 94506, 21258, 78100, 12600, 25445, 73899, 64135, 9504, 74250, 6739, 57961, 54179, 13542, 5642, 20957, 85002, 79785, 25348, 53012, 42783, 75943, 60343, 835, 8712, 24763, 90679, 22131, 31112, 69992, 91072, 65282, 99261, 52822, 41655, 42760, 68370, 46331, 49724, 35470, 39646, 8188, 62225, 36398, 55089, 47498, 87985, 58783, 91588, 45218, 52614, 87538, 99826, 28256, 73423, 71864, 61133, 41836, 95979, 91926, 73086, 42749, 8162, 2514, 32982, 34390, 63136, 23586, 62059, 74630, 15029, 13091, 76248, 41815, 39767, 4513, 85394, 49161, 39154, 96952, 3838, 60208, 75119, 43216, 39570, 38921, 23263, 87670, 48324, 62175, 19326, 14202, 63537, 98127, 34404, 94783, 66131, 70137, 2687, 64290, 86971, 50120, 34689, 12251, 60922, 7842, 4003, 14785, 45465, 7160, 31272, 70725, 71605, 98703, 97439, 15852, 20496, 98937, 25159, 91138, 31497, 5863, 18480, 92305, 25896, 2753, 87462, 63919, 13971, 96668, 12265, 52870, 95093, 31529, 11487, 43998, 82482, 16033, 28852, 11886, 86745, 28558, 8898, 54439, 40746, 76984, 99553, 6962, 44407, 95397, 8985, 94874, 73343, 24935, 16588, 36698, 16014, 54947, 79968, 35572, 95553, 17036, 44355, 77977, 48793, 4429, 23936, 79825, 43596, 8560, 7548, 4990, 82036, 17468, 84411, 76602, 68870, 32197, 24897, 92577, 6800, 62334, 31344, 30695, 19884, 71219, 48910, 11666, 69630, 49931, 26320, 2174, 99406, 90292, 78740, 75149, 15136, 74294, 49932, 37285, 52942, 77267, 75957, 35478, 80373, 50372, 33156, 85819, 58334, 53953, 73515, 73115, 97138, 72505, 32115, 72719, 99820, 3329, 4192, 49048, 88265, 9114, 18935, 72251, 80750, 9022, 24245, 48656, 7657, 96460, 52204, 30042, 59813, 22961, 88474, 2883, 26845, 88716, 6901, 3963, 3487, 45701, 51509, 2603, 35627, 69382, 38748, 25365, 55653, 28531, 14827, 4835, 51508, 55442, 59578, 27352, 30983, 39590, 31676, 63952, 30372, 99463, 3790, 60375, 8674, 48758, 19506, 3647, 36457, 10065, 81839, 83495, 67139, 24212, 74709, 28174, 88565, 81080, 73238, 78887, 40516, 74959, 21833, 52791, 79738, 92990, 69050, 86590, 54120, 72797, 31189, 78370, 21879, 40531, 60592, 34656, 64760, 86944, 39775, 17493, 58262, 5820, 16645, 85938, 34310, 93191, 81972, 90383, 69584, 49376, 84712, 42111, 94674, 67538, 16916, 25181, 54481, 82970, 68296, 68070, 59319, 63372, 48168, 1623, 173, 85954, 36526, 22218, 94033, 87457, 91448, 58531, 74774, 72206, 63879, 99037, 39967, 15084, 38083, 31555, 84629, 71146, 86230, 36713, 38101, 77043, 90763, 41504, 69553, 31768, 26985, 64387, 9445, 91550, 14874, 80089, 9323, 82976, 62178, 14855, 9024, 51134, 53014, 98226, 77483, 47768, 62034, 75689, 27140, 85846, 21091, 51009, 55737, 97696, 69450, 75637, 48938, 27095, 67987, 69159, 70313, 13421, 18937, 64173, 19807, 76336, 68009, 73379, 76934, 59723, 825, 31823, 11760, 123, 45564, 51443, 62460, 70192, 7790, 69388, 4948, 71632, 5780, 626, 57513, 88950, 45163, 36425, 37671, 20438, 61101, 62006, 73655, 55010, 40066, 25472, 48877, 11658, 15209, 85713, 66752, 91076, 87228, 89453, 10205, 52763, 83658, 37122, 66641, 12316, 59615, 51080, 80365, 11201, 72610, 14041, 4098, 2819, 65741, 39824, 88220, 43554, 67058, 91260, 78734, 51212, 42100, 6783, 87592, 81508, 4738, 93860, 17792, 2060, 70477, 90201, 24336, 39621, 10944, 29556, 65503, 73733, 48565, 39582, 1326, 1884, 77933, 10474, 54501, 72053, 48134, 49465, 18755, 66981, 60723, 60280, 87135, 50810, 31014, 98465, 43177, 23254, 34185, 67467, 66085, 56219, 44814, 54401, 99948, 78377, 39808, 11355, 82101, 80636, 29195, 6577, 52525, 30567, 80676, 8640, 60739, 54961, 46725, 79008, 27441, 40978, 48040, 22864, 98961, 9800, 60600, 3660, 67122, 27886, 80263, 22976, 69809, 52258, 93307, 25730, 13286, 63650, 51786, 15555, 24009, 5138, 88765, 76728, 44648, 2598, 42518, 92437, 59710, 75032, 61937, 41346, 8320, 64393, 6609, 32350, 29649, 46741, 16848, 33251, 17649, 10795, 24542, 29435, 55574, 70284, 91904, 15882, 56415, 75607, 97820, 937, 54631, 70491, 40824, 18168, 23696, 41029, 72213, 99057, 70364, 56093, 32874, 96020, 89918, 5400, 82725, 36366, 382, 48442, 45557, 28508, 78647, 72179, 71523, 3511, 80744, 12974, 98785, 58804, 19419, 22020, 58899, 31015, 48658, 49002, 26991, 57473, 4154, 31852, 67508, 73625, 68835, 696, 57020, 97942, 94923, 88473, 42544, 534, 75049, 72887, 88445, 4411, 46967, 28319, 34952, 63080, 56658, 95606, 49485, 93925, 41006, 35141, 62585, 76067, 82170, 80427, 34211, 48942, 64921, 84289, 27720, 9999, 86624, 38442, 89655, 69261, 39960, 86553, 67918, 50148, 14833, 90680, 31043, 6880, 52692, 25868, 22628, 95674, 68563, 6124, 14806, 71459, 31655, 21962, 66, 27961, 10101, 8019, 67130, 61989, 60235, 65844, 33344, 50905, 92959, 18419, 36050, 5117, 90115, 77300, 99195, 22232, 59390, 78933, 92058, 70433, 32322, 5137, 882, 54093, 84089, 22539, 48444, 77098, 97163, 73717, 72025, 31453, 38194, 25390, 4177, 17970, 36372, 68737, 17490, 44253, 44945, 44678, 58674, 94579, 84232, 77093, 92885, 38347, 28468, 8683, 5435, 90341, 69146, 40874, 49060, 19099, 50251, 4167, 51005, 7659, 85696, 24491, 63360, 94962, 60623, 6373, 69215, 11077, 32252, 61075, 45098, 8234, 54058, 5104, 52161, 51872, 66631, 29002, 69213, 70915, 38564, 21435, 83094, 49729, 58800, 16134, 18138, 57416, 82272, 90698, 90689, 80043, 76950, 25480, 74726, 19649, 48577, 42197, 71468, 62287, 77119, 10441, 26289, 93984, 23569, 23073, 12452, 61028, 79886, 50719, 33889, 54976, 66804, 85849, 21727, 90280, 48997, 40305, 20480, 95129, 70711, 5085, 34313, 30675, 61001, 42428, 46076, 83419, 11049, 78531, 70969, 50546, 31861, 34085, 36992, 3670, 93438, 84800, 39073, 64733, 87201, 47341, 12674, 82056, 98767, 79390, 12497, 6621, 23917, 71546, 53416, 93700, 73723, 33949, 65832, 1421, 94725, 92846, 41598, 54388, 45687, 36079, 9819, 38664, 35696, 10196, 93776, 13004, 60965, 20226, 38575, 8802, 34261, 67643, 1787, 27302, 78733, 43743, 91255, 85892, 81312, 70471, 52200, 27484, 53403, 71289, 56231, 44722, 96670, 37162, 25784, 57997, 74430, 17209, 18894, 92573, 69869, 39218, 4013, 39688, 23637, 96745, 33700, 15074, 59973, 40044, 56949, 9697, 89698, 37370, 10092, 15301, 68295, 75397, 75428, 48911, 51095, 84002, 64569, 26713, 50278, 29933, 10596, 65400, 260, 45430, 75746, 98805, 72239, 52519, 61236, 78956, 94695, 23488, 29336, 38463, 63988, 38773, 71535, 16883, 91784, 67522, 57510, 23865, 92108, 53419, 90981, 79012, 54227, 12700, 31515, 8044, 68668, 14735, 2927, 98683, 95693, 90357, 16566, 71253, 37421, 90211, 35631, 41445, 86838, 74456, 19447, 65847, 54153, 44934, 68214, 41802, 1404, 31032, 29996, 15866, 91847, 77691, 56815, 45507, 90051, 11699, 72078, 91405, 33317, 96743, 21, 66674, 14689, 48986, 88997, 23785, 58938, 11406, 80250, 15473, 32401, 54949, 37281, 55329, 89287, 73186, 68706, 57860, 10615, 83629, 93457, 47527, 6900, 69011, 43004, 60191, 38962, 74276, 68539, 74403, 4221, 16934, 2457, 16947, 26790, 69999, 20079, 63171, 13311, 59646, 63370, 36134, 61300, 95651, 60241, 85684, 12946, 68255, 9717, 59966, 79914, 20283, 91408, 87121, 8849, 25394, 77968, 20490, 97746, 55674, 32076, 33594, 78327, 5229, 39311, 59849, 83295, 23680, 84488, 20347, 86017, 22298, 74605, 36935, 59815, 74243, 21909, 49850, 51944, 89858, 70851, 38381, 29818, 89595, 53675, 96748, 50231, 9099, 47299, 75002, 14108, 53063, 70017, 77069, 21666, 40965, 23368, 2334, 69304, 58372, 36316, 46647, 11659, 5526, 70037, 5248, 57673, 3332, 57391, 62665, 58733, 32561, 83464, 20656, 2702, 50927, 40566, 36717, 7485, 53679, 75310, 5687, 79330, 98013, 97303, 32457, 61416, 4494, 97799, 52736, 83437, 72863, 68256, 60037, 77880, 48102, 37401, 58349, 65613, 57321, 30777, 28529, 9115, 79448, 13199, 1314, 32199, 47096, 99561, 48989, 88105, 71855, 71922, 78917, 6386, 82649, 19761, 3926, 41471, 51770, 37063, 70057, 56542, 15542, 75447, 92046, 99129, 10857, 11968, 49668, 46600, 55032, 39628, 2446, 40225, 49514, 72304, 79227, 51344, 53671, 553, 91501, 68221, 36484, 62878, 98412, 14623, 96920, 76129, 19014, 39676, 71201, 8532, 87128, 68230, 13056, 4552, 56958, 94227, 12153, 2913, 47544, 65305, 24439, 89638, 58281, 21915, 13845, 55224, 89303, 19820, 25482, 12695, 89045, 39259, 93818, 13106, 1531, 71345, 77719, 66410, 30009, 98420, 33258, 94146, 28616, 15778, 84015, 33, 5524, 6772, 66922, 29145, 44987, 44040, 12807, 38903, 72744, 8069, 28544, 43032, 16789, 61276, 62365, 38705, 78136, 50568, 1097, 87235, 50576, 80827, 2466, 79138, 83050, 87960, 7375, 39183, 47296, 95290, 93273, 36897, 64781, 9081, 77228, 91823, 51932, 81105, 6946, 12871, 59917, 48282, 64366, 44252, 70288, 28851, 73694, 81644, 60382, 35007, 56915, 49497, 88748, 48935, 52757, 63563, 7701, 50027, 71662, 30422, 97361, 27583, 84988, 52815, 90034, 94741, 20454, 70091, 10370, 62192, 63117, 57424, 73535, 22929, 52252, 19918, 89950, 52979, 38431, 63936, 74782, 80708, 78434, 7243, 36772, 57147, 89784, 63781, 98748, 93854, 56450, 58571, 24464, 84360, 88112, 99025, 76901, 26943, 72960, 75764, 46239, 33119, 90820, 3981, 99269, 37951, 28037, 88729, 88633, 31918, 10468, 46605, 21536, 85926, 72423, 47226, 12741, 35982, 58609, 57065, 47928, 28914, 78151, 35326, 50128, 36891, 17144, 5406, 6622, 36715, 50718, 98131, 85883, 32377, 13961, 58122, 30120, 78409, 9828, 79898, 87230, 5527, 43405, 66761, 53878, 5055, 81577, 21861, 17199, 18184, 90330, 90075, 18253, 83501, 22332, 44191, 27087, 78786, 57404, 6691, 47457, 71104, 63054, 89887, 80988, 40558, 97360, 72529, 98087, 53629, 95113, 63776, 1691, 1988, 47370, 42610, 99478, 33631, 89099, 97779, 33568, 4436, 59112, 29732, 31024, 5072, 98488, 8609, 88693, 55296, 22064, 81719, 96659, 38937, 82162, 38437, 94720, 95191, 72240, 41318, 527, 3456, 64821, 58296, 59594, 82083, 90508, 89903, 4460, 78133, 88078, 53299, 30316, 17958, 89445, 76402, 69459, 3160, 84152, 46907, 75321, 38766, 84513, 39028, 77829, 60242, 42433, 73294, 92401, 56532, 21920, 88242, 94279, 18278, 53405, 20788, 48746, 3759, 10248, 89886, 88500, 25508, 45726, 96441, 90718, 76375, 71084, 65873, 52775, 60224, 88559, 89424, 79297, 1943, 67551, 61844, 33359, 82961, 27811, 13698, 49175, 66887, 24926, 35219, 98602, 80345, 88524, 17014, 43323, 91272, 94666, 40735, 86973, 9728, 6017, 76113, 80284, 18194, 74432, 54658, 2435, 46097, 36375, 49363, 64179, 82826, 13128, 49951, 78670, 99612, 30389, 76581, 3455, 38760, 7857, 22362, 27100, 48152, 91187, 35990, 17568, 30206, 82637, 29639, 74167, 62204, 60899, 274, 36727, 11544, 61016, 52552, 52088, 35170, 10255, 74434, 56030, 54084, 32733, 25735, 35556, 96109, 9400, 50200, 94310, 93531, 4223, 22818, 20159, 55701, 67010, 30831, 9757, 75276, 83682, 75585, 80670, 55126, 36625, 9554, 89753, 80292, 26331, 61533, 2207, 63840, 61826, 57580, 34000, 70256, 55042, 77482, 82888, 15004, 63398, 72943, 69429, 31634, 6302, 81437, 91678, 38862, 57798, 38193, 88219, 17964, 12128, 22684, 49126, 85891, 65416, 39447, 945, 69332, 7557, 23695, 88234, 94986, 75228, 58, 22132, 91491, 75307, 40505, 9944, 1240, 99142, 89844, 21645, 63063, 99895, 63793, 25697, 35381, 98203, 86975, 77013, 10635, 72178, 42661, 13172, 27749, 8989, 71157, 49145, 24743, 95824, 84841, 45736, 86259, 67183, 79097, 58850, 17651, 86407, 93921, 82428, 68948, 90438, 41160, 39197, 15361, 15745, 9605, 33232, 86250, 16776, 29430, 3144, 75062, 51984, 56666, 3707, 23619, 10230, 83726, 38599, 79236, 53306, 67023, 42128, 85123, 4300, 53287, 8820, 43721, 40254, 65885, 39313, 75994, 8270, 18967, 11578, 52956, 58422, 42648, 85964, 47303, 49446, 25017, 58594, 87306, 26495, 30588, 41202, 902, 6637, 51682, 31310, 87441, 41634, 35387, 66345, 40973, 94716, 44546, 58561, 55159, 33167, 51613, 15544, 91964, 59152, 91421, 26398, 52696, 80360, 78266, 16743, 89689, 45954, 31849, 5586, 99635, 81153, 88176, 39385, 10282, 90332, 18796, 47865, 98252, 79990, 99021, 23352, 22599, 60869, 64688, 8836, 52737, 756, 2574, 48472, 70632, 76953, 68988, 97165, 69099, 9162, 13679, 17554, 77159, 25606, 82317, 40563, 95226, 66393, 97938, 64121, 79561, 52516, 75619, 52307, 45368, 8233, 7238, 32937, 97883, 25554, 26705, 36458, 7539, 26938, 36424, 24389, 8638, 71769, 35365, 39632, 20604, 76892, 89505, 659, 73810, 4941, 35974, 18429, 36900, 89346, 77514, 85878, 75082, 20281, 93699, 39663, 10428, 52004, 24637, 50943, 65174, 91742, 18729, 71971, 88831, 59599, 24287, 87577, 85481, 71166, 24112, 70662, 37262, 1548, 70046, 79498, 52508, 99076, 76044, 27813, 67303, 88061, 578, 94249, 6491, 59181, 55585, 62375, 75058, 38719, 59076, 84673, 80881, 75961, 73126, 20474, 11730, 43893, 55254, 11289, 76835, 9119, 95865, 35788, 21372, 67159, 67917, 37114, 4122, 91751, 10286, 8831, 86147, 43382, 32868, 34098, 53093, 71958, 32164, 35955, 57980, 30681, 85454, 63812, 98054, 28017, 47942, 52813, 6758, 7962, 27488, 75192, 86371, 11203, 96395, 52359, 57761, 82501, 15840, 36009, 36545, 58239, 12089, 25302, 48981, 19286, 59591, 14305, 73153, 9012, 26095, 40518, 18634, 11817, 38014, 9594, 2766, 35120, 96367, 86561, 69938, 93518, 85584, 44566, 93535, 54852, 18890, 68570, 95190, 74723, 47886, 89134, 68024, 86930, 37727, 36383, 16777, 53764, 23889, 98242, 56603, 20701, 21607, 78701, 47012, 60529, 30014, 55012, 60012, 11072, 9101, 98183, 80351, 79166, 44245, 15634, 61128, 16818, 57679, 82375, 96923, 38998, 74655, 71162, 92509, 23727, 45772, 63681, 30225, 51884, 20886, 34307, 58949, 11390, 44170, 9204, 44390, 70328, 91636, 17914, 58776, 52267, 77656, 44665, 66795, 58451, 7244, 15795, 47555, 84874, 62912, 62386, 79503, 56972, 54195, 18678, 56253, 75730, 47501, 26972, 53286, 29629, 45329, 42083, 76376, 45825, 83380, 82954, 44379, 45601, 69455, 34045, 15024, 4426, 68481, 10275, 8379, 64371, 43589, 93275, 58615, 82690, 32559, 85188, 74584, 89349, 22260, 32268, 95797, 479, 23554, 10643, 41296, 85768, 13594, 65963, 15228, 87848, 26698, 94020, 64581, 97841, 90354, 67594, 76364, 80632, 87658, 57742, 17077, 9080, 76874, 57664, 9598, 12658, 33279, 59605, 79782, 98161, 51257, 15044, 46282, 77272, 30537, 80985, 30958, 78630, 61226, 51334, 63158, 93136, 23210, 49968, 99862, 8134, 30971, 29088, 75015, 39834, 65842, 20508, 74942, 60620, 1306, 52143, 90505, 90904, 67035, 83870, 19122, 22102, 35239, 59918, 29576, 20056, 25241, 60217, 53893, 21903, 6551, 8953, 21849, 78365, 21336, 2362, 42572, 64560, 61040, 29469, 28225, 5239, 55966, 27228, 4170, 81666, 42324, 35203, 62858, 83656, 44620, 64680, 78593, 4697, 86679, 7942, 62678, 93076, 81197, 58846, 41677, 61055, 12865, 66127, 96421, 65320, 40479, 26084, 53724, 26114, 60719, 6003, 56242, 51656, 65758, 15835, 24645, 43636, 55405, 88916, 76655, 9921, 35296, 56159, 5736, 79599, 19802, 90704, 23144, 6201, 44704, 35002, 23024, 95280, 83, 95027, 53696, 63713, 69205, 57511, 46750, 80937, 13676, 79376, 74365, 7233, 52887, 85699, 48730, 56250, 3151, 70396, 86737, 2234, 46753, 17995, 55156, 84824, 51455, 79798, 33380, 52745, 32885, 58764, 16464, 78943, 72742, 29845, 37769, 77380, 88531, 29813, 63487, 30190, 22842, 20267, 88199, 69585, 92105, 22302, 99123, 66870, 41829, 95444, 29506, 66779, 24258, 84199, 69039, 37893, 90407, 71947, 83837, 13097, 30657, 20024, 32801, 97490, 48854, 81797, 32521, 55235, 50421, 47097, 20374, 27522, 52365, 13997, 49107, 62946, 70686, 80593, 74239, 60665, 2497, 56382, 96552, 38882, 39840, 88897, 9565, 26848, 12035, 63541, 11236, 67043, 16580, 40381, 85894, 97459, 74299, 42498, 66217, 31687, 9708, 13648, 93263, 71891, 89248, 94159, 14663, 64657, 68979, 8099, 51982, 29578, 18507, 69118, 81924, 25826, 65747, 78394, 85715, 9775, 386, 43293, 95630, 59658, 24803, 90080, 32048, 7682, 69517, 62078, 71172, 60243, 19623, 22388, 12908, 21518, 2881, 31955, 26043, 22554, 15859, 36016, 37318, 17941, 59116, 55340, 35412, 92316, 7100, 39880, 36333, 28043, 5557, 62425, 38652, 26788, 17442, 52157, 69298, 40702, 38812, 23621, 71491, 94084, 29780, 40840, 43054, 74988, 62030, 8880, 21038, 45251, 68965, 78092, 28410, 2743, 59747, 42525, 27450, 62028, 42690, 11473, 12629, 52550, 79452, 8311, 27077, 25668, 75357, 6774, 98430, 69565, 53899, 16736, 27613, 46449, 32705, 69467, 7728, 20917, 30739, 49031, 21825, 85360, 43163, 72609, 63689, 58268, 64084, 47342, 27988, 38697, 68540, 96431, 75409, 62876, 92968, 57220, 96566, 33071, 9729, 91141, 77867, 92295, 3834, 73247, 2679, 79966, 57049, 92269, 75010, 47239, 20495, 51875, 4521, 2223, 79355, 73623, 95487, 85578, 14257, 38835, 27520, 27227, 32300, 60323, 33470, 19205, 91071, 30510, 98893, 24385, 81004, 55939, 50452, 608, 8236, 9295, 35443, 93680, 97914, 55649, 95405, 14614, 88636, 5590, 15854, 39193, 14704, 17669, 84547, 15035, 16746, 49063, 22862, 16254, 5481, 37058, 76621, 61177, 48564, 18564, 76787, 58968, 16677, 26890, 71184, 31062, 42132, 7765, 41051, 6503, 81085, 56492, 68022, 1496, 48076, 16659, 93661, 65761, 55283, 13522, 52502, 88232, 30355, 97387, 35398, 19669, 43079, 57687, 98603, 42393, 12279, 91022, 99856, 76567, 55191, 24465, 42754, 58817, 66555, 76563, 85057, 98204, 86636, 99564, 64836, 94916, 48643, 45581, 57451, 34537, 5082, 55416, 60380, 54921, 55099, 15006, 48204, 55395, 12342, 86549, 64685, 39220, 24883, 23838, 78634, 21343, 42495, 61985, 16931, 34221, 61700, 23451, 71252, 30451, 99906, 35050, 24463, 46501, 48118, 81232, 171, 75109, 89579, 63254, 13881, 25374, 83313, 46038, 80899, 76244, 3002, 36730, 3549, 54758, 71588, 14424, 48536, 57902, 88161, 73543, 1442, 50156, 51721, 11778, 83354, 66130, 97232, 48927, 15166, 15103, 26939, 87571, 3694, 52202, 33580, 28355, 20772, 630, 41232, 24262, 23824, 54754, 87553, 43762, 3370, 40957, 19519, 7045, 17827, 8538, 12683, 47683, 26359, 56350, 9773, 48914, 23925, 76452, 89589, 10400, 77509, 51787, 24681, 20733, 95695, 56441, 88404, 60525, 22029, 7645, 82698, 88439, 21255, 24005, 69772, 14710, 66171, 65153, 47844, 28304, 66188, 69017, 36629, 58067, 45122, 13641, 88708, 97058, 50530, 16171, 25600, 93819, 47616, 82991, 85414, 35426, 99952, 5593, 6550, 7043, 4730, 67070, 27260, 44376, 3400, 76093, 62284, 26881, 72861, 77416, 26499, 12783, 4408, 70806, 60773, 74382, 52492, 81735, 31839, 41793, 15730, 2320, 88284, 85754, 90079, 53254, 25871, 66983, 38801, 48455, 49611, 75816, 38042, 83948, 43543, 27891, 92805, 31506, 63053, 31201, 97368, 52080, 15330, 52347, 20311, 50368, 77685, 76912, 19016, 23668, 75137, 42154, 83272, 41817, 43889, 2494, 67046, 31546, 89935, 82475, 83326, 71062, 25786, 18869, 2727, 67824, 77985, 78440, 38939, 82275, 60548, 22745, 39625, 46606, 72266, 11589, 91650, 52268, 86289, 75240, 82111, 89169, 23468, 56768, 21759, 22821, 30914, 11256, 87968, 31215, 77022, 75147, 80884, 64359, 23462, 14062, 54719, 31664, 96742, 34625, 13880, 36150, 95327, 36696, 74634, 46012, 28434, 53535, 30850, 84945, 13562, 30127, 46403, 69801, 44916, 11066, 45609, 23521, 61567, 52185, 48089, 3041, 39394, 22981, 70372, 85781, 19311, 67703, 61174, 47175, 30805, 51526, 91041, 4070, 13579, 26572, 4528, 48335, 43093, 79889, 8374, 14417, 47571, 98241, 10020, 51125, 98774, 75263, 44578, 9453, 12798, 11177, 36999, 50181, 46693, 59657, 2837, 44341, 58921, 77580, 14346, 8329, 68254, 58541, 17858, 97406, 45115, 43978, 98082, 81422, 59589, 30946, 99059, 29395, 42051, 43416, 44004, 8104, 22202, 4904, 57717, 74791, 88072, 15273, 9996, 4381, 52897, 82112, 89452, 24966, 59782, 22873, 44134, 95914, 4407, 98067, 97405, 83939, 47433, 19510, 47576, 53571, 66424, 42064, 98191, 80650, 87408, 25813, 74984, 98091, 19709, 79911, 5786, 55234, 83174, 66125, 85645, 80947, 2715, 68196, 99900, 81865, 60666, 64024, 62540, 2672, 23359, 97310, 4862, 72019, 28455, 47614, 29652, 38057, 8731, 95668, 11911, 21175, 29982, 98662, 46183, 55288, 18687, 84610, 63153, 47287, 63561, 41182, 55186, 13353, 46104, 30928, 71369, 84305, 62803, 44507, 91866, 61802, 63170, 53429, 24115, 18309, 67258, 45791, 4291, 26047, 75682, 97468, 37092, 65313, 4791, 73964, 78258, 9470, 77410, 17686, 71357, 34486, 55778, 19369, 41454, 29371, 94132, 56069, 11369, 10181, 34754, 82116, 70272, 13151, 21575, 90982, 40588, 26418, 44775, 65083, 86992, 51742, 61678, 65344, 6361, 78665, 40084, 50484, 20315, 2423, 95284, 40613, 51832, 31937, 91999, 79278, 48234, 50348, 97401, 93119, 27796, 48110, 74777, 23576, 49353, 55200, 82085, 11291, 64913, 48095, 51480, 31958, 38795, 72818, 90663, 28061, 99424, 45284, 84109, 50867, 5463, 20721, 62228, 35086, 25032, 82886, 10160, 17578, 81092, 70165, 14677, 12229, 74035, 30528, 75083, 31670, 87424, 44098, 15387, 48815, 48443, 66472, 7185, 57157, 60955, 64342, 56974, 52150, 61510, 63006, 31695, 53813, 5486, 10533, 45817, 77406, 26092, 58546, 86325, 33139, 60658, 89205, 52896, 2047, 41900, 13658, 79042, 32438, 52126, 63225, 56228, 66235, 82430, 48493, 28960, 75212, 76465, 38485, 99783, 92051, 64488, 29408, 62272, 42325, 5473, 51975, 84993, 4365, 15311, 70154, 69774, 93315, 35949, 42678, 13624, 96468, 28353, 95015, 49948, 69090, 77668, 54537, 96097, 7964, 66288, 43935, 53978, 54398, 68535, 60752, 29852, 54071, 44107, 42015, 45525, 88398, 39718, 35359, 9720, 87833, 60239, 90147, 13647, 39534, 76216, 73066, 83934, 78248, 28054, 75765, 30096, 72779, 86442, 56868, 10605, 13380, 46486, 7833, 53984, 52627, 71460, 93122, 75991, 62122, 44073, 93889, 57160, 88272, 63708, 8657, 66959, 24695, 30400, 73231, 72416, 8210, 23381, 57945, 22476, 32780, 92965, 62925, 97114, 88720, 63614, 65268, 9560, 81771, 14439, 56036, 64267, 2356, 32254, 92510, 73995, 48906, 12724, 14122, 70628, 10979, 30450, 47189, 4523, 49908, 58699, 16826, 94043, 55535, 50286, 97189, 14621, 61386, 76053, 62254, 90181, 61866, 63662, 30748, 53564, 41208, 40765, 89649, 88357, 24151, 42637, 6908, 75091, 94412, 13704, 1532, 17824, 71710, 46714, 1789, 64441, 69374, 6457, 49394, 58126, 28710, 27860, 11884, 65660, 32476, 28857, 23776, 89518, 55238, 47481, 48573, 93527, 94545, 83848, 28733, 81896, 51324, 65514, 23929, 59563, 37947, 66508, 49535, 82621, 9278, 89105, 60722, 76025, 61691, 53310, 30581, 9473, 28907, 31706, 3577, 20629, 65723, 51039, 26125, 95510, 48601, 49541, 13213, 80954, 9341, 32286, 80428, 41302, 11775, 80507, 90562, 73046, 55883, 4557, 16178, 5758, 81761, 35963, 71483, 33916, 74706, 10413, 67321, 45513, 16511, 70186, 20439, 12249, 91901, 4856, 61239, 63049, 19600, 56714, 89484, 63435, 17414, 24952, 62464, 89747, 85149, 8869, 97566, 76923, 44516, 4606, 32832, 3325, 56131, 7931, 10209, 18835, 46786, 2056, 57807, 17467, 86124, 6433, 20189, 53245, 42993, 95212, 94816, 29501, 55521, 5641, 72825, 59951, 60746, 41608, 7672, 90360, 19236, 16843, 77477, 87368, 59317, 818, 66325, 15722, 28866, 98651, 78606, 81720, 25500]
それぞれをGoogle Colabを使って実行しましょう。
選択法で並べ替えたときの処理時間
改良版の選択法で並べ替えたときの処理時間
実行時間の差を見て、思ったことを記述してください。
たとえば、
「少しの改良で処理時間が短縮されたので、アルゴリズムの効率の良さを追求するべきであると感じた」
「改良した割にはあまり効果はなかったので、あまりアルゴリズムの効率化は不要だと感じた」
など。
最大 500 文字
※この再現版では提出は行いません（送信先は未接続です）
