ソートロジック大会

[omasu]

お世話になります。

　自分が理解しているソートロジックは
　バブル、単純挿入法、単純選択法、バケツの４種類です。

　クイックソートやシェル、ヒープのロジックはわかりません。

　どうか以下のロジック以上早いソートロジックを
　簡単な記述でアクティブベーシックロジックを教えてください。

　ちなみにexeで文字１０００件のソートが３２秒かかりました。
　 cpu pentium4 2.66GB

'
'　単純選択法(最小、最大１パス選択)ソート
'
Print "sort start",Time$
p3=tblcnt
For i=1 To p3-1
p1=i:p2=i
For j=i+1 To p3
If keytbl$(p1)>keytbl$(j) Then
p1=j
EndIf
If keytbl$(p2)<keytbl$(j) Then
p2=j
EndIf
Next j
If p1<>i Then
Swap keytbl$(i),keytbl$(p1)
Swap datatbl$(i),datatbl$(p1)
EndIf
If p2<>i Then
Swap keytbl$(p3),keytbl$(p2)
Swap datatbl$(p3),datatbl$(p2)
p3=p3-1
EndIf
Next i

[イグトランス]

すいません。
試してみようにもkeytbl$とdatatbl$の関係がわからないので、
どう扱ってよいか判断に迷います。

両者にそれぞれどんなデータを入れるのか教えてもらえませんか？

[omasu]

申し訳ありません。

　知人からｃｓｖファイルのソートを依頼され、最速？ルーチンの作成を手がけました。

　テストデータとして列が２６列、キー列は１列目と２列目、ランダムな３桁の数値を１０００行作成したＣＳＶファイルをテストデータとしました。
　ｋｅｙｔｂｌ＄はソートキーとして１列目と２列目のデータを連結
　ｄａｔａｔｂｌ＄は２６列の全てのデータをｃｓｖ化出力するためのカンマ区切りのデータを入れています。
　書籍によると、ソートキー＝ソートデータとして扱っている物がほとんどのため、データ列から特定の優先キー列を抽出するロジックも追加しました。

　単にランダム数値を文字列として扱っているためキー１２３と１２３よりも１３と１３の方が結果としては大きくなります。

以下にプログラム全体を添付します。

　最新版アクティブベーシックではコンパイルエラーとなってしまうため
バージョンは２．６２を使用しています。

　ちなみにデバックでの実行時間は７２秒、ｅｘｅでは３２秒かかります。

　バブルソート　　デバック１１５秒　ｅｘｅ５５秒
　単純挿入ソート　デバック１５７秒　ｅｘｅ７３秒　ロジック最悪

力量不足でクイックソートやシェル、ヒープはベーシックでは作成していません。

'**************************************************************************
'*　ＣＳＶファイル入力、テーブルセット、単純選択法改良ソート、ＣＳＶファイル出力
'**************************************************************************
'
'　変数定義
'
Dim tblcnt As Long
Dim a$ As String,b$ As String,c$ As String,d$ As String,e$ As String,f$ As String,g$ As String,h$ As String,i$ As String,j$ As String,k$ As String,l$ As String,m$ As String,n$ As String,o$ As String,p$ As String,q$ As String,r$ As String,s$ As String,t$ As String,u$ As String,v$ As String,w$ As String,x$ As String,y$ As String,z$ As String
Dim keytbl$(2000) As String,datatbl$(2000) As String
Dim i As Long,j As Long,k As Long
Dim p1 As Long,p2 As Long,p3 As Long
'
'　処理開始確認
'
MsgBox hMsgWnd,"ソート処理を実行します。よろしいですか？",hSubWndTitle$,MB_YESNO or MB_ICONINFORMATION,MsgretAns
If MsgretAns=IDNO Then
Goto *ProgramEnd
End If
Print "program start",Time$
'
'　ファイルオープン
'
Open "infile.csv" For Input As #1
Open "outfile.csv" For Output As #2
'
'　ファイルリード、テーブルストック
'
Print "tbl stock start",Time$
tblcnt=0
While Eof(1)=0
Input #1,a$,b$,c$,d$,e$,f$,g$,h$,i$,j$,k$,l$,m$,n$,o$,p$,q$,r$,s$,t$,u$,v$,w$,x$,y$,z$
tblcnt=tblcnt+1
keytbl$(tblcnt)=a$+b$
datatbl$(tblcnt)=str$(tblcnt)+","+a$+","+b$+","+c$+","+d$+","+e$+","+f$+","+g$+","+h$+","+i$+","+j$+","+k$+","+l$+","+m$+","+n$+","+o$+","+p$+","+q$+","+r$+","+s$+","+t$+","+u$+","+v$+","+w$+","+x$+","+y$+","+z$
Wend
Print "tbl stock end",Time$
'
'　単純選択法ソート
'
Print "sort start",Time$
p3=tblcnt
For i=1 To p3-1
p1=i:p2=i
For j=i+1 To p3
If keytbl$(p1)>keytbl$(j) Then
p1=j
EndIf
If keytbl$(p2)<keytbl$(j) Then
p2=j
EndIf
Next j
If p1<>i Then
Swap keytbl$(i),keytbl$(p1)
Swap datatbl$(i),datatbl$(p1)
EndIf
If p2<>i Then
Swap keytbl$(p3),keytbl$(p2)
Swap datatbl$(p3),datatbl$(p2)
p3=p3-1
EndIf
Next i
Print "sort end",Time$
'
'　ソートしたテーブルをファイルに出力
'
Print "file out start",Time$
For i=1 To tblcnt
Print #2,datatbl$(i)
Next i
Print "file out end",Time$
'
'　ファイルクローズ
'
Close #1
Close #2
Print "program end",Time$
'
'　処理終了確認
'
*ProgramEnd
MsgBox hMsgWnd,"ソート処理が終了しました。",hSubWndTitle$,MB_OK or MB_ICONINFORMATION,MsgretAns
End

[河川屋]

>文字１０００件のソートが３２秒
そんなにかかるのは、たぶん、言語処理系にとんでもなく効率の悪い
ところがあるためと思われます。
Excel上のVBAで、最小値選択法で組んでみたところ、
全変数をバリアント型にしたという手抜きしたにもかかわらず、
文字１０００件のソートは１秒以下。おそらく０．１秒。（ソート時間のみ。）
ちなみに、
keytbl$()：会社名簿の住所
datatbl$()：会社名
で行なったから、datatbl$()のほうはomasuさんのよりだいぶ小さいですが、
１０００件３２秒は異常に遅い？？？
　※バリアント型：型宣言なし。文字でも数値でも使える。
　　　　　　　　　そのかわり、メモリーを食うし計算が遅い。

で、遅い原因の１つかもしれない点として、
・文字型を多用したためガベージコレクションが多発した
というのがあります。（basicインタプリタに時代には確かに存在した。）
これは、言語処理系の作りにより、多発したり、全く発生しなかったり。
よって、ガベージを起こさないためには文字列演算をしないのが良いし、
datatbl$()が巨大ならガベージを考慮しなくても入れ替えに時間がかかるため、
入れ替えを極力行なわなければ高速化されます。
（ただし、最小値選択法は、入替え回数が最小の部類のアルゴリズムです。）
よって、順位配列を用意し、こうやると速くなる場合があります。
ついでながら、最小と最大を一遍に求めてもあまり意味ないと思うけど。
（比較回数、交換回数が減るわけではない。）
このため、最小値のみを求めています。

　　 dim rec(1000) as integer　　'順位を入れる。

　　 for i = 1 to tblcnt
　　　 rec(i) = i
　　 next
　　 for i = 1 to tblcnt - 1
　　　 k=i
　　　 for j =i + 1 to tblcnt
　　　　 if keytbl$(rec(k)) > keytbl$(rec(j)) then k = j
　　　 next
　　　 if k<>i then
　　　　 r = rec(k)
　　　　 rec(k) = rec(i)
　　　　 rec(i) = r
　　　 end if
　　 next
　 ' 結果の書き出し
　　 for i=1 to tblcnt
　　　 print #2, datatbl$(rec(i))
　　 next


あと、比較回数を減らすことを目指したアルゴリズムの１つとして
シェル法の例。なお、この例は順位配列は使っていません。
交換回数はそこそこの回数発生するため、
datatbl$()が巨大なら最小値選択法に負ける可能性あり。


'クヌースによる改シェル法
　　　Gap = 4
　　　While Gap <= tblcnt
　　　　Gap = 3 * Gap + 1
　　　Wend
　　　While Gap > 1
　　　　Gap = (Gap - 1) \ 3
　　　　For j = Gap + 1 To tblcnt
　　　　　i = j - Gap
　　　　　t$ = keytbl$(j)
　　　　　tt$ = datatbl$(j)
　　　　　k = j
　　　　　While i > 0 And T > keytbl$(i)
　　　　　　keytbl$(k) = keytbl$(i)
　　　　　　datatbl$(k) = datatbl$(i)
　　　　　　k = i
　　　　　　i = i - Gap
　　　　　　If i < 0 Then i = 0
　　　　　Wend
　　　　　keytbl$(k) = t$
　　　　　datatbl$(k) = tt$
　　　　Next
　　　Wend


注記　左側の半角は削られるんでやんの。
　よって、全角スペースを使っているので、全角スペースは
　半角スペース×２に置き換えてください。

[omasu]

お世話になります。
　河川屋さんの言われるとおり、実行速度が遅い事は実感しておりました。ａｂの最新版では早いのでしょうか？
　エクセルのデータの並び替えを使用しても１秒もかからず完了します。

以下に私のテストデータを使った実行時間を一覧表示します。

　「今は昔」の話ですが、ロムベーシックやディスクベーシックの時代に『ｉ＝ｉ＋１』のような「自分プラス自分」計算をするとガベージコレクションが発生するとか言われていた時代がありました。？？？そんなことが今でもあるのでしょうか？？？

　また、最小と最大を同時抽出した理由ですが、ソート時間はデータ数の２乗に比例するため、１０００件のソートが３２秒かかり、半分の５００件のデータでは、４／１の時間の８秒で終わります。
　データを半分にして二回実行すれば半分の時間で終了する（ヒープソート？）
　そのため少しでも１パスにかかる比較時間を減らしていこうという考えでロジックを組みました。
　その成果がデバックで１１秒の短縮、コンパイルで４秒の短縮となっています。
　（１パスで比較が１個ずつ減るか、２個ずつ減るかの違い）

　シェルソートの実行時間の早さに感動しました。

　(~i~)あつかましいかもしれませんが、もっと・・・を教えていただければ幸いです。

作成者　　　　　ソート名称　　　　　　　　ﾃﾞﾊﾞｯｸﾞ(秒)　　　　　ｺﾝﾊﾟｲﾙ(秒)　　　　　記事
河川屋さん　　　クヌースによる改シェル法　　　　　　9　　　　　　　　　5 　　　　　逆順ソート
omasu 　　　　　単純選択法 　　　　　　　　　　　　72 　　　　　　　　32 　　　　　最小・最大同時選択
omasu 　　　　　単純選択法 　　　　　　　　　　　　83 　　　　　　　　36 　　　　　最小選択
河川屋さん　　　順位決定？　　　　　　　　　　　　119 　　　　　　　　49 　　　　　ソート部のみ
omasu 　　　　　バブル　　　　　　　　　　　　　　115 　　　　　　　　55
omasu 　　　　　単純挿入法　　　　　　　　　　　　157 　　　　　　　　73

[マティ]

ActiveBasicをはじめて３日目のマティって言います。

今回の処理速度が遅いのは、文字列のSwapが主原因と思われます。
同じアルゴリズムでも、キー部分のデータのみをSwapする方が、性能的に有利になります。

キー定義 [ここをクリックすると内容が表示されます]

むかし日経バイトで見たコームソートが単純でそれなりに早いので紹介します。

コームソートのソース [ここをクリックすると内容が表示されます]

[omasu]

　マティさんの示唆で「だんだん」高度な話になってきたため（~＝~）| おじさんには「だんだん」と理解ができなくなっています。
　ｓｗａｐを減らすというのは、ｓｗａｐコマンドを使わない方がが早くなるのでしょうか？（～ｍ～）便利なので使っちゃいました。

（ｓｗａｐ＄＝ａ＄：ａ＄＝ｂ＄：ｂ＄＝ｓｗａｐ＄）という記述をすれば早くなるのでしょうか？

[マティ]

Swap命令が問題なのではなく・・・
並べ替えを行う場合は、
　数値を用いて比較を行う
　文字列を用いる場合は、文字列自体は移動しない。（添え字orポインターを移動する）
を用いた方が良いと言いたかったのです。

-------------------------------------------------
ActiveBasicも文字列管理がどのよう行われているかは分かりませんが
一般的に可変長の文字列を移動する際には、以下のような処理が行われる
と考えた方が良いと思います。

（例）以下の配列があります。

文字列(1)=■■■■
文字列(2)=□□
文字列(3)=○○○

この時、メモリには、
0 1 2 3 4 5 6 7 8 91011121314（メモリの番地）
■■■■□□○○○
　文字列(1)は　０　番地に格納
　文字列(2)は　４　番地に格納
　文字列(3)は　６　番地に格納

このとき、文字列(1)と文字列(2)を交換すると
　文字列(1)は　４　番地に格納
　文字列(2)は　０　番地に格納
となれば理想的なのですが、

ガーベージコレクションの必要な処理系の場合は、
0 1 2 3 4 5 6 7 8 91011121314（メモリの番地）
□□・・・・○○○■■■■
　文字列(1)は　９　番地に格納
　文字列(2)は　０　番地に格納
　文字列(3)は　６　番地に格納
のように処理を行ってしまいます。

・・・・は未使用領域となり、この部分を使用可能にする処理を
ガーベージコレクションといいます。

[マティ]

[AB4]の新規プロジェクトのノーマルウィンドウモードにコマンドボタンを作成すれば実行可能なコードを乗せておきます。
（CSVの１・２項目が数字項目として動作確認しています。）

コームソートの実行可能コード [ここをクリックすると内容が表示されます]

[淡幻星]

ガーベージコレクションとか、可変長文字列の扱いとか、
結構高度な議論になっているところ、そんな領域には
さっぱり踏み込まない投稿もどうかと思いますが、
参考までに書いてみます。


≫omasuさん
>ａｂの最新版では早いのでしょうか？
コードにも因りますが、ずいぶん早くなります。
Ver2.62は中間コード型なのに対して（私もまだ愛用してますが＾＾；）、
Ver3.0以降は実行コード型になったので、
実行ファイル（.exe）でのかなりの速度向上が望めます。
私のとあるコードの場合は、Ver2.xからVer3.xに乗り換えることで、
10倍ほど高速になりました。
（主要部において、String形を一切使わずにBytePtr型に書き換えたりも
　したので、それだけの要因ではないと思いますが。）
最新版のVer4.xはより最適化がされているはずなので、もっと早いかもしれません。


>バブル、単純挿入法、単純選択法、バケツの４種類です。
>クイックソートやシェル、ヒープのロジックはわかりません。
>どうか以下のロジック以上早いソートロジックを
「データ形式（逆順or乱順etc）に寄らず高速」と評判のコムソートが
マティさんから紹介されていますので、今更な感もしますが、
私の使っているクイックソートのコード（Ver2.59）を、参考までに載せておきます。
正順or逆順に非常に弱いのが欠点ですが、
「乱順に対しては非常に高速であり、コードも簡単」との評判のアルゴリズムです。
ソートの王道（理解しやすい割りに早い）って言われているらしいです。
私の環境では500件前後のデータで2秒くらいだったでしょうか（.exe型Ver2.59）。

address() As Long -- ソート結果後の移動先の配列要素番号が格納されます。
　　　　　　　　　　Ex: address(2)=6 --> 元の配列の2番要素はソート後は6番要素
　　　　　　　　　　　　　　　　　　　　に入れられるべきこと意味。
　　　　　　　　　　　　　　　　　　　　初期値の設定は不要（ゼロでよい）。
source() As String -- ソートが実行される配列。
　　　　　　　　　　　　「ソートキー」って呼ぶんでしょうか？
　　　　　　　　　　　　中身は変更されません。
ByVal lef As Long -- ソート範囲の左端（開始要素番号）
ByVal rig As Long -- ソート範囲の右端（終了要素番号）

コード: 全て選択

'□ QuickSort □ ************************************************************
Sub QuickSort( address() As Long , source() As String , ByVal lef As Long , ByVal rig As Long )
  dim i
  dim process(rig-lef+2) As String  'ソート結果を入れる配列。
  
  for i=lef to rig
    process(i) = source(i)  '元の順序をコピー
    address(i) = i          '元の配列番号をコピー
  next i
  QuickSort_Part( address() , process() , lef , rig )   '昇順に並び替える
  i = lef
  while ( i <= rig )  'たまに空要素が範囲内になることがあるので、それを外にだす（原因不明。一つだけ入ることがある）。
    if process(i) = "" and process(i+1) <> "" then
      swap process(i),process(i+1)
      swap address(i),address(i+1)
    else
      i = i + 1
    Endif
  wend
EndSub


'plm() の配列を lef～rig の範囲で昇順に並び替え、その配列番号の移動先を sort() に記録する。
Sub QuickSort_Part( sort() As Long , plm() As String , ByVal lef As Long , ByVal rig As Long )
  if lef = rig or lef > rig then ExitSub  'チェック範囲が１ or ナンセンスな範囲＝その範囲内はソート済みなので、プロシージャを抜ける。
  dim i As Long      '左側のチェック場所
  dim j As Long      '右側のチェック場所
  dim div As String  '閾値
  dim div_n As Long  '閾値の場所

  div_n = (lef+rig)/2  '閾値の場所の決定
  div = plm( div_n )   '閾値の決定
  i = lef  '左側チェック場所初期値
  j = rig  '右側チェック場所初期値
  while ( i < j )  '左からのチェックと右からのチェックがぶつかるまで、左からのチェックを繰り返す。
    if plm(i) <= div then  '左側のチェック：閾値よりも小さいとき
      if i = div_n and lef <= i then  '閾値の場所にぶつかったとき。
        swap plm(i),plm(i+1)  'まだ左と右はぶつかってないので、閾値の場所を右へ移動する。
        swap sort(i),sort(i+1)  '配列場所移動の記録
        div_n = i + 1  '閾値の場所を右へ移動したことを更新。
      else
        i = i + 1  '左側のチェック：チェックする場所を右へ一つ進める。
      Endif
    else  '左側のチェック：閾値よりも大きいとき
      while ( plm(j) >= div and lef < j )  '右側のチェック：閾値よりも小さい文字が見つかるまで左へ進む。
          if j = div_n and j <= rig then  '閾値の場所にぶつかったとき。
             swap plm(j-1),plm(j)  'まだ左と右はぶつかってないので、閾値の場所を左へ移動する。
             swap sort(j-1),sort(j)  '配列場所移動の記録
             div_n = j - 1  '閾値の場所を左へ移動したことを更新。
          else
            j = j - 1  '右側のチェック：チェックする場所を左へ一つ進める。
          Endif
      wend
      swap plm(i),plm(j)   '左側の大きい文字と、右側の小さい文字を入れ替える。
      swap sort(i),sort(j)  '配列場所移動の記録
    Endif
  wend 
   if plm( div_n ) > plm( div_n + 1 ) then  '最後の閾値場所移動で右側に小さい文字が来ると、それをチェックできないので、その補正。
    swap plm( div_n ),plm( div_n + 1 )
    swap sort( div_n ),sort( div_n +1 )  '配列場所移動の記録
    div_n = div_n + 1
   Endif
   if plm( div_n - 1 ) > plm( div_n ) then  '最後の閾値場所移動で左側に大きい文字が来ると、それをチェックできないので、その補正。
    swap plm( div_n - 1 ),plm( div_n )
    swap sort( div_n-1 ),sort( div_n )  '配列場所移動の記録
    div_n = div_n - 1
   Endif
  QuickSort_Part( sort() , plm() , lef , div_n-1 )  '分類の終わった、小さい側（左側）をさらにチェックする。
  QuickSort_Part( sort() , plm() , div_n+1 , rig )  '小さい側は終わったので、残りの大きい側（右側）をさらにチェックする。
EndSub

･･･実は微妙にバグ（ソート失敗）があったり。でも滅多に発生しないので放置中（苦笑）。
時間があったら、Ver3.x用に書き換えてみようとも思っています。

参考サイト
http://www.ffortune.net/comp/develop/sort/gaikan.htm
http://www2s.biglobe.ne.jp/~nuts/labo/daal/daal06.html

[イグトランス]

淡幻星さんに先を越されてしまいましたが、私のクイックソートのコードです。

コード: 全て選択

Sub QuickSort3Main(KeyTable() As String, Index() As Long, ByVal First As Long, ByVal Last As Long)
	Dim j As Long, Center As Long
	If First < Last Then
		Swap Index(First), Index((First + Last) / 2)
		Center = First
		For j = First + 1 To Last
			If KeyTable(Index(First)) < KeyTable(Index(j)) Then
				Center = Center + 1
				Swap Index(Center), Index(j)
			End If
		Next
		Swap Index(Center), Index(First)
		QuickSort3Main(KeyTable(), Index(), First, Center - 1)
		QuickSort3Main(KeyTable(), Index(), Center + 1, Last)
	End If
End Sub

テストに使ったのは60数件と少な目のデータですが、最初の選択ソートが160ミリ秒前後、このクイックソートが60ミリ秒前後になりました。（コンパイルして）

以下コード全体です。

コード: 全て選択

#strict
Declare Function timeGetTime Lib "winmm.dll" () As DWord
Declare Function timeBeginPeriod Lib "winmm" (ByVal uPeriod As DWord) As Long
Declare Function timeEndPeriod Lib "winmm" (ByVal uPeriod As DWord) As Long

Function GetKeyPart$(ByVal str As String) As String
	Dim Length As Long, PartA As Long, PartB As Long
	PartA = InStr(1, str, ",")
	If PartA > 0 Then
		PartB = InStr(PartA + 1, str, ",")
		If PartB > 0 Then
		End If
	End If
	GetKeyPart$ = str
End Function

Const TableSize = 2000

Dim tblcnt As Long
Dim keytbl$(TableSize) As String, datatbl$(TableSize) As String
Dim i As Long,j As Long,k As Long

Dim Line$ As String

Dim StartTime As DWord, EndTime As DWord

Dim SubWndTitle$ As String, MsgretAns As Long
SubWndTitle$ = "ソート"

'
'　処理開始確認
'
MsgBox OwnerWnd(), "ソート処理を実行します。よろしいですか？", SubWndTitle$, MB_YESNO or MB_ICONINFORMATION, MsgretAns
If MsgretAns=IDNO Then
	Goto *ProgramEnd
End If

timeBeginPeriod(1)

Print "program start", timeGetTime()
'
'　ファイルオープン
'
Open "z:\infile.csv" For Input As #1
Open "z:\outfile.csv" For Output As #2
'
'　ファイルリード、テーブルストック
'

Print "tbl stock start", timeGetTime()
For i = 0 To TableSize
	Line Input #1, Line$
	keytbl$(i) = GetKeyPart$(Line$)
	datatbl$(i) = str$(i) + "," + Line$
	If Eof(1) Then
		Exit For
	End If
Next
tblcnt = i
Print "tbl stock end", timeGetTime()

StartTime = timeGetTime()
Print "sort start", StartTime
QuickSort3(keytbl$(), Index(), tblcnt)
EndTime = timeGetTime()
Print "sort end", EndTime
'
'　ソートしたテーブルをファイルに出力
'
Print "file out start", timeGetTime()
For i = 0 To tblcnt
	Print #2, datatbl$(Index(i))
Next i
Print "file out end", timeGetTime()
'
'　ファイルクローズ
'
Close
'
'　処理終了確認
'
Print "program end", timeGetTime()
timeEndPeriod(1)
Print "ソート時間:"; EndTime - StartTime; "ミリ秒"
*ProgramEnd
MsgBox OwnerWnd(), "ソート処理が終了しました。", SubWndTitle$, MB_OK or MB_ICONINFORMATION
End

Sub QuickSort3(KeyTable() As String, Index() As Long, ByVal Num As Long)
	Dim i As Long
	For i = 0 To Num
		Index(i) = i
	Next
	QuickSort3Main(KeyTable(), Index(), 0, Num)
End Sub

' ここに先のQuickSort3Mainを入れて下さい。

[河川屋]

>あつかましいかもしれませんが、もっと・・・を教えていただければ幸いです。
ここから先は一般論になります。
ソートアルゴリズムの優劣を見る場合、一般には、
比較回数と交換回数で比べます。
だから、datatbl$()のほうはくっつけない状態で比較するのが普通です。

で、ソートアルゴリズムとその特徴
(別途作業用メモリーを使うものは除外。)

クイックソート　　NlogN 　但し、運が悪いとN^2の手間。
ヒープソート NlogN　　計算量はデータの並びにほとんど左右されない。
シェルソート　　N^1.25(?) 計算量の理論値不明。いちおう、
　　　　　　　　　　　　　 N*(logN)^2または約N^1.25らしい。
単純挿入法　　　　N^2　　　ほとんど整列済データに対してなら最速。
最小値選択法　　　N^2　　　データ交換回数最小。
単純交換法(バブル) N^2　　 いいとこなし。

ソートの速度の理論値はNlogN。ただし、データの性質を利用したもの
（たとえば、整数データのみ、など。）は、更に速いのもありうる。

他のプログラミング例です。datatbl$()はくっついていないのと、
これはN88BASICです。（行場番号省略。）

'シェルソート（ノーマル）
' Gapの取り方が違うだけで、あとはKnuth改と同じ。
Gap = N
WHILE Gap > 1
Gap = Gap \ 2
FOR I = Gap + 1 TO N
J = I - Gap: T = DAT(I): K = I
WHILE J > 0 AND T < DAT(J)
DAT(K) = DAT(J): K = J: J = J - Gap
IF J < 0 THEN J = 0
WEND
DAT(K) = T
NEXT
WEND
RETURN

'ヒープソート
L=(N\2)+1 : R=N
WHILE L>1
L=L-1 : GOSUB 3500'SHIFT
WEND
WHILE R>1
SWAP DAT(1),DAT(R)
R=R-1 : GOSUB 3500'SHIFT
WEND
RETURN
3500 '篩い落とし
I=L : J=2*L : X=DAT(L)
IF J<R AND DAT(J)<DAT(J+1) THEN J=J+1
WHILE J<=R AND X<DAT(J)
DAT(I)=DAT(J) : I=J : J=2*J
IF J<R AND DAT(J)<DAT(J+1) THEN J=J+1
WEND
DAT(I)=X
RETURN

[イグトランス]

参考までに
http://ja.wikipedia.org/wiki/%E3%82%BD% ... C%E3%83%88
ソートに関しては完璧ではありませんが、ここはそこそこよくまとまっていると思います。

[マティ]

河川屋さんのコードを一部いじって計測しました。

私が使用したテストデータは、ある程度ソート済みです。
件数：　　　約27万件
レコード長：約340ﾊﾞｲﾄ
並べ替えキーは数値項目に置き換え可能なテキストでした
　　Athron 1GHz
　　Memory 512MB
計測時間は、ソートのみです。

クヌースによる改シェル　1970ms
　　　　　　　　シェル　2080ms
　　　　　　　　コーム　2750ms
バブル　　３０分実行しても終わらないので、処理を中止
クイック　スタック不足で強制終了（再帰で組んだのですが、私の能力不足で申し訳ないです。）

2005.08.30：クイックの性能
河川屋さんのコードを正しくインプリメントするとクイックの性能が計測できました。
再帰なし 880ms
再帰あり 1280ms （再帰なしを変更：後ほどアップします）
と言うわけで、クイックの圧勝でした。

2005.08.28：自分の重複投稿が多いので修正しました。

ここをクリックするとコードが表示されます [ここをクリックすると内容が表示されます]

[omasu]

お世話になります。

　トピックのテーマどおりの展開になって、驚きのひとことです。

申し訳ありません。

　事の発端が「知人からｃｓｖファイルのソートを依頼され、
　　　　　　　最速？ルーチンの作成を手がけました。」であります。

　前提条件が「ｃｓｖファイルの１列目と２列目をキーとして
　　　　　　　ソートをしたい」ということで始まりました。

　テストデータは「３桁の数字を文字列として扱い、２６列、１０００件の
　　　　　　　　　データ」を作成しました。

高度なロジックを教えていただき、みなさまには感謝のかぎりです。

　しかし、実行しようにもデータの受け渡しやアドレスの受け渡しにも苦労し
　ａｂのバージョンがわからず、コンパイルエラーの嵐になってしまっている
　のが現状です。

　以下にそのテストデータとして使用したｃｓｖファイルを添付しますので、
　条件にあったロジックをご教授願います。

コード: 全て選択

171,591,339,524,859,549,600,821,633,728,685,169,868,717,707,886,188,902,770,603,672,895,215,338,598,250
290,975,283,448,563,903,925,823,481,826,108,889,813,704,994,808,157,549,933,358,883,716,941,373,889,157
432,620,296,445,236,538,927,551,958,632,408,368,611,325,218,149,103,707,578,489,262,281,322,921,638,207
253,571,876,318,193,263,728,619,134,227,857,388,971,418,278,307,684,934,440,941,379,346,547,838,139,539
112,446,911,180,163,248,511,297,836,491,288,388,211,633,450,578,213,643,512,303,733,387,146,679,714,807
232,555,848,881,450,374,803,698,110,966,365,366,967,310,678,338,470,232,241,589,468,774,355,645,910,220
156,707,812,766,354,107,268,194,361,758,654,193,606,930,242,507,517,500,514,817,724,373,533,805,421,166
983,453,249,652,642,769,185,975,692,230,441,816,970,553,415,176,531,681,338,774,393,531,683,280,825,918
241,900,348,527,226,572,695,936,975,135,446,189,679,767,402,703,954,887,268,202,408,742,661,710,932,372
198,191,609,201,894,418,673,678,584,318,840,778,195,280,520,371,572,653,406,630,247,119,905,856,129,785
914,539,627,835,821,590,743,168,833,274,852,497,944,889,855,228,893,140,567,401,105,199,792,847,425,443
913,875,649,216,724,121,231,908,380,353,924,897,600,617,661,529,223,319,276,490,111,878,521,518,168,360
996,915,767,837,492,556,496,110,726,179,144,969,464,984,962,488,329,585,616,712,744,511,191,328,965,137
354,300,819,555,270,685,179,961,617,549,298,135,771,641,113,121,899,773,471,512,756,206,542,458,756,144
730,346,486,318,905,539,838,927,182,420,187,624,356,106,773,681,465,210,973,961,413,872,642,151,737,907
299,654,326,437,154,844,828,766,906,797,883,204,199,545,864,171,289,353,260,376,478,404,810,800,945,420
760,387,384,747,828,727,659,817,425,499,995,643,107,789,987,374,673,550,195,959,662,546,161,169,489,380
777,318,767,515,857,913,641,801,460,495,588,262,782,122,644,539,779,694,357,485,158,249,910,793,508,383
887,200,410,446,769,794,215,172,787,323,311,141,732,473,913,707,762,448,556,693,441,156,782,233,609,321
951,389,871,202,307,384,547,197,787,327,243,859,631,242,693,433,936,918,368,968,718,457,683,170,475,490
952,700,648,429,895,347,235,749,854,816,807,918,744,186,294,550,193,680,706,358,938,121,790,239,548,398
194,942,366,337,423,318,691,259,539,572,437,263,896,959,382,417,837,699,908,468,394,864,180,869,823,545
294,254,526,328,302,107,245,627,478,844,149,831,746,425,973,518,391,603,807,757,636,320,898,178,636,110
501,187,103,837,211,475,455,879,526,931,971,716,864,783,713,546,352,623,332,830,242,136,471,502,105,111
606,690,227,558,184,985,523,945,964,530,788,436,276,110,589,973,573,296,354,700,382,673,306,610,714,709
928,513,869,692,222,811,274,956,802,303,456,840,192,682,141,552,549,462,554,327,536,594,767,702,522,777
559,582,542,900,966,412,176,333,828,291,828,151,819,437,791,218,646,648,569,233,139,199,604,117,613,283
174,830,968,278,474,502,163,800,416,155,190,445,590,203,113,552,961,130,482,716,898,723,588,980,582,421
399,452,354,391,367,783,235,819,321,254,130,316,124,562,179,462,814,147,397,853,246,519,661,878,829,470
612,397,898,920,950,426,110,995,391,489,188,343,587,556,716,474,683,810,627,390,690,387,137,420,259,627
648,816,342,575,391,764,333,327,274,556,542,797,592,855,834,638,719,658,189,507,204,417,235,138,498,762
382,508,447,313,581,603,812,402,218,211,427,163,370,123,739,598,104,386,527,786,875,420,126,482,995,188
725,607,375,299,166,457,739,540,400,869,960,135,277,842,913,353,266,324,931,978,764,322,229,900,626,188
319,783,216,545,223,414,247,934,823,434,256,402,653,501,437,126,220,194,203,222,683,689,783,450,550,224
180,187,922,811,123,360,276,217,512,239,852,410,439,550,449,635,759,494,421,807,496,637,826,665,545,344
132,543,209,390,716,397,761,374,554,929,493,689,463,388,917,901,892,576,485,331,539,726,886,865,706,423
217,806,201,870,738,233,473,957,895,439,766,954,205,575,539,728,419,889,261,764,266,744,595,894,806,444
971,776,491,724,297,406,149,455,303,184,861,768,280,436,931,214,196,522,339,773,875,870,590,852,965,719
313,837,387,992,336,137,523,113,502,477,804,785,683,149,433,556,464,343,384,902,646,259,945,803,197,769
526,257,736,442,743,646,378,989,915,801,213,275,779,229,713,447,296,883,376,867,111,936,745,372,643,961
568,516,548,878,658,136,643,323,552,625,674,791,740,724,714,208,680,836,874,266,488,659,511,814,188,872
769,268,854,721,720,142,470,474,522,643,419,413,677,503,991,205,442,494,288,119,979,584,814,966,918,207
682,281,380,424,216,959,778,538,501,318,444,908,681,955,331,537,732,984,230,502,336,839,703,250,555,725
792,436,636,633,169,159,609,590,887,945,770,142,830,779,773,716,721,823,737,297,791,859,468,859,538,780
354,582,123,838,461,659,469,172,601,188,924,376,232,697,439,838,278,273,190,208,587,962,211,274,941,889
618,452,769,882,755,719,486,317,222,330,955,212,315,452,262,693,704,118,737,399,815,546,783,494,838,280
123,951,365,979,539,330,376,920,211,819,587,592,708,893,212,290,977,875,329,604,834,987,181,626,729,180
907,681,701,193,977,819,656,223,767,444,261,864,765,635,432,761,659,820,742,552,169,780,450,988,108,418
389,404,543,603,633,500,841,846,935,234,377,424,599,566,622,775,153,985,293,208,103,682,504,885,155,900
776,957,618,801,863,856,802,921,157,718,424,973,501,161,435,970,688,454,834,640,951,277,786,210,826,777
862,653,119,985,810,387,540,114,701,293,627,702,417,716,575,357,766,609,614,235,859,936,169,401,913,772
436,253,544,284,234,314,583,585,575,364,157,352,192,955,857,462,328,157,420,985,217,331,541,717,422,573
388,517,882,721,573,974,130,256,734,520,545,621,996,587,328,478,191,726,107,439,829,997,627,113,154,951
508,882,457,690,111,835,185,631,826,614,959,843,806,475,389,284,342,868,466,590,104,978,264,669,472,677
810,856,137,830,828,337,114,920,514,736,560,299,938,309,709,403,780,990,923,243,562,124,435,237,757,714
985,837,919,701,203,642,862,178,484,863,452,834,897,891,960,662,113,778,363,821,375,907,918,820,896,616
149,099,324,554,661,287,764,750,579,543,149,746,265,838,964,652,779,447,142,184,409,993,116,239,793,569
438,653,552,645,648,190,453,170,977,376,867,693,661,299,708,399,474,917,729,884,498,559,853,195,359,169
350,705,580,783,497,671,623,798,979,995,132,861,790,758,811,792,534,792,981,946,529,268,891,838,447,451
352,850,337,306,265,557,136,299,778,552,601,148,379,799,915,872,680,552,464,269,987,513,384,965,114,360
875,391,221,875,920,654,884,873,325,553,630,495,221,192,513,539,219,822,563,693,440,177,755,875,277,129
522,117,359,144,383,893,855,569,665,347,301,359,476,438,146,309,698,302,192,140,918,665,527,636,458,117
338,771,206,907,219,914,105,718,386,821,758,414,685,281,177,902,905,761,175,378,583,246,710,217,985,560
595,949,910,831,102,636,818,390,781,336,900,818,589,282,778,439,387,422,393,394,184,335,947,430,978,841
249,501,136,719,174,172,930,790,653,597,969,636,670,266,640,768,180,481,301,462,292,957,644,464,575,254
768,631,308,831,866,414,890,573,455,296,837,720,867,477,483,760,558,130,603,309,738,471,834,767,224,434
308,633,147,394,548,513,260,179,664,199,127,499,955,266,652,781,583,903,403,815,202,657,614,513,357,315
510,632,208,897,884,150,511,748,493,575,758,224,166,478,620,533,634,276,690,910,751,366,619,586,992,928
220,145,614,340,103,491,431,545,394,153,229,170,691,385,580,896,964,405,194,169,683,596,351,113,393,860
254,851,954,272,889,558,238,932,741,411,719,417,882,226,377,689,323,352,255,475,789,641,361,289,635,486
891,311,288,428,225,479,997,742,407,541,747,377,352,791,187,155,861,428,510,351,850,830,155,409,254,518
374,353,862,824,648,467,450,962,649,128,689,452,567,887,904,795,814,686,379,210,726,183,410,490,822,288
959,918,744,643,523,768,522,430,634,625,654,333,432,185,278,752,570,652,119,107,662,201,314,111,846,465
125,644,930,610,402,229,799,131,312,229,814,425,250,406,114,921,514,740,938,526,389,684,589,486,920,390
376,196,531,821,331,688,349,631,253,884,846,629,877,660,436,974,464,186,156,111,480,695,193,577,512,559
253,856,845,361,659,745,523,275,272,250,693,370,663,708,605,505,358,697,722,267,257,845,625,244,707,579
972,375,185,506,303,841,272,323,911,523,449,855,550,536,192,392,840,719,873,483,290,618,898,887,278,903
110,297,202,143,456,658,742,382,404,790,592,224,789,893,678,155,737,124,395,866,152,923,458,251,542,947
852,283,662,923,849,786,504,337,838,107,707,434,290,322,985,320,433,480,562,792,690,972,457,968,851,297
220,772,340,233,811,125,454,415,980,126,609,881,173,251,759,332,796,797,360,384,491,822,258,336,501,300
435,485,877,423,294,856,732,831,232,359,762,868,908,234,914,207,110,724,892,155,426,447,397,254,380,528
894,354,474,579,530,835,988,450,114,919,114,254,735,469,704,860,503,678,328,514,626,762,494,207,459,147
858,705,892,744,513,981,534,161,925,798,499,454,765,973,543,926,583,869,563,652,355,136,598,804,396,751
762,173,807,106,591,284,444,572,881,643,381,555,505,613,924,521,466,363,371,550,742,279,463,481,116,708
814,622,714,916,143,626,418,256,725,248,778,621,828,867,333,227,735,423,309,323,612,384,378,257,116,606
646,259,940,706,706,873,979,580,898,840,191,879,564,788,921,140,735,722,648,449,211,923,202,708,457,727
464,613,443,375,207,943,207,722,615,636,582,521,554,112,875,696,277,107,784,987,571,496,800,704,607,256
165,367,213,250,368,486,106,209,897,986,883,882,343,499,159,473,729,668,418,623,711,904,908,360,371,404
445,247,751,989,650,117,313,512,532,660,628,370,242,319,836,621,285,633,815,895,849,684,128,270,310,404
470,661,636,368,385,797,493,964,120,822,435,725,945,869,832,477,188,977,361,948,931,417,117,214,385,586
365,271,198,792,664,225,460,458,543,460,617,602,989,233,897,753,547,195,554,542,718,503,425,296,193,447
884,320,561,996,853,297,506,309,308,983,828,214,475,555,423,916,776,496,944,209,473,338,743,258,971,621
476,842,234,291,291,880,132,681,359,223,400,957,534,493,464,409,820,301,255,942,994,104,470,532,156,329
523,906,218,881,284,658,190,765,253,664,837,485,195,249,315,413,732,104,201,779,290,289,875,816,309,988
672,780,764,546,889,856,407,148,713,410,552,867,526,382,119,760,882,552,709,528,521,904,813,575,132,533
321,807,805,985,591,997,692,982,725,779,663,206,099,797,728,807,946,568,392,336,157,755,327,430,863,927
753,378,657,153,479,584,583,631,679,326,953,283,209,907,795,421,829,320,464,295,962,484,730,290,409,736
974,908,494,460,309,294,496,590,685,228,279,785,957,625,404,260,771,818,381,308,335,805,552,504,502,756
743,655,899,638,343,196,856,988,675,612,954,268,977,620,575,275,227,880,823,791,966,627,683,762,636,711
896,510,152,852,886,404,105,591,832,972,448,637,986,176,785,192,220,569,984,846,530,521,997,362,357,803
663,808,265,349,739,765,173,579,732,980,907,834,552,778,688,351,950,333,606,709,664,751,373,516,278,424
871,520,943,911,865,977,833,773,677,350,123,177,908,422,806,570,560,211,841,384,268,670,849,292,113,781
409,997,447,319,684,256,783,401,389,198,852,196,797,759,752,824,966,270,944,761,398,143,981,488,872,867
750,193,902,973,779,135,718,424,337,594,205,795,297,182,756,848,747,402,645,915,789,560,378,241,887,729
156,843,580,212,910,630,475,945,962,799,170,208,133,585,546,276,156,931,600,736,285,226,908,563,876,219
588,252,370,768,741,695,450,981,705,224,352,564,735,121,232,773,968,400,459,189,892,837,828,508,862,829
576,785,448,656,683,114,935,210,710,554,577,438,612,640,873,965,937,598,648,730,224,504,743,324,628,734
417,588,828,816,519,836,770,214,416,546,957,983,516,931,219,184,359,547,530,174,660,629,719,656,893,916
591,284,415,387,180,897,151,603,280,434,958,524,877,614,469,530,949,949,147,150,741,379,309,937,182,264
772,876,877,105,744,973,736,701,549,301,704,158,258,252,559,542,102,487,381,383,956,899,861,994,817,963
916,889,544,522,452,941,460,796,397,221,847,806,483,452,309,686,189,160,698,152,463,244,801,754,623,894
309,654,276,938,168,490,855,259,103,123,436,756,499,631,124,362,761,119,834,983,932,146,579,682,894,695
136,399,340,136,161,170,149,425,462,794,442,162,219,700,743,564,580,386,826,437,520,916,584,815,516,509
800,987,884,581,750,653,821,897,987,822,636,612,930,804,341,212,887,440,442,854,442,806,168,307,627,566
296,449,491,558,719,634,107,864,174,397,157,642,926,802,919,474,156,119,286,495,675,244,734,435,322,838
976,495,232,414,989,723,983,126,242,965,930,135,818,320,333,363,809,441,145,964,983,145,948,828,970,955
657,419,877,327,241,858,771,736,907,809,566,696,717,552,308,820,155,541,239,278,668,330,264,666,355,292
130,568,904,700,700,296,431,114,154,196,863,258,890,902,945,142,295,533,477,823,597,741,831,689,210,264
526,254,641,843,174,699,984,295,242,801,163,520,200,289,712,559,910,544,547,306,835,653,550,910,630,798
480,752,115,102,474,907,535,144,861,504,944,165,576,606,593,348,636,761,484,628,664,319,174,530,489,671
603,209,903,675,271,342,236,410,788,485,658,525,497,420,882,318,101,365,303,850,394,814,617,223,839,786
838,657,406,754,546,809,282,577,482,884,129,283,443,719,536,626,791,862,859,817,298,765,527,703,360,229
722,341,772,605,623,201,310,729,831,698,735,150,720,202,646,412,157,156,461,193,843,448,561,424,764,384
922,929,387,588,875,809,188,140,909,261,352,519,788,708,549,663,218,249,101,304,518,556,684,447,209,268
280,655,494,376,493,200,423,239,146,783,410,352,504,170,477,318,639,644,747,244,486,446,321,692,284,452
206,735,802,462,507,951,156,324,445,506,377,830,138,843,375,106,833,874,730,433,985,452,928,300,659,216
919,267,554,194,126,450,358,979,209,235,382,331,993,296,966,552,197,917,732,643,812,491,554,216,605,733
169,305,374,613,368,407,537,435,101,636,551,525,478,340,688,160,951,803,989,544,404,169,927,712,789,131
730,708,837,710,786,401,858,357,742,797,441,605,992,248,727,529,227,235,160,488,426,706,887,840,271,770
915,313,188,267,452,446,219,813,415,769,965,541,360,404,308,392,222,586,332,821,565,693,974,654,144,388
250,654,294,531,198,892,335,353,626,832,847,871,747,955,364,872,411,489,496,739,192,784,423,417,965,133
650,608,393,948,808,718,689,169,438,828,386,853,201,873,890,785,896,198,226,842,303,216,789,761,345,568
247,518,259,426,454,744,389,134,991,324,973,242,557,927,613,862,990,125,537,303,575,339,501,982,870,671
586,875,678,200,257,519,298,758,248,468,747,321,518,139,191,306,735,183,740,857,347,805,367,351,898,236
344,569,956,921,864,417,309,289,586,373,136,538,945,931,973,170,112,804,523,901,273,114,326,966,598,212
568,687,448,141,965,303,741,448,808,302,116,313,640,696,256,707,298,977,220,986,218,667,162,261,749,717
183,737,398,432,303,426,525,362,753,364,607,579,149,417,614,248,721,736,877,513,436,314,499,199,924,208
334,147,840,828,626,396,581,321,307,980,467,542,152,814,389,970,648,442,478,747,839,952,231,336,527,541
186,177,558,903,140,771,964,982,203,353,891,360,294,695,737,146,251,613,532,719,238,276,929,186,860,222
160,120,416,869,324,631,477,897,810,235,614,159,394,917,719,411,454,673,334,865,613,459,734,180,774,120
739,916,747,894,324,483,403,738,246,107,336,099,491,339,713,711,658,441,861,287,861,400,343,336,863,330
598,356,787,854,523,541,990,165,899,115,202,585,583,983,158,370,964,352,573,684,147,782,557,186,177,766
249,292,973,102,620,566,812,256,592,797,647,473,105,772,382,851,344,099,352,521,474,617,474,976,823,147
638,548,571,213,285,228,359,280,319,888,198,189,210,402,204,624,646,340,697,331,177,832,498,380,700,778
658,536,681,524,433,380,463,720,367,298,220,983,745,483,989,255,115,573,763,403,557,785,530,108,514,823
544,120,565,467,869,770,723,895,817,260,461,560,748,251,251,244,618,720,674,725,857,478,805,704,193,252
712,748,141,660,946,913,276,496,380,337,294,976,690,606,661,571,384,370,704,158,310,684,782,743,212,471
351,251,823,426,159,371,845,206,963,454,218,113,295,874,425,349,170,384,601,288,788,381,480,949,222,398
683,362,427,227,336,479,212,966,921,700,513,611,262,958,338,412,375,190,696,840,815,326,884,729,382,580
793,829,862,413,393,628,653,370,346,267,619,430,386,250,882,486,551,103,191,777,918,424,659,445,525,897
554,897,960,250,829,210,824,759,153,889,523,936,927,484,771,110,217,694,558,894,301,231,573,805,891,417
148,441,236,736,843,444,518,136,682,144,409,350,659,353,766,850,302,643,662,677,558,658,177,700,118,781
835,264,455,189,118,996,223,842,419,785,640,355,467,678,674,318,743,444,457,683,938,851,391,250,239,867
506,904,441,843,847,345,711,577,538,232,267,243,247,788,159,350,663,367,190,425,731,445,601,168,772,690
650,229,257,170,871,177,934,380,804,811,356,630,233,463,202,642,212,352,441,915,172,934,286,110,966,854
843,758,702,277,957,370,505,350,759,332,996,190,804,256,307,681,674,527,362,806,821,442,326,316,479,629
556,370,345,712,530,229,289,162,162,153,703,112,282,664,733,764,846,462,330,434,499,963,179,323,155,761
437,570,582,567,388,247,879,630,560,247,596,676,914,150,525,739,669,199,100,578,929,424,730,811,191,659
151,803,112,449,899,145,520,161,980,512,899,194,333,099,436,339,291,194,928,270,969,102,250,470,228,535
781,404,264,816,909,460,195,150,354,983,468,433,854,111,496,771,574,625,854,283,458,169,439,587,255,373
402,333,591,276,525,788,656,102,566,508,654,921,841,320,671,936,804,578,743,689,806,358,581,953,980,913
198,500,411,243,494,717,535,388,934,886,493,440,765,322,368,208,751,970,261,206,210,170,106,498,455,439
521,984,351,768,339,838,308,807,331,964,578,977,313,680,157,524,177,247,485,571,453,830,733,563,976,988
153,639,783,491,674,568,672,851,671,161,854,623,701,929,858,978,611,447,304,172,779,562,969,293,241,573
394,741,171,841,756,178,985,388,337,414,549,353,809,716,970,804,776,401,516,975,516,763,195,449,602,441
198,795,144,248,930,926,430,304,270,133,649,551,805,727,334,785,806,683,856,195,264,231,726,238,643,964
482,717,758,456,161,624,693,684,234,458,338,842,449,644,662,211,153,312,869,486,202,463,804,974,224,204
101,887,225,363,160,276,739,588,354,384,399,445,503,409,766,821,785,212,238,370,366,587,415,794,296,993
299,796,302,264,927,845,749,560,583,632,550,189,877,776,326,466,171,388,146,819,185,106,446,867,960,430
182,419,155,326,232,806,540,792,449,878,562,644,177,587,378,717,159,149,969,543,503,500,389,465,810,849
987,792,396,967,886,163,752,553,179,477,106,538,496,185,425,246,694,899,536,880,448,888,764,309,770,539
813,606,801,803,804,254,260,103,559,200,383,704,458,861,720,956,390,770,218,655,956,207,838,910,557,130
462,299,569,338,271,893,954,892,644,884,663,205,221,624,651,256,390,794,725,901,373,276,377,481,164,741
781,985,201,861,944,856,126,945,893,625,485,431,770,667,146,969,227,294,911,275,837,920,749,258,812,954
357,655,220,690,658,468,358,269,987,956,360,890,927,397,483,161,925,947,625,819,725,234,352,268,695,759
167,673,949,676,253,145,755,524,194,483,918,714,393,348,304,656,157,755,818,372,382,522,932,517,172,120
681,312,986,905,449,422,780,532,702,395,654,868,183,432,330,984,373,682,905,822,119,959,700,902,685,865
592,258,320,632,357,409,654,996,803,232,275,578,480,639,578,332,404,159,746,690,159,667,586,717,283,116
372,791,882,601,295,825,755,451,519,326,714,947,640,943,712,360,537,609,619,109,374,469,651,391,528,833
592,935,919,810,557,695,530,487,864,516,588,568,477,890,148,594,371,584,533,713,330,361,429,905,419,140
669,285,119,713,121,914,637,458,719,260,414,559,882,873,626,595,245,322,826,591,686,396,679,702,807,120
727,823,767,960,446,718,963,490,919,829,332,951,305,197,794,541,362,578,588,802,176,718,757,606,746,245
365,191,371,208,328,499,535,753,764,985,826,251,888,172,660,440,946,384,624,312,789,504,670,593,236,962
568,705,249,540,629,911,605,382,931,726,206,333,567,528,324,330,920,609,760,371,261,254,841,896,304,317
149,491,393,766,861,523,924,934,358,860,618,860,935,267,886,834,567,574,708,789,327,802,732,943,548,433
929,395,370,731,435,408,332,870,334,997,582,195,440,426,774,660,475,187,195,819,318,699,695,172,899,188
640,203,463,621,354,925,699,150,281,571,497,207,218,502,807,884,372,624,993,534,544,447,333,311,887,953
950,433,959,187,961,654,646,715,535,370,415,542,726,124,582,662,104,815,527,568,599,591,653,267,353,323
673,629,159,745,665,830,564,663,936,710,898,420,524,937,145,488,517,609,234,814,608,381,195,645,731,440
590,211,422,487,369,984,422,394,689,446,397,898,852,569,360,440,459,118,226,115,619,450,637,984,343,916
590,739,973,755,848,100,277,714,627,638,504,983,494,510,320,108,699,820,202,296,769,345,561,220,679,760
245,799,750,848,777,591,944,466,615,194,380,532,186,153,602,478,778,744,303,669,548,704,325,336,706,990
294,632,856,907,454,875,173,856,386,318,238,985,680,503,730,385,128,571,708,764,530,347,807,512,109,976
461,265,952,225,244,397,626,511,238,516,577,706,576,857,285,348,159,576,704,504,521,510,807,877,406,823
884,183,182,452,352,457,805,778,392,773,223,718,554,363,834,437,428,895,873,360,815,885,788,425,750,663
379,495,430,185,438,301,871,589,129,269,748,665,263,952,951,873,569,786,662,439,129,530,673,689,678,322
470,782,216,400,780,717,974,311,372,225,345,482,216,165,166,642,835,938,437,263,344,134,380,664,430,584
680,129,628,575,920,668,545,132,273,250,369,866,952,886,396,601,612,242,763,847,216,250,760,674,526,228
712,752,173,415,599,106,194,137,481,103,461,674,316,942,346,575,778,997,505,885,980,806,381,109,851,990
170,803,680,164,304,993,682,722,545,894,704,527,977,240,159,594,889,160,381,727,901,774,529,470,522,659
826,933,994,513,409,313,342,357,119,564,341,340,284,408,284,408,719,337,667,329,220,288,714,949,135,716
191,819,539,838,233,978,563,201,309,609,512,848,102,617,770,616,688,346,428,648,902,733,783,328,392,404
266,404,620,194,310,360,800,329,572,470,790,546,791,408,820,890,839,322,830,996,512,766,448,603,358,961
544,569,202,228,212,849,447,337,278,932,885,337,156,235,925,231,884,394,639,528,346,643,294,491,796,712
619,819,483,222,732,526,412,859,861,974,639,524,273,664,406,198,844,358,866,269,501,395,983,949,993,301
206,193,916,289,841,257,772,230,274,410,970,147,288,453,453,564,718,657,740,849,676,749,697,329,801,307
397,250,363,700,571,495,509,812,509,676,709,135,937,235,185,379,679,187,257,228,412,500,551,234,889,629
144,881,664,222,966,792,348,682,443,490,631,940,693,554,160,621,529,821,658,559,761,554,518,496,290,685
208,758,840,871,386,369,515,729,283,781,348,661,526,700,975,580,979,400,654,636,558,633,824,967,472,953
496,436,220,518,334,673,182,685,851,609,245,145,339,279,865,802,344,132,260,668,891,902,339,606,316,288
989,510,185,289,798,593,542,152,129,977,346,769,474,910,530,623,380,739,608,280,428,687,469,527,945,352
686,347,454,178,951,567,527,964,148,912,995,821,697,467,168,393,602,184,927,192,556,996,639,970,223,767
449,965,368,936,829,608,308,367,851,737,390,181,817,247,531,898,742,199,613,797,132,301,667,429,228,433
680,305,118,278,459,706,477,694,400,772,553,188,141,764,693,883,889,718,400,465,183,493,220,300,190,450
814,132,514,110,549,929,135,925,665,592,315,274,550,350,997,540,149,222,581,253,740,677,858,575,744,579
367,894,956,869,642,858,642,660,267,376,942,464,340,509,446,823,198,878,477,610,759,699,929,838,610,713
501,480,443,628,992,789,765,964,606,322,927,341,276,822,641,420,139,871,681,138,231,945,837,284,429,948
358,542,357,719,391,375,941,361,149,588,268,251,332,243,468,769,387,899,580,794,836,282,946,542,755,700
788,178,734,450,944,334,421,710,437,746,129,136,981,439,445,279,509,259,162,230,444,884,768,220,725,368
099,707,717,681,136,489,613,457,697,309,203,180,129,513,127,896,431,676,980,608,728,462,520,606,648,739
895,721,786,604,558,287,647,683,351,603,406,607,435,501,728,191,760,361,235,448,851,319,311,495,519,592
393,391,320,153,109,573,328,211,564,872,235,285,362,758,873,462,140,911,254,288,215,728,924,697,767,179
611,904,362,177,732,333,613,689,341,374,878,224,985,161,404,333,224,369,197,858,355,516,272,289,957,672
696,498,255,423,467,762,205,948,365,392,464,345,552,821,837,537,859,643,448,732,257,638,244,466,727,483
465,646,488,541,653,262,821,303,304,207,715,858,142,204,404,843,184,665,467,451,535,482,453,466,499,324
734,165,613,316,619,363,188,955,795,661,505,940,602,399,628,934,240,941,290,123,553,230,792,373,478,373
608,196,582,419,454,301,743,320,203,769,615,646,318,423,841,853,619,931,853,144,325,792,965,124,532,107
561,780,185,235,379,229,740,784,823,887,367,454,170,472,149,643,734,169,305,905,621,933,380,179,698,553
707,243,630,722,293,135,304,921,645,620,202,216,438,951,580,754,365,894,340,625,735,466,662,856,451,533
701,775,960,354,635,295,580,812,774,725,328,838,479,732,932,267,913,100,264,541,695,186,707,199,370,968
637,607,883,328,653,399,694,456,107,347,744,262,921,642,851,309,337,365,827,982,459,324,175,373,559,852
589,154,152,296,790,564,150,207,482,646,523,588,682,811,136,498,269,894,427,160,865,878,238,657,977,841
119,548,165,254,249,883,458,133,140,190,717,248,112,645,196,847,641,997,240,536,824,417,724,299,347,836
802,470,756,139,989,156,979,349,939,810,519,817,956,353,585,293,135,841,719,976,424,404,642,115,441,902
896,783,806,618,785,350,533,131,557,466,833,505,223,931,324,199,322,161,897,840,144,214,514,794,152,581
282,761,620,614,691,295,749,987,370,749,826,207,311,660,516,965,986,756,774,324,143,539,312,811,695,177
459,509,169,431,370,845,165,979,985,170,837,583,619,674,571,211,322,491,595,567,787,945,357,351,383,855
627,251,767,796,305,184,354,761,279,802,340,840,124,344,113,777,797,216,556,334,388,800,815,366,548,755
930,818,819,895,993,480,751,159,982,900,664,403,880,199,242,105,642,297,358,617,987,177,955,126,578,870
751,783,757,690,335,790,438,460,800,506,921,783,443,100,678,635,325,870,778,555,822,934,986,489,774,409
455,344,724,108,986,644,221,443,434,281,849,985,327,215,223,110,878,939,243,413,996,877,976,200,397,606
144,115,577,885,265,912,873,139,762,187,347,557,275,472,274,730,156,301,756,591,399,300,285,568,829,358
183,289,901,453,171,985,255,650,653,339,571,962,269,541,174,355,298,588,782,174,279,199,537,446,835,959
192,962,703,260,648,631,607,255,711,356,956,717,942,602,934,934,565,760,379,638,291,780,339,707,511,200
470,940,190,355,194,391,119,955,287,142,347,481,512,413,754,131,391,994,275,762,421,171,693,219,653,879
579,960,763,822,366,913,160,803,814,707,326,339,847,235,878,398,235,278,575,340,137,616,370,305,925,690
319,619,932,755,668,734,590,109,496,757,329,597,259,783,428,637,327,708,285,549,582,636,875,772,961,853
756,229,135,609,766,315,531,194,333,379,893,728,135,790,397,770,749,819,534,357,155,680,631,703,105,313
637,444,584,734,322,310,603,257,639,201,607,673,472,669,670,131,516,436,227,753,158,249,349,835,442,784
503,584,420,600,916,425,279,798,146,260,788,346,896,415,712,325,323,412,954,558,665,699,750,569,298,549
451,874,241,560,667,562,622,659,547,582,743,223,623,732,685,814,502,499,523,870,595,785,459,372,263,227
826,934,790,633,247,880,295,958,980,857,800,375,675,912,204,739,623,711,509,895,223,398,577,368,412,318
323,806,224,375,960,993,492,768,797,125,282,236,826,867,773,470,228,530,808,189,589,243,991,783,971,116
437,878,613,110,919,528,105,898,445,536,781,351,658,983,434,399,767,755,767,186,956,600,707,753,954,170
960,709,714,533,533,297,976,128,729,933,849,808,138,923,203,625,994,821,993,382,365,574,769,132,172,300
177,855,674,624,265,809,328,337,979,406,197,957,118,273,494,400,995,902,783,182,961,683,514,394,388,761
946,705,772,510,968,698,487,363,271,840,456,388,974,230,758,255,532,403,894,963,455,219,594,337,678,430
481,904,666,350,246,446,684,852,713,181,804,310,257,300,153,466,854,465,976,131,893,561,783,857,176,864
861,467,510,674,237,800,983,259,929,455,548,311,405,707,250,971,696,911,409,958,186,831,139,913,219,805
239,820,719,510,712,483,473,875,442,473,531,538,954,921,484,107,531,398,306,293,654,942,356,769,663,354
480,169,214,569,929,991,944,560,214,290,625,888,481,133,520,849,099,310,775,779,389,810,709,103,300,681
426,741,646,524,859,220,301,714,879,932,864,257,576,905,213,565,857,832,953,801,714,355,184,297,971,178
820,671,477,134,278,695,711,406,380,494,876,139,831,731,548,592,147,970,602,468,307,372,367,982,909,849
907,243,146,803,837,118,243,662,126,894,197,415,613,704,123,435,763,769,851,468,511,555,714,692,641,428
310,591,323,797,461,431,519,599,783,196,713,599,806,156,814,309,637,369,516,216,276,462,583,954,607,736
146,309,731,337,356,878,986,900,579,711,170,670,939,642,395,241,616,133,126,810,519,631,345,542,706,244
552,367,858,466,671,603,762,788,733,759,796,769,148,565,244,130,317,178,475,720,646,200,257,272,164,416
810,465,543,402,226,127,343,525,154,780,110,388,326,799,941,451,334,837,965,702,300,226,289,119,411,099
363,639,406,465,281,600,923,786,176,429,347,300,730,279,824,178,878,284,919,436,728,847,398,148,513,292
472,872,595,144,460,593,526,511,936,893,864,685,185,133,523,393,197,488,445,915,105,131,217,637,183,496
326,554,234,540,439,619,598,345,558,410,322,848,433,393,406,949,485,815,455,113,697,994,101,308,600,426
102,708,307,917,311,422,523,604,958,099,407,345,592,356,341,899,367,754,766,915,461,834,456,339,812,663
937,529,213,319,254,311,540,523,447,889,959,569,333,167,215,250,242,183,579,914,777,885,620,380,115,628
433,822,345,638,377,903,227,741,320,613,835,870,202,131,265,536,202,709,493,336,900,257,716,854,948,905
685,740,138,540,978,667,365,558,993,763,588,101,158,435,810,314,316,636,432,201,546,747,234,575,311,268
661,892,217,171,296,995,474,822,839,579,692,989,233,963,226,303,612,582,491,559,283,387,517,812,828,357
764,572,443,856,559,234,576,975,240,461,651,946,319,180,976,225,373,524,941,349,657,428,448,891,369,946
750,684,940,881,181,980,197,336,451,571,365,655,991,437,977,442,584,485,161,393,154,546,469,981,210,450
743,854,461,524,264,787,188,821,779,452,551,124,973,529,275,992,156,333,391,502,670,417,192,688,206,812
883,750,919,295,552,367,902,699,545,953,562,264,790,644,863,832,872,424,715,230,830,122,231,957,159,557
194,191,276,618,274,433,579,183,895,142,832,153,114,295,593,745,649,303,187,609,778,515,317,128,691,870
602,493,823,770,120,534,191,223,973,248,153,601,462,106,768,658,971,728,823,245,923,643,177,413,517,248
113,547,553,621,466,640,440,647,813,815,635,497,274,755,987,174,325,550,577,460,876,652,850,396,276,651
318,307,698,723,183,533,687,966,601,920,706,887,650,208,242,532,625,620,697,575,637,322,168,469,397,670
866,178,370,333,844,414,157,894,804,649,156,651,524,251,714,331,197,756,513,544,667,871,299,865,577,641
182,236,962,392,599,269,595,152,712,489,296,347,599,599,702,777,589,915,831,794,786,684,149,587,785,124
270,828,564,319,811,893,836,664,390,220,291,519,233,661,967,334,892,430,279,521,435,167,576,221,795,908
985,533,892,676,670,885,476,859,730,335,490,208,831,120,459,561,916,460,965,579,116,941,354,427,906,685
979,806,151,787,798,443,785,310,114,418,945,845,841,916,830,485,968,633,956,794,154,401,996,935,153,776
626,100,992,974,414,855,940,421,759,413,625,648,195,390,750,154,100,105,951,919,877,591,811,295,431,739
847,289,659,672,897,416,946,184,152,642,197,418,684,594,618,164,528,842,833,181,388,240,245,400,686,218
485,479,406,526,131,844,716,411,706,112,669,468,892,726,174,926,675,458,649,727,830,646,172,626,608,923
267,211,484,359,793,400,282,309,194,359,742,922,996,686,835,923,813,524,306,888,753,905,624,387,366,444
838,852,289,907,722,383,442,793,860,556,990,121,619,735,890,479,179,589,427,939,177,326,121,990,761,415
562,394,131,126,465,613,272,476,811,575,266,619,188,829,442,503,144,659,891,530,729,993,369,204,455,832
383,592,709,554,899,648,527,263,376,331,742,391,554,644,636,625,932,376,662,394,820,726,162,103,401,802
657,985,350,404,199,610,517,319,332,186,319,774,114,433,874,969,913,438,992,320,988,535,938,592,483,907
505,210,426,542,886,356,347,618,888,310,755,848,303,374,509,546,133,150,364,173,161,846,981,325,254,792
541,735,179,525,208,209,678,269,702,278,867,466,628,749,296,173,532,887,841,745,370,820,465,665,620,641
710,638,573,907,987,877,712,911,429,539,893,827,493,688,334,323,723,854,314,721,753,679,776,103,789,563
930,750,756,814,958,902,145,956,597,218,877,699,675,585,146,107,846,215,375,127,397,620,887,359,314,250
121,755,265,969,859,143,128,370,770,937,652,137,229,697,525,503,774,392,729,563,647,262,310,441,541,864
256,353,792,415,881,685,474,857,225,755,186,783,479,104,900,479,615,759,462,273,698,388,287,997,247,996
990,362,936,264,382,280,733,180,278,235,995,743,953,810,166,726,566,938,960,960,396,304,346,134,321,620
496,638,744,876,833,965,725,373,714,838,437,331,474,357,708,147,385,125,453,329,304,616,604,768,459,343
145,767,228,631,781,748,752,185,279,363,937,586,738,470,208,982,237,757,239,265,873,370,104,864,454,961
271,848,734,177,381,388,690,452,995,795,533,752,838,899,650,503,713,345,434,539,779,693,639,873,797,837
885,634,536,900,234,592,283,704,963,666,333,666,685,799,264,182,614,108,536,801,568,113,296,353,480,569
172,285,218,668,745,601,706,545,753,305,856,631,232,495,590,340,736,799,743,137,895,588,276,543,500,361
905,755,717,436,380,216,638,397,116,211,759,492,148,836,259,505,926,133,344,371,750,506,144,364,752,508
664,983,715,382,748,819,865,848,699,298,361,886,785,682,767,245,446,458,955,933,662,587,887,653,743,691
943,654,950,529,831,822,158,927,574,694,596,792,832,428,691,244,573,458,899,388,528,364,329,334,753,183
481,524,728,518,932,979,260,916,691,143,660,767,635,727,275,244,489,525,145,153,132,149,880,266,245,603
894,378,698,766,910,459,675,847,110,524,371,593,751,265,345,145,493,781,649,479,992,476,889,137,937,368
798,152,289,410,445,899,459,698,815,232,168,924,906,226,139,365,436,551,433,485,708,474,519,735,433,443
601,475,274,782,236,269,879,632,672,558,560,901,458,140,186,286,978,386,962,911,490,371,757,770,831,722
201,713,488,484,815,814,509,574,181,559,980,633,738,784,484,662,331,294,819,177,287,574,307,663,479,153
210,653,569,114,213,152,970,388,899,295,755,201,742,142,723,516,616,322,266,248,909,287,710,141,925,213
264,973,539,464,882,317,526,767,756,635,882,389,632,463,463,183,631,126,882,928,123,149,403,641,695,862
529,496,227,700,330,737,138,185,366,821,643,109,530,933,489,798,494,229,907,304,527,771,967,658,629,310
559,540,936,651,619,601,228,354,129,844,631,204,490,170,281,822,896,403,675,453,474,971,851,979,732,772
191,526,401,467,105,568,522,673,506,939,117,472,696,177,715,739,575,640,348,527,963,624,811,842,853,771
105,760,186,106,577,100,927,543,656,431,842,406,433,320,600,130,689,609,643,305,691,300,284,400,719,429
303,392,784,477,721,893,551,349,767,802,355,354,319,671,727,120,719,428,219,312,111,934,729,518,773,925
331,893,220,944,383,713,403,848,643,185,560,115,221,475,570,131,563,772,819,942,464,472,466,217,434,161
837,702,965,203,146,688,583,731,228,463,982,449,731,514,584,733,691,604,303,516,486,683,142,738,924,806
539,279,775,671,173,679,550,741,698,994,169,506,674,354,512,675,725,854,514,708,981,954,393,237,255,451
475,817,507,770,949,916,775,473,271,715,585,369,629,723,333,713,332,663,896,190,273,111,614,179,397,216
553,374,546,727,504,306,590,669,538,585,501,827,604,784,739,959,606,860,388,528,712,289,161,314,693,510
260,551,990,187,647,651,327,596,737,883,756,721,774,273,831,907,641,339,307,703,943,663,271,276,575,439
685,925,918,954,634,735,550,466,571,687,493,269,914,989,961,361,592,642,344,683,523,858,248,584,767,652
820,346,808,236,765,942,575,453,535,963,807,861,538,869,863,249,465,497,449,401,663,643,997,835,112,409
217,374,565,220,830,645,160,491,476,349,512,420,213,224,771,499,389,189,110,448,385,692,630,424,236,735
578,705,565,899,864,668,445,212,258,489,117,492,243,895,454,567,931,774,905,222,722,790,634,428,633,573
303,529,181,853,365,672,340,101,507,984,520,808,934,709,456,527,881,428,309,579,153,746,775,638,562,323
504,228,402,953,337,908,408,149,308,726,187,103,821,870,996,541,465,309,451,932,348,270,834,167,720,856
704,221,518,830,580,900,365,265,627,552,558,603,928,805,421,349,452,873,809,765,849,707,449,279,178,961
686,124,463,262,297,271,251,320,304,977,198,477,597,924,347,776,948,188,955,355,941,961,772,444,827,378
443,222,728,780,848,756,259,273,923,432,986,251,745,706,759,683,752,786,249,780,813,384,317,914,656,653
985,272,545,110,157,176,783,816,779,978,541,575,883,963,859,495,891,925,961,308,858,234,302,203,465,864
948,363,418,474,203,632,710,711,709,409,399,619,301,749,280,780,126,462,538,483,306,483,823,620,579,121
961,522,680,796,206,598,450,730,889,541,721,463,842,428,599,769,308,640,921,368,578,700,450,179,898,973
541,963,952,261,292,510,160,967,887,516,244,616,980,911,886,643,794,627,921,543,666,346,140,252,862,806
566,404,808,233,692,475,618,336,226,134,469,247,439,318,733,225,948,376,824,349,578,324,189,171,595,951
467,728,879,810,327,163,570,864,950,949,448,577,881,722,604,501,526,601,772,720,996,473,941,997,899,960
739,580,738,686,895,822,558,409,566,174,722,537,831,321,430,167,165,362,787,167,978,179,823,675,169,397
506,421,771,323,153,523,388,556,516,238,295,281,719,901,444,383,721,175,819,659,102,769,580,385,674,505
794,978,439,649,292,635,587,139,424,267,787,898,369,669,287,250,381,740,371,814,596,756,196,223,795,512
761,586,610,748,558,548,776,786,551,872,708,748,735,389,806,571,615,629,391,150,525,829,942,662,181,821
711,551,402,920,272,910,541,371,253,464,241,861,627,754,954,334,142,729,523,715,911,485,208,465,621,727
734,277,255,595,321,184,213,904,163,121,762,954,435,719,247,547,881,237,305,498,799,807,484,170,209,889
997,138,967,224,126,289,563,873,366,347,969,671,748,588,491,954,689,818,104,803,493,120,179,736,924,113
645,316,368,696,320,426,493,522,298,572,569,136,101,171,769,461,562,501,720,695,821,994,725,711,138,614
254,161,311,568,100,616,628,161,668,376,119,229,109,709,566,417,368,396,188,400,646,763,548,402,130,360
777,414,465,121,774,846,117,392,543,965,482,211,374,605,383,946,172,843,638,892,461,338,407,197,896,511
963,960,456,840,912,933,705,613,289,437,783,148,191,951,832,449,939,716,925,874,295,203,115,853,306,170
694,463,806,445,266,124,937,594,654,881,213,966,226,121,209,840,408,842,830,111,275,492,446,575,389,378
213,907,144,590,920,740,843,309,915,299,746,758,968,371,773,121,606,688,795,634,236,819,191,585,539,316
582,269,927,898,778,673,395,132,557,463,515,800,578,866,830,309,365,247,903,361,950,292,251,856,962,147
718,599,331,340,154,319,143,111,581,707,228,115,228,672,679,552,745,652,616,954,616,371,611,722,974,630
756,686,206,606,907,731,560,733,662,761,653,151,758,639,295,648,205,152,765,899,197,530,666,784,246,751
533,750,705,953,752,427,554,202,850,417,167,848,563,475,326,298,152,785,570,737,971,545,231,488,471,700
394,879,973,709,580,801,620,674,317,929,314,554,643,336,785,331,313,240,273,301,484,878,122,540,401,455
875,245,346,966,887,553,890,329,541,314,799,784,536,731,261,297,356,237,685,338,742,401,785,141,567,357
711,585,653,548,107,393,448,349,361,116,299,694,769,274,475,161,989,818,484,716,891,431,431,924,335,169
676,608,249,541,351,929,800,147,502,704,546,316,933,679,244,722,411,926,424,526,446,819,129,248,701,888
517,555,280,481,956,957,831,728,367,189,257,896,431,213,269,487,446,545,653,807,972,692,556,453,356,280
682,965,536,843,498,769,709,784,508,215,751,290,759,832,214,769,643,103,660,833,684,563,648,377,982,133
658,303,984,896,173,333,382,276,760,441,636,741,628,942,719,671,887,908,824,285,921,202,410,345,285,844
244,649,538,380,837,174,473,480,613,222,698,785,966,456,504,381,869,407,347,252,913,868,628,271,192,727
386,320,450,172,937,732,910,564,814,125,739,508,886,183,989,292,405,893,173,235,401,297,530,730,995,910
142,609,159,628,754,779,529,246,698,297,622,608,273,988,694,474,303,640,848,452,941,711,896,151,278,146
561,534,367,502,737,556,283,637,278,638,195,276,851,765,118,574,668,167,690,747,574,556,615,373,639,485
633,860,597,890,790,298,369,885,984,703,709,980,301,529,877,668,343,584,560,214,907,119,264,337,273,641
203,689,731,330,920,261,141,107,365,609,823,650,333,563,893,374,190,756,820,839,790,623,854,979,777,318
914,570,535,798,980,329,517,877,684,357,282,888,537,292,730,398,871,587,448,447,425,692,247,583,200,765
598,543,799,636,871,113,187,431,848,619,377,224,646,523,195,153,993,156,401,443,119,466,928,735,223,106
384,306,764,101,843,528,175,721,120,546,907,587,948,413,530,654,122,478,325,110,372,487,406,668,655,970
297,296,482,831,822,410,678,232,335,290,463,308,645,550,534,812,297,918,390,837,722,264,748,266,426,124
862,257,767,453,617,936,745,671,919,742,874,199,727,600,666,294,622,669,788,726,303,443,764,325,365,699
148,867,244,984,771,435,311,763,158,593,740,339,913,592,244,698,370,829,608,584,486,969,210,379,638,571
879,433,228,353,901,742,634,410,625,770,250,840,674,784,779,418,780,161,815,126,645,726,432,155,925,695
973,641,765,395,833,284,300,556,984,141,189,509,651,469,840,246,231,639,107,289,211,829,153,660,624,882
876,647,657,550,427,336,564,862,719,436,978,843,584,444,474,124,476,725,787,307,274,745,510,965,783,570
169,859,590,903,595,443,624,763,189,977,200,139,383,747,833,126,790,243,258,399,513,846,909,795,534,400
727,213,400,443,985,568,383,481,530,925,617,691,942,425,487,111,112,705,762,714,994,501,167,259,484,527
811,635,509,154,128,955,920,675,213,628,957,285,315,967,407,253,244,425,439,496,733,650,992,589,504,608
188,712,925,719,235,925,978,199,967,231,893,325,847,699,853,353,279,570,321,217,125,100,546,537,216,430
407,595,935,832,979,451,936,565,207,262,253,192,739,939,738,689,549,881,229,870,748,598,214,448,786,559
739,638,967,491,129,700,902,951,525,667,599,463,259,452,575,829,522,350,992,794,477,691,218,191,912,522
696,546,566,736,816,568,296,751,580,771,602,368,470,812,465,822,229,495,631,630,179,828,820,764,671,895
964,257,252,985,784,202,787,314,967,347,307,596,209,253,252,411,865,917,379,451,666,944,203,489,873,436
401,303,778,473,498,679,480,258,476,760,361,434,479,544,279,663,873,291,502,950,308,163,190,781,576,743
258,160,228,425,195,533,440,702,906,452,719,453,579,789,384,958,411,474,875,653,887,990,779,547,693,586
771,185,124,870,773,276,198,261,390,330,536,581,756,263,712,459,708,301,843,927,765,331,142,165,267,465
292,569,878,359,219,927,314,692,283,100,625,571,729,625,655,483,648,176,391,661,197,707,226,754,334,958
957,968,658,512,855,455,579,432,976,466,942,406,173,680,929,351,740,674,130,608,827,467,903,852,755,180
555,896,659,188,744,954,262,912,632,883,670,609,389,689,318,208,924,184,114,217,321,564,444,896,495,404
731,346,696,900,165,838,545,483,435,837,414,988,538,390,221,145,478,597,443,466,973,776,744,209,624,223
829,567,342,743,296,466,947,337,498,515,964,790,832,313,467,647,104,655,163,545,157,616,996,933,470,993
163,306,551,244,215,854,458,760,491,457,122,276,489,393,980,344,844,770,699,681,291,842,953,527,795,838
916,846,525,960,777,453,833,412,607,595,939,806,875,536,951,328,269,768,273,839,870,309,858,892,579,137
659,599,253,905,168,746,954,636,947,597,790,638,594,104,142,796,734,805,100,493,575,175,875,898,268,254
429,524,769,435,255,861,948,607,390,459,898,771,256,110,915,890,626,770,969,971,459,288,275,265,529,384
534,928,519,267,769,119,267,995,450,413,579,437,841,502,774,850,392,192,865,249,832,855,352,704,238,988
459,755,168,992,782,099,616,299,779,784,457,969,261,529,330,125,457,211,207,500,543,967,315,900,916,187
301,498,795,795,801,362,203,424,633,597,420,831,188,158,565,777,163,561,544,475,702,553,386,303,511,813
776,783,755,903,161,591,779,177,224,364,156,459,120,602,772,485,377,608,323,986,701,726,278,741,451,625
322,731,937,989,621,508,154,283,530,473,934,750,657,260,994,939,716,249,711,304,945,510,657,496,213,424
253,124,866,929,550,155,756,238,816,732,821,989,741,618,252,285,707,562,443,379,865,829,297,488,762,415
414,961,722,962,931,143,869,239,442,600,572,793,964,523,544,537,850,507,249,693,186,737,533,162,559,145
609,755,622,793,744,919,239,270,948,641,448,660,790,887,646,416,279,603,639,780,129,146,507,783,899,492
637,617,602,365,259,289,114,325,511,195,128,804,961,175,723,938,712,723,401,329,811,621,378,659,918,522
553,858,414,408,764,682,327,725,487,808,506,192,285,236,996,904,729,645,110,869,584,512,360,540,573,663
581,867,634,881,144,767,407,164,681,675,312,949,520,249,919,609,651,498,516,736,304,835,340,370,522,974
648,871,770,395,791,498,444,113,641,526,110,589,833,430,906,323,761,173,917,635,878,128,165,288,352,322
358,756,766,862,919,588,840,253,700,758,797,391,287,613,241,434,164,412,201,454,393,129,494,252,213,693
215,258,362,862,522,217,186,990,950,125,809,338,925,565,940,365,797,621,210,672,858,111,731,567,627,195
652,861,550,212,627,752,462,401,405,736,666,943,655,110,234,225,855,830,783,564,235,867,452,528,227,681
422,473,441,293,218,507,506,844,411,670,750,342,833,473,838,178,603,523,944,731,664,709,106,696,260,639
280,701,399,183,218,345,789,129,678,155,272,112,388,285,275,516,543,173,786,355,329,600,444,551,150,925
124,764,160,931,646,230,950,723,198,526,340,987,850,984,902,201,168,882,351,842,673,537,521,599,473,784
129,588,933,158,390,306,304,242,283,990,239,110,323,703,926,387,573,687,725,709,483,458,827,927,342,261
634,844,110,775,306,637,434,845,609,751,459,315,318,996,541,409,766,988,784,759,533,592,207,732,401,195
556,435,902,811,663,997,909,463,380,317,144,782,266,492,678,401,883,341,245,277,445,184,290,598,477,419
249,255,905,560,694,890,586,660,486,206,535,985,923,541,754,140,457,360,405,613,831,344,282,192,813,397
489,606,239,816,666,849,942,735,387,529,198,478,967,763,883,384,661,426,198,496,707,632,137,106,883,694
599,959,505,244,867,834,776,473,373,720,747,442,396,252,675,673,769,517,847,450,756,521,726,437,412,605
904,141,707,830,904,134,753,274,944,847,804,461,666,819,242,402,818,926,667,130,919,385,344,462,935,184
554,631,252,128,902,489,941,546,215,683,305,514,510,304,291,350,296,326,603,654,897,426,798,415,690,753
492,879,587,373,364,229,794,416,627,615,845,929,651,618,119,236,801,503,118,967,563,782,473,290,646,327
373,117,557,280,622,493,919,220,685,228,690,826,923,445,183,677,654,901,554,784,710,228,539,456,826,985
403,687,481,492,655,726,524,700,763,380,366,499,687,393,728,549,955,557,302,203,964,277,602,374,290,992
695,631,277,135,889,383,502,717,274,742,288,887,258,593,635,483,663,402,220,883,285,686,351,393,906,504
154,494,124,773,409,857,913,411,928,723,679,409,189,691,763,734,369,723,563,785,635,695,973,951,212,958
866,680,939,815,704,266,827,138,115,816,285,548,381,848,282,705,141,888,514,996,686,155,948,372,582,422
162,476,551,837,620,132,594,603,221,434,264,749,902,793,902,610,494,346,099,284,760,904,283,974,326,688
480,291,488,653,158,125,129,806,236,595,824,701,633,585,216,336,980,822,938,811,435,359,240,544,211,318
756,236,602,405,387,488,951,827,972,544,870,569,128,425,608,173,977,449,274,128,405,735,207,309,911,921
329,658,369,650,403,681,574,386,548,461,909,980,257,974,744,253,877,948,140,136,963,331,696,840,123,370
144,440,284,281,659,349,556,920,196,573,407,579,363,261,666,931,133,194,807,160,566,220,260,396,333,173
301,952,696,541,274,365,620,349,439,273,945,290,520,571,870,221,809,192,708,378,969,646,916,708,207,604
603,192,259,503,615,429,894,747,852,472,518,222,328,255,874,480,859,932,710,267,588,101,612,992,912,155
643,417,604,424,356,642,898,645,394,654,609,554,360,285,178,129,946,669,458,151,315,739,680,919,791,804
844,454,182,109,924,788,635,605,532,279,829,104,368,197,185,219,667,779,911,471,693,650,349,728,931,108
311,656,623,383,707,181,180,311,674,391,870,586,394,840,527,937,672,480,757,669,286,736,585,677,729,231
398,472,207,156,787,190,382,358,660,159,451,211,821,257,546,680,939,626,962,565,204,304,228,869,443,152
245,543,304,416,889,461,746,100,303,099,789,559,605,390,604,863,951,967,912,155,232,584,226,195,227,973
340,705,880,581,434,203,183,627,661,241,828,842,853,462,307,187,258,510,187,522,289,426,477,426,848,255
657,227,255,293,383,221,580,579,783,746,710,166,211,633,803,729,796,439,589,252,539,254,484,508,450,909
191,976,587,886,172,468,164,287,608,817,578,965,855,239,619,751,521,249,243,622,307,129,751,217,199,820
960,678,331,347,670,812,271,140,759,742,922,229,958,678,860,157,240,186,749,786,813,535,257,559,318,173
837,831,591,863,922,517,758,705,663,143,099,610,230,363,132,729,719,131,997,368,490,857,376,177,570,467
824,124,571,545,339,458,776,241,459,147,959,731,414,708,573,272,915,610,628,414,958,358,377,205,601,202
515,536,899,225,187,417,229,141,108,685,547,962,869,627,888,293,200,516,834,749,190,674,650,521,519,849
258,383,362,833,178,370,610,642,252,638,558,592,649,956,739,317,360,941,831,931,936,892,539,571,622,617
105,332,701,498,746,526,943,431,937,334,708,497,911,197,817,409,870,229,888,314,406,634,170,614,499,295
438,309,603,542,507,774,745,902,570,985,636,672,669,499,776,648,384,827,626,136,600,811,483,918,399,348
227,648,178,753,162,742,194,435,833,809,355,740,102,425,247,382,579,902,442,294,325,551,268,349,232,100
790,951,219,136,301,328,565,642,862,321,229,304,480,236,324,450,959,259,724,476,986,604,982,484,966,208
560,910,654,100,817,969,687,321,319,786,649,726,106,385,970,958,545,934,619,346,111,363,314,341,987,588
411,855,492,417,295,726,342,659,932,163,405,386,496,952,573,752,216,516,994,993,709,352,842,602,247,525
355,151,691,117,742,489,317,688,663,917,411,531,831,921,446,626,139,909,357,666,844,180,579,540,684,233
169,685,981,545,197,311,435,140,569,726,850,399,205,302,302,620,640,539,848,156,959,883,927,151,488,129
827,388,426,494,588,319,591,953,567,484,878,465,619,715,818,786,733,876,413,924,304,543,571,194,260,613
272,134,171,200,274,755,235,977,650,620,926,196,667,120,912,419,293,216,526,485,480,716,162,583,888,726
225,210,549,229,749,195,687,158,131,356,140,793,290,182,378,609,700,642,930,964,865,644,435,826,741,917
421,688,676,170,889,786,474,995,740,990,797,289,876,286,143,575,612,883,906,397,441,108,560,917,655,479
452,379,456,540,843,717,184,742,647,112,949,352,419,947,544,643,132,679,865,851,692,799,812,539,672,247
577,689,362,341,755,678,298,548,466,338,935,201,291,106,661,782,493,503,309,882,281,920,131,594,207,233
972,173,592,955,794,162,602,850,351,433,227,157,962,738,518,291,718,680,173,741,619,292,117,808,154,392
101,662,150,645,992,646,489,250,332,249,462,432,427,706,642,112,947,526,181,780,793,397,403,391,669,856
934,110,864,262,711,362,192,526,505,345,382,641,760,438,398,825,269,966,852,490,360,354,762,712,899,572
980,747,181,487,399,501,982,709,927,815,798,940,748,986,195,851,316,450,341,298,679,595,711,506,467,962
316,692,106,790,417,303,129,349,728,705,656,474,125,182,824,826,172,634,457,768,556,502,802,331,753,549
186,803,475,783,436,607,724,513,412,634,482,576,798,819,761,729,569,273,928,735,906,671,855,792,692,311
183,685,487,692,322,347,955,291,358,778,890,769,906,473,206,535,919,177,783,437,270,349,425,576,566,844
313,569,682,338,770,258,662,647,902,676,988,716,635,916,542,239,512,717,464,137,651,996,101,161,459,845
481,740,256,306,172,812,970,676,827,321,858,268,117,617,979,573,861,420,795,369,221,541,682,700,422,613
211,632,372,415,680,378,609,722,793,409,913,199,116,196,284,574,993,961,431,177,414,907,862,694,588,590
770,902,293,645,504,603,151,117,299,167,215,141,765,621,909,677,936,317,193,935,183,812,236,423,732,392
943,550,792,244,516,532,425,775,772,561,491,704,363,383,191,217,812,907,806,990,923,546,396,153,167,128
843,538,918,720,483,884,841,268,623,874,779,326,987,734,950,849,197,633,503,854,721,127,237,593,706,478
971,793,459,775,876,962,637,601,474,750,173,599,462,968,590,699,697,437,865,589,638,345,703,122,788,389
686,308,466,233,399,546,167,123,938,377,922,861,623,248,702,951,187,238,804,387,392,239,808,578,879,159
485,712,340,696,761,685,187,252,280,147,783,536,650,805,663,186,922,437,540,662,196,419,691,119,387,897
589,638,305,982,203,762,972,661,642,481,190,894,223,641,990,228,314,350,578,554,424,989,376,737,768,845
787,992,979,714,393,944,333,771,784,951,485,692,874,242,360,325,566,473,204,830,507,882,454,496,617,691
747,176,814,271,743,893,213,787,434,316,255,729,388,651,982,967,635,418,733,297,820,871,979,266,499,808
525,783,837,866,971,923,613,968,908,259,538,186,627,743,253,365,417,804,464,372,962,117,177,567,628,895
317,185,276,751,847,127,782,988,978,807,430,271,186,442,472,124,946,540,732,842,799,980,468,396,615,669
391,288,399,679,326,742,338,578,156,099,609,767,883,907,944,520,251,772,174,549,115,772,994,810,512,614
724,208,450,113,677,972,231,132,924,309,320,336,986,129,571,353,968,278,600,659,559,475,771,574,555,290
982,155,585,520,278,548,718,211,605,489,749,202,213,447,762,302,593,467,123,213,334,567,161,780,571,682
239,220,866,225,403,928,436,378,852,340,464,599,413,564,870,107,619,878,172,479,962,777,920,252,254,336
823,774,147,113,297,947,726,851,125,788,757,200,581,586,640,602,764,631,770,189,368,475,575,239,628,293
880,330,851,584,954,679,788,299,510,452,891,651,659,142,240,671,302,867,942,395,167,767,620,550,817,466
361,836,472,623,152,536,121,214,453,669,495,287,531,325,921,345,981,970,197,334,746,322,432,404,853,981
579,522,842,643,332,233,256,669,410,183,951,245,192,337,828,622,860,157,648,410,599,850,226,533,380,307
154,737,878,622,713,255,583,153,642,561,908,991,176,332,346,691,211,690,381,282,106,701,965,747,124,698
940,469,769,364,841,397,872,246,886,521,474,447,251,548,122,162,156,801,984,818,612,824,839,610,987,745
157,287,810,754,424,715,321,912,372,527,652,972,819,479,897,320,151,950,946,542,381,829,397,314,349,914
830,492,668,491,441,951,363,209,244,804,862,348,572,832,631,742,670,160,803,557,133,438,749,128,209,337
596,573,165,332,887,351,179,834,630,476,225,265,839,333,809,882,189,308,414,338,753,323,211,625,796,574
445,730,923,489,239,961,794,231,935,969,240,302,390,346,214,251,226,343,720,564,933,328,713,855,764,945
434,165,210,283,211,645,315,617,531,830,178,244,769,661,980,498,893,570,617,402,240,106,509,723,720,563
781,401,572,235,634,406,717,202,912,855,965,297,646,513,811,114,374,579,992,504,362,244,868,629,321,616
976,911,179,351,590,746,269,270,214,184,803,496,144,499,824,174,853,800,522,507,958,874,712,341,565,905
578,383,662,817,662,806,476,887,692,504,179,449,453,195,542,148,786,860,807,179,153,236,506,355,310,561
464,865,338,254,937,308,867,233,176,528,396,601,801,280,571,765,235,288,647,752,142,782,337,234,881,888
494,577,283,658,596,480,134,926,571,963,985,585,136,699,186,192,614,424,666,168,991,932,969,821,541,335
174,528,201,440,581,725,539,686,379,735,893,709,808,872,966,157,340,928,727,233,444,575,380,355,168,802
743,191,243,890,960,697,214,117,527,135,688,521,724,292,164,500,979,350,134,925,758,870,689,329,351,614
540,548,365,485,809,422,616,561,182,570,117,501,238,126,383,439,781,228,278,501,455,312,489,131,349,870
321,427,538,578,870,804,433,929,178,847,625,521,624,996,879,797,489,161,350,514,744,911,570,419,523,232
740,224,117,146,277,710,625,869,949,935,122,178,180,361,432,557,366,851,118,996,579,391,430,248,267,143
516,942,305,358,227,532,238,945,447,768,770,967,255,200,348,178,280,810,991,238,945,774,916,817,618,206
306,470,141,523,964,205,757,965,455,884,517,225,438,619,408,540,278,156,319,629,977,526,750,539,900,649
621,415,570,918,284,524,409,914,644,995,133,472,247,108,804,330,322,887,315,141,601,915,483,475,193,340
548,880,849,139,953,289,936,620,687,504,505,606,279,638,666,996,209,860,678,727,210,430,187,941,650,958
223,412,535,757,583,692,717,308,824,234,759,474,921,339,690,604,613,440,294,771,463,930,908,486,794,120
491,510,945,364,929,428,884,595,581,144,836,165,830,986,337,825,581,534,776,277,293,143,924,870,404,736
688,140,828,250,219,689,476,552,192,440,737,226,833,114,719,224,892,946,332,397,823,126,294,811,940,838
817,167,112,539,297,272,153,310,883,712,816,881,492,712,405,419,113,149,975,190,228,723,521,978,332,429
230,964,521,803,923,174,637,958,545,329,202,146,980,374,691,817,666,257,438,769,237,851,432,645,411,588
420,318,786,922,509,882,668,768,277,699,690,401,528,372,739,146,148,599,660,754,688,182,683,579,157,305
339,466,811,550,233,336,502,762,916,253,796,200,360,362,104,732,850,412,456,848,549,471,767,671,860,592
993,110,997,133,228,809,497,337,725,964,604,576,934,526,821,193,265,592,430,985,619,712,718,572,372,425
685,997,588,669,789,571,575,366,698,564,968,174,476,442,464,270,840,599,341,527,862,951,667,157,580,832
272,113,114,361,635,669,491,388,784,370,537,872,865,147,141,660,147,825,553,702,467,130,546,610,510,500
527,589,335,390,205,254,512,476,154,671,596,478,826,463,862,323,165,102,380,825,224,987,582,504,566,313
407,915,855,433,854,537,663,421,328,887,917,458,931,726,400,113,571,419,254,578,667,596,722,207,237,191
284,471,518,670,612,833,686,578,104,701,502,808,693,858,223,221,847,222,887,142,779,906,656,454,321,940
534,203,511,572,900,512,627,471,950,588,339,438,858,405,399,555,232,585,968,278,795,289,598,543,260,979
951,978,711,108,113,108,215,320,632,791,597,107,511,455,601,566,795,689,797,563,945,454,157,587,409,489
904,228,684,408,808,389,719,791,276,598,538,610,498,858,610,919,099,679,748,767,964,476,265,403,822,492
891,920,809,244,481,917,694,284,608,296,460,600,251,321,170,676,357,579,655,440,628,295,750,904,459,407
165,715,706,443,592,262,917,537,119,787,852,414,754,630,282,400,134,850,278,810,951,414,771,483,298,682
523,196,974,254,256,573,150,708,133,780,899,508,991,207,333,244,458,301,952,663,987,520,131,611,628,110
360,106,928,233,421,134,554,926,200,910,722,989,944,849,132,974,561,140,976,941,888,959,951,305,851,920
713,188,724,291,501,411,916,364,255,238,285,782,619,320,204,457,152,435,487,584,767,681,637,800,674,667
486,185,117,684,440,583,201,203,151,190,734,788,827,557,628,753,717,546,933,359,635,436,433,778,622,209
923,501,573,898,981,402,914,441,245,428,486,929,401,215,196,888,475,971,163,719,122,353,490,392,337,697
463,497,273,220,407,316,435,888,994,289,885,189,233,701,883,558,717,199,560,366,137,615,923,798,911,816
936,370,588,334,733,360,660,935,158,165,988,924,761,307,253,121,179,617,546,916,925,283,557,168,226,836
534,863,872,674,313,618,480,503,144,624,762,588,862,495,683,524,510,918,241,629,297,621,394,984,606,328
768,788,297,516,264,590,469,168,104,718,797,517,339,153,116,255,226,601,504,662,370,110,486,581,623,399
922,389,672,131,428,462,612,239,453,661,423,331,228,823,445,616,130,259,789,338,386,619,211,768,140,858
238,205,598,523,104,670,605,961,719,768,263,925,775,653,877,677,620,563,776,863,241,543,234,797,538,633
804,742,911,210,794,528,207,899,886,429,394,728,361,810,446,365,639,332,484,765,190,322,766,146,273,839
630,222,277,717,989,539,896,825,664,427,342,880,806,345,721,984,389,388,774,595,282,510,308,592,390,330
741,394,694,113,584,689,358,134,492,246,824,435,651,375,783,117,101,904,380,749,249,480,231,845,630,467
358,234,982,930,470,164,228,552,272,992,545,742,945,778,145,795,452,279,552,570,603,617,436,266,268,210
139,176,673,979,947,470,405,220,743,662,800,716,751,552,297,587,616,883,565,205,340,588,902,854,450,642
364,864,747,719,483,636,735,789,146,189,715,689,571,983,293,527,813,819,193,993,620,228,184,465,463,944
285,496,675,555,529,131,128,275,831,940,592,748,200,828,339,484,654,584,516,699,577,732,504,461,345,894
912,260,335,781,766,937,826,968,179,546,661,703,369,568,303,598,218,285,435,625,915,150,530,119,687,716
326,389,672,624,468,375,529,176,707,436,728,279,153,282,759,417,956,284,121,395,248,174,759,586,181,536
290,838,383,878,370,926,159,447,274,979,589,590,677,475,205,322,817,892,960,380,277,187,859,681,389,699
325,222,439,118,906,131,215,451,532,291,529,384,336,616,395,937,420,390,288,723,636,127,184,377,688,681
511,483,886,926,691,600,806,949,665,265,334,948,929,234,140,832,131,410,845,644,566,818,713,770,526,575
877,178,598,751,780,343,448,897,747,801,294,494,594,932,638,757,938,452,206,990,365,920,510,326,518,121
573,830,627,438,833,276,945,694,806,382,592,187,638,664,509,968,588,891,754,572,915,331,587,266,583,192
158,196,592,365,500,617,861,380,550,924,411,579,156,356,215,888,121,130,274,861,172,554,297,622,234,108
616,396,671,101,833,916,576,767,691,395,111,610,650,820,530,606,728,997,268,945,728,416,655,279,888,856
108,754,246,560,927,616,130,830,827,934,631,981,713,808,763,325,814,783,799,367,373,835,610,423,195,394
327,651,239,122,571,952,232,147,968,113,932,400,344,467,726,256,436,785,204,413,634,143,178,900,402,435
840,453,676,288,246,746,591,790,472,732,779,713,597,974,234,969,136,811,456,116,870,381,307,598,454,806
962,125,496,629,166,533,340,775,705,196,443,672,680,523,967,143,766,620,383,917,298,149,179,738,715,987
434,305,350,321,915,597,391,928,759,413,161,750,655,689,878,489,773,788,440,735,688,204,911,737,231,458
632,525,492,959,225,782,451,692,724,651,442,997,205,380,385,653,902,776,805,445,834,753,468,786,419,788
529,596,983,353,356,867,215,629,283,344,922,403,099,905,399,702,340,120,361,457,110,447,386,120,995,270
421,499,754,164,509,462,418,582,178,598,216,449,208,270,277,337,584,436,376,860,177,695,443,314,908,392
303,215,788,703,274,191,655,606,103,882,214,317,326,638,345,694,714,702,973,448,707,244,141,456,619,652
453,504,682,840,720,617,155,831,717,267,276,301,657,333,740,263,343,517,209,946,173,449,994,426,918,666
924,126,442,583,156,350,194,566,628,294,501,575,678,344,456,300,960,185,270,281,644,330,385,962,352,673
410,937,952,617,473,359,446,637,220,886,158,851,689,505,375,225,870,870,933,622,433,806,527,199,743,136
617,600,852,162,914,726,526,920,325,857,199,356,816,305,334,225,297,806,896,237,883,709,837,748,972,950
693,840,560,199,716,837,670,597,212,929,649,561,781,543,233,859,522,296,674,577,480,863,483,824,418,666
443,298,757,195,711,819,311,910,995,158,493,151,787,237,703,233,391,596,331,862,309,820,366,802,204,132
738,760,592,377,768,750,518,769,281,701,952,186,273,762,558,895,436,821,503,491,666,361,718,478,202,178
406,680,610,485,372,552,295,422,593,497,871,431,959,153,525,265,329,882,126,320,419,278,970,132,214,373
760,567,892,632,394,241,268,176,777,557,978,897,252,835,835,866,267,740,553,648,150,175,320,302,747,945
887,381,990,896,119,436,972,895,554,272,283,599,184,445,725,743,970,253,344,337,321,786,382,701,508,246
522,162,158,544,422,102,204,569,931,368,685,245,324,573,808,646,970,371,987,374,357,758,329,956,380,398
471,235,217,585,819,698,624,949,172,188,771,979,869,386,846,204,176,815,437,761,567,106,284,435,901,346
846,126,279,159,407,652,775,347,984,377,243,200,221,857,132,903,439,408,551,201,628,758,932,536,961,414
145,573,197,208,908,134,261,938,341,788,796,197,312,413,325,696,257,941,845,577,937,336,630,938,532,621
187,691,746,364,140,281,279,149,566,158,294,510,298,181,715,118,380,236,425,357,472,624,432,599,962,114
616,711,888,222,982,969,256,567,651,117,878,608,727,373,816,735,559,227,286,441,603,875,918,356,287,105
799,301,673,584,657,906,674,157,566,444,651,635,200,367,460,148,470,495,914,499,422,137,727,868,903,714
476,412,808,292,982,539,704,935,127,143,180,212,578,271,229,823,685,463,739,622,893,356,453,847,406,236
388,339,417,441,767,456,739,132,621,482,241,428,156,978,465,955,728,938,766,950,141,494,331,516,305,776
198,442,687,497,975,909,326,374,221,158,882,634,759,726,891,128,536,820,985,159,222,876,178,831,777,847
102,410,294,344,233,927,840,833,779,554,426,503,899,444,209,419,191,712,161,510,786,561,673,830,565,125
296,179,881,522,390,794,765,468,547,437,346,216,187,676,665,213,516,265,861,465,481,400,166,297,730,291
358,323,703,748,984,992,482,259,605,835,904,306,849,193,852,798,181,651,266,959,974,307,408,312,959,362
571,176,283,102,288,458,514,722,218,831,174,677,171,477,595,245,437,697,644,112,237,211,431,141,741,162
525,496,702,393,922,903,914,878,182,942,268,506,825,794,214,869,811,388,257,850,990,145,491,578,848,536
585,765,333,639,970,465,810,344,169,449,460,889,754,597,596,359,526,508,426,820,405,676,323,108,268,815
404,217,672,342,950,711,780,310,912,142,681,579,834,458,524,261,449,485,148,690,928,970,552,309,379,685
823,784,814,103,652,144,424,118,121,410,548,621,879,637,417,876,250,166,505,336,147,699,673,519,221,846
940,281,466,722,338,801,910,388,404,632,645,215,395,330,869,120,729,991,700,180,829,126,144,812,196,496
780,893,348,282,172,376,653,857,759,834,597,534,119,194,694,779,781,857,934,495,625,825,262,833,663,996
355,620,323,175,568,487,686,186,719,990,362,924,112,512,626,876,320,411,659,792,232,764,237,810,558,596
100,270,958,469,264,390,983,199,409,108,747,449,875,706,262,774,947,283,422,279,202,794,197,632,664,990
556,119,900,541,306,812,389,546,788,112,362,824,870,864,103,501,237,758,901,185,170,929,329,874,330,357
158,580,853,256,845,246,751,483,712,501,828,901,210,475,238,826,752,319,337,580,821,455,538,621,756,985
276,415,683,167,694,610,117,749,367,918,823,316,574,655,940,925,919,575,814,751,693,194,130,169,153,568
214,288,564,826,677,510,427,949,211,966,696,356,233,501,586,676,198,954,207,449,873,356,699,752,223,391
898,196,308,278,485,281,375,190,942,788,801,513,412,551,368,791,257,925,359,284,927,922,624,854,389,608
297,877,611,865,292,781,851,668,137,710,933,988,424,136,400,287,499,575,556,976,896,455,558,745,305,127
394,242,935,791,895,61