自動mention系Twitter botを復活させる

以前にいくつかTwitter botを作っていて。

どちらも「フォロワーの発言から特定の語が含まれているTweetを拾って、replyする」という機能を持つもの。
これを実現するために、フォローされたら自動でフォロー返しをして、GET statuses/home_timelineを定期的に叩いたり、 User streams でフォロワーの発言を収集していた。
しかし数ヶ月前に@genkidashitebotがAPI Key Restrictionを食らってしまい、ちょっと調べてみたところfollow/unfollowの自動化は禁止事項となっているらしい(知らなかった)。

となると、自動フォロー返しなどをせずにフォロワーの発言を拾ってくる必要がある…。無理なんじゃないかとしばらく諦めていたけど、REST APIを駆使することである程度実現できるのでは、と思い至った。

GET followers/listを使うとfollowersのuser情報に付随して最新のtweetが1件含まれて返ってくる。これらを集約すればfollowersのタイムライン的なものが得られる。ただ、これは1回あたり200件が取得上限で、cursorを使って遡っていっても3000 followersくらいいるとそこまでで15分の枠を使い切ってしまう。

followersが多いときに使えるのがGET followers/idsGET users/lookup。followers/idsではfollowersの「IDだけ」を1回で最大5,000件取得できる。ので数万followersいても数回のリクエストですべて取得できる。そしてusers/lookupにはそのIDをカンマ連結したパラメータでリクエストすることで最大100件のuser情報を得ることができる。


ということで、これらを使えば「全followersのIDを取得し、それらのuser情報と最新のTweetを1件取得」できるので、これを定期的に実行することで(連続でTweetされたときなど ある程度の取りこぼしは出るものの)フォロワーの発言だけで構成されるタイムラインを得ることができる。

そしてusers/lookupなんかはcursorを含まない独立のリクエストになるので(可能か否かだけで言えば)並行で処理することもできる。
ので「定期的にフォロワーのタイムラインを取得し、特定の条件に合致したもの自動でmentionを送る」という機能を持つフレームワーク的なものを書いた。goで。

で、それを使って停止された自動mention系botを再始動させてみた。

Goで全裸 というのは以前に書いていたのだけど、形態素解析kagome がけっこうアップデートされていたのでそれに合わせてちょっと直した。外部辞書も利用できるようになっているようなのでいつかは NEologd 辞書を使うようにしたりして全裸にする精度を上げたい気持ちはある。


botともherokuで動かしてみていて、経過観察しているところ。このまま放置していても動き続けてくれるといいなぁ…。

#isucon 2015で優勝しました

第5回 ISUCONの本選に、参加しました。第1回のときの出場メンバー(@さん、@さん)での「fujiwara組」。

ISUCON5 本選リアルタイムフォトレポート【更新終了】 : ISUCON公式Blog


結果はなんと、昨年に引き続き優勝!!


自分はアプリケーション側の担当ということで コード書いていこうと思っていましたが、今回あまり出来ることが無く、並行で作業もしづらかったので@songmuさんと@fujiwaraさんにコード書くのをお任せし、横から口を出す係になりました。



まぁでも一応わかる限りのことは横から指摘して 正しく早く実装をするお手伝いは出来たつもりなので幾らかはチームに貢献できたと思うし、とにかく優勝できてよかったです。ここからまた精進していきたいと思います。

出題の皆様、運営の皆様、テコラス様、ありがとうございました!



賞金でたくさんアイドルに会いに行こうと思います。

Perl6での6記号プログラムの作りかた

先日、

の2つの記事でPerl6の記号プログラムを紹介したけど、その作り方については何も言及していなかったので ちゃんと書いておこうと思います。

おさらい: Perl5における記号プログラムの基礎

Perl5における記号プログラミングの手法は古くから確立されていて、 記号だけのPerlプログラミングの基本原理 - JPerl Advent Calendar 2010 Sym Track の記事にも全貌が載っていますが、要するに「任意のプログラム文字列を排他的論理和(XOR)を使って生成し、それを拡張正規表現を利用してevalする」という方法です。

   01100000  => 0x60 ('`')
^) 00100001  => 0x21 ('!')
-----------
   01000001  => 0x41 ('A')

このように2つの文字のASCIIコードのXOR演算によって別の文字を生成できるので、記号文字同士のXOR演算でアルファベットや数字を生成することができ、最終的に実行したいプログラムなど 任意の文字列をすべて記号だけで表現することができます。

で、その生成した文字列を実際に実行するための手段として拡張正規表現(?{ code })という記法があります。

'' =~ /(?{ print "Hello" })/;

のようにして書くと (?{ ... })内のコードが実行され"Hello"が出力されます。これを

'' =~ '(?{ print "Hello" })';

と書くこともでき、つまり記号だけでこの右辺の文字列を生成すれば、任意のプログラムを実行することができる、という仕組みです。


記号プログラムでアスキーアートを作れる Acme::EyeDrops というCPANモジュールでも、この手法が使われています。
ただし、Perl 5.18以降では拡張正規表現の使用に制限ができており、use re 'eval'プラグマを宣言しないと実行できなくなっています。とても残念です。


Perl6での記号プログラム実現方法

で、Perl6ではこれはどうなるか、というと 1.「排他的論理和で任意の文字列を生成する」に関してはPerl5と同様に出来ました。ただし演算子が変わっておりPerl5でのXOR演算子^は one Junction を生成する演算子となっています。

http://docs.perl6.org/language/operators#infix_%5E

で、上記ドキュメントには明記されていないけど どうやら文字列の排他的論理和~^という演算子で実現できるようでした。
こっちには書いてありますね。

http://design.perl6.org/S03.html#Symbolic_unary_precedence

ちなみに~^""で文字列のビット反転が取れるらしいですが、実際に使ってみるとprefix:<~^> NYIとエラーを吐いて死にます。Not Implemented Yet!!


そして 2.「拡張正規表現によるeval」について、こちらは正規表現の書き方・仕組みが大きく変わっている影響で使えなくなっているようでした。

'' ~~ /{ say "Hello" }/

のような書き方でblock内のコード実行は出来るけれど、文字列に置き換えることは出来ないようで。


で、別の手段を使う必要がある… ということで某soozyというSlackグループで尋ねたところ、以下の方法を教えていただきました。

::('&EVAL')('say q{Hello}');

::というのがグローバルのstash的なもの?で、ここに対して文字列でシンボルを参照できる仕組みがあるようで。"dynamic symbol lookup" というsyntaxだそうです。

http://doc.perl6.org/language/5to6#%26_Sub

これを使うことで文字列からPerl6の"EVAL"関数を呼び出すことができ、ここに任意のプログラム文字列を渡すことでeval実行することができます。
なので、"&EVAL"とプログラム文字列を記号から生成することができれば任意のプログラムを記号だけで表現できる、ということになります。

こうして作られたのが1つめの記事で書いた記号Hello worldになります。

::('!{.(?'~^'.~!)~'~^')^.^^'~^'?!^?('~^'??)!{')('!?}}~~(!^~{~))(.{~('~^'))?^?.).(?.}?)().!~'~^'~!.?}?~.^.{?!)~}!).'~^'}!!.~(}(!?}~{!}).(('~^')^(^.(.)~?!.()!})?)')

前半の::('!{.(?'~^'.~!)~'~^')^.^^'~^'?!^?('~^'??)!{')の部分が::('&EVAL')を表していて、後半の('!?}}~~(!^~{~))(.{~('~^'))?^?.).(?.}?)().!~'~^'~!.?}?~.^.{?!)~}!).'~^'}!!.~(}(!?}~{!}).(('~^')^(^.(.)~?!.()!})?)')部分が"Hello, world!".sayというコード本文になっています。分かりやすいですね。

6つの記号に制限する

さて、任意の記号プログラムが作れることが分かったので、あとは使う記号の種類を減らすことを考えます。Perl5の場合は、' = ~ ( ) ^ .と最低限必要な7種類の記号だけを使って実現できていました。

Perl6においては、前述の通り記号プログラミングに最低限必要なのは: ' ( ) ~ ^の6種類だけとなります。この6種類の記号の組み合わせで任意の文字列を生成することができれば、6種類の記号だけで任意のプログラムを記号だけで書けるわけですが…

use v6;

my @chars = <: ( ) ~ ^>;
my %dict;
for @chars -> $c1 {
    %dict.push: $c1 => ($c1);
    for @chars -> $c2 {
        %dict.push: $c1~^$c2 => ($c1, $c2);
        for @chars -> $c3 {
            %dict.push: $c1~^$c2~^$c3 => ($c1, $c2, $c3);
            for @chars -> $c4 {
                %dict.push: $c1~^$c2~^$c3~^$c4 => ($c1, $c2, $c3, $c4);
                for @chars -> $c5 {
                    %dict.push: $c1~^$c2~^$c3~^$c4~^$c5 => ($c1, $c2, $c3, $c4, $c5);
                }
            }
        }
    }
}

for %dict.keys.sort({ .ord }) -> $c {
    next unless %dict{$c}:exists;

    '\x%02X %s => %s'.sprintf(
        $c.ord,
        $c ~~ /<[\x20 .. \x7E]>/ ?? qq{"$c"} !! '(?)',
        %dict{$c}.pick.sort({ .ord }).join(' ')
    ).say
}
say %dict.keys.elems;

のように試してみると、

\x00 (?) => ) ) ~ ~
\x01 (?) => ( ) ) )
\x08 (?) => ( ( ( ^ ~
\x09 (?) => ) : : ^ ~
\x12 (?) => ( :
\x13 (?) => ( ( ) :
\x1A (?) => ) ) : ^ ~
\x1B (?) => ( ) : ^ ~
\x20 " " => ) ) ^ ~
\x21 "!" => ( ) ^ ~
\x28 "(" => ( : : : :
\x29 ")" => ) ) ) : :
\x32 "2" => ( : ^ ~
\x33 "3" => ) : ^ ~
\x3A ":" => ( ( ) ) :
\x3B ";" => ( ) : ~ ~
\x44 "D" => ( ( : ~
\x45 "E" => ( ) : ~
\x4C "L" => ( ) ) : ^
\x4D "M" => ) : ^ ~ ~
\x56 "V" => ( ~
\x57 "W" => ( ( ) ~
\x5E "^" => ) ) : : ^
\x5F "_" => ( ) ) ) ^
\x64 "d" => : ^ ~ ~
\x65 "e" => ( ) : ^
\x6C "l" => ( : : : ~
\x6D "m" => ( ( ) : ~
\x76 "v" => ( ) ) ^
\x77 "w" => ) ^ ~ ~
\x7E "~" => ) ) : : ~
\x7F (?) => ( ) : : ~
32

と32種類の文字しか生成できません。これでは'&EVAL'を作ることもできない… ので、使う記号種類は6のままで別の文字列を作る方法を模索するしかありません。

で、前述のperl5での7記号プログラミングに似た手法で"0"を作ります。それが~(^(''~~''))です。これは、'' ~~ ''正規表現マッチでTrueを生成し、そこにRangeを作るprefix operator^を適用させて0..^1というRangeを作り、それを文字列として評価することで"0"を作る、ということになります。

dd (''~~'');     #=> Bool $var = Bool::True
dd ^(''~~'');    #=> Range $var = 0..^1
dd ~(^(''~~'')); #=> Str $var = "0"
dd ~(^2);        #=> Str $var = "0 1"
dd ~(^3);        #=> Str $var = "0 1 2"

Rangeの文字列表現はスペースでの連結になるようなので、「0からTrue(つまり1)までのRange」の文字列表現として"0"が生まれるようです。ちなみにPerl6ではPerl5と違ってTrue(真値)の文字列表現は"True"になるので、ここから"1"を作るようなことはできません。数値コンテキストとして評価する+演算子を使って~(+(''~~''))のようにしないと"1"が作れません。ここでは"+"を使うことができないので、つらい。

さて、"0"を作れることは分かったので それを使える前提として改めて何種類の文字を記号から生成できるか、を見てみると…

\x00 (?) => ( ( 0 0 : :
\x01 (?) => ( ) ^ ^ ~ ~
\x02 (?) => ( 0 : ^ ~
\x03 (?) => ) 0 : ^ ~
\x08 (?) => ( 0 0 ^ ~
\x09 (?) => ) 0 0 ^ ~
\x0A (?) => 0 : ^ ^ ~ ~
\x0B (?) => ( ) 0 : ^ ^
\x10 (?) => 0 : : ^ ~
\x11 (?) => ( ) 0 ^ ~
\x12 (?) => ( ) ) : ~ ~
\x13 (?) => ) ) ) : ^ ^
\x18 (?) => ( ) ) 0 ^ ^
\x19 (?) => ) 0 0 0 ^ ^
\x1A (?) => : ^ ~ ~ ~
\x1B (?) => ( ) : ^ ~
\x20 " " => ) ) : : ^ ~
\x21 "!" => ( ) : : ^ ~
\x22 """ => ( 0 : ^ ^
\x23 "#" => ( ( ) 0 :
\x28 "(" => ( 0 0 ~ ~
\x29 ")" => ) 0 0 ~ ~
\x2A "*" => 0 : ^ ~ ~ ~
\x2B "+" => ( ) 0 : ^ ~
\x30 "0" => ( ( 0 ~ ~
\x31 "1" => ( ) 0
\x32 "2" => ( : : : ^ ~
\x33 "3" => ) 0 0 : ^ ~
\x38 "8" => ( 0 : : ^ ~
\x39 "9" => ( ( ) 0 ^ ~
\x3A ":" => 0 0 : ~ ~
\x3B ";" => ( ) 0 0 :
\x44 "D" => ( ( : : : ~
\x45 "E" => ( ) 0 0 : ~
\x46 "F" => ( 0 ^ ~ ~
\x47 "G" => ( ( ) 0 ^
\x4C "L" => ( ( ( : ^
\x4D "M" => ( ( ) : ^
\x4E "N" => 0 0 0 ^ ^ ~
\x4F "O" => ( ) 0 ~ ~ ~
\x54 "T" => ) ) 0 : ^
\x55 "U" => ( ) 0 : ^
\x56 "V" => ( 0 0 : : ~
\x57 "W" => ) ) ) ^ ^ ~
\x5C "\" => ( ) ) 0 : ~
\x5D "]" => ) 0 0 0 : ~
\x5E "^" => ) ) 0 0 ^
\x5F "_" => ( ) ) ) ^
\x64 "d" => 0 0 : ^ ~ ~
\x65 "e" => ( ) : ^ ~ ~
\x66 "f" => ( 0 : : ~
\x67 "g" => ) 0 ~ ~ ~
\x6C "l" => ( 0 0 : ~
\x6D "m" => ) 0 0 : ~
\x6E "n" => 0 : : ^ ^ ^
\x6F "o" => ( ) 0 0 0 ^
\x74 "t" => 0 : : : ~
\x75 "u" => ( ) 0 : ~
\x76 "v" => ( 0 0 : : ^
\x77 "w" => ( ( ) 0 0 ^
\x7C "|" => ( 0 : : : ^
\x7D "}" => ( ( ) 0 : ^
\x7E "~" => ^ ^ ~ ~ ~
\x7F (?) => ( ) ^ ^ ~
64

と、64種類まで増やせました、がこれでもまだ"A"を作ることもできない…。ここに出てこない文字をさらにどうにかして作り出す必要があります。数値コンテキストとして評価する演算子が使えないので"1", "2", "3"が使えてもそこから"4", "5", "6", "7"を作ることもできなくて、つらい。

「"4"」

ここで思い出すのが::('&EVAL')でdynamicにsymbolを参照する方法。'&EVAL'は呼べなくても他のものなら呼べるのでは…!と。なんと偶然にも、"Mu", "Num", "VM"などの文字は先ほどまでの方法で作れます。ということで編み出したのが

~(::('Num')('1*2**2'))

という方法。::('Num')でNumクラスを参照、これはそのままコンストラクタを呼ぶような形で利用できるので、括弧で文字列を渡して数値を生成することができます。ただしどんな文字列でも受け付けられるわけではなく.Numで数値としてparseできるような文字列でなければならなりません。単純な足し算や掛け算の式はダメ。
しかしどうやらexponentials(指数)を使う表現として特殊な記法が用意されているようです。

http://design.perl6.org/S02.html#Exponentials

所謂 6.02\times10^{23} のような形式を表すために"6.02*10**23"という形式の文字列はサポートされているらしい。"1", "2", "*"の文字はここまでで生成できているので、これを利用して、"1*2**2"という文字列から"4"を作り出すことができる!!


ということで"4"を使うことができるようになると、無事に"\x00"から"\x7F"までのASCIIコードをすべて表現することができるようになります。
あとは"\x80"より上の範囲、マルチバイト文字列が含まれる場合を考慮する必要がありますが、これはすべて"\x3042"のような形で表現するよう変換してしまえばすべてASCII範囲内で収まるので問題ありませんね。

これで任意のプログラムを6種類の記号だけを使った等価なプログラムに変換することができそうです。やったー!!

作ったもの

というわで、この方法で任意のコードを6種類の記号プログラムに変換するモジュールを作っておきました。ご自由にお使いください。

perl6なので6種類の記号だけでプログラムを書く

Perl6で記号Hello worldする - すぎゃーんメモ という記事を書いたところ

というブコメをいただいたけど、あの記事では適当に生成したので 11種類もの記号を使っていて まだちょっと多いかな、という感じがした。

ので最大限に使う文字種類を減らして、6種類の記号だけでHello worldを書いてみた。

::('('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~':'~^')'~^'~'~^'('~'~'~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^(~(^(''~~'')))~^'~'~^'('~^':'~^')'~'('~^':'~^'^')((~(^(''~~'')))~^'('~^':'~':'~^'('~^(~(^(''~~'')))~^'~'~'^'~^':'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'~'~^'('~^'^'~^':'~'^'~^')'~^'~'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^(~(^(''~~'')))~^':'~'('~^(~(^(''~~'')))~^'~'~^':'~':'~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'~'~^'('~^(~(^(''~~'')))~^'^'~'('~^(~(^(''~~'')))~^':'~^'~'~':'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~'('~^(~(^(''~~'')))~^'~'~^':'~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'('~^')'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'('~^':'~^'~'~^(~(^(''~~'')))~'^'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~'('~^'^'~^'~'~^(~(^(''~~'')))~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~'^'~^')'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~(~(^(''~~'')))~^'~'~^':'~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'('~^'^'~(~(^(''~~'')))~^'~'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'('~^'^'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~^'^'~':'~^'~'~^'('~^(~(^(''~~'')))~'^'~^':'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'('~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'~'~^':'~^(~(^(''~~'')))~'^'~^(~(^(''~~'')))~^'('~'~'~^(~(^(''~~'')))~^':'~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^'('~^':'~'~'~^':'~^'('~^'^'~')'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~':'~^'~'~^'('~^(~(^(''~~'')))~'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'^'~'^'~^'~'~^':'~^'('~(~(^(''~~'')))~(~(^(''~~'')))~^'~'~^'('~^':'~'^'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'~'~^':'~^(~(^(''~~'')))~^'^'~^')'~'^'~^'~'~^':'~^')'~^(~(^(''~~'')))~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'~'~^'('~^':'~^(~(^(''~~'')))~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^'('~^':'~'~'~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^(~(^(''~~'')))~^'^'~^'('~'('~^'^'~^(~(^(''~~'')))~(~(^(''~~'')))~^':'~^'('~^'~'~'('~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'~'~^')'~^(~(^(''~~'')))~^'^'~'^'~^':'~^'('~^'~'~'('~^':'~^(~(^(''~~'')))~^'~'~':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^'^'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^(~(^(''~~'')))~^'^'~^'('~^'~'~')'~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'~'~^':'~^(~(^(''~~'')))~^'('~'('~^':'~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~':'~^(~(^(''~~'')))~^'~'~^'('~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~(~(^(''~~'')))~^'('~^':'~^'~'~'^'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~'^'~^':'~^'('~^'~'~'('~^(~(^(''~~'')))~^')'~':'~^(~(^(''~~'')))~^'~'~^'('~'^'~^'('~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'^'~^'~'~^':'~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'~'~^'^'~^(~(^(''~~'')))~^')'~^':'~':'~^'~'~^(~(^(''~~'')))~^'('~'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~'~'~^':'~^'^'~^'('~'('~^':'~^'~'~^')'~'('~^(~(^(''~~'')))~^':'~^'~'~'('~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~(~(^(''~~'')))~^')'~^'~'~^':'~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'^'~^':'~^')'~^'~'~'('~^(~(^(''~~'')))~^'~'~^':'~'^'~^':'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~(~(^(''~~'')))~^':'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'~'~^'^'~'('~^')'~^(~(^(''~~'')))~(~(^(''~~'')))~^'('~^':'~^'~'~'('~^':'~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~(~(^(''~~'')))~^'~'~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^')'~'~'~^')'~^(~(^(''~~'')))~^'^'~':'~^(~(^(''~~'')))~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^'~'~^':'~':'~^'('~^'~'~^')'~'~'~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^')'~^(~(^(''~~'')))~^'~'~^':'~'^'~^'('~^':')

https://gist.github.com/sugyan/8505d2602965967c7a9b

これでperl6で実行すると"Hello, world!"が出力されます。

"(", ")", ":", "'", "^", "~"の6種類の記号だけで任意の記号プログラムが書ける、はず。
Perl6すごい。

FizzBuzz

という要望もあったので書いてみた。

::((~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'('~'~'~^')'~^'('~^':'~'('~^'~'~'~'~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~^(~(^(''~~'')))~^'('~':'~^'^'~^'(')('('~^(~(^(''~~'')))~^':'~':'~^(~(^(''~~'')))~^'('~^'~'~':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^'('~'~'~^(~(^(''~~'')))~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~^':'~'^'~^')'~^':'~^'~'~':'~^'~'~^'('~^(~(^(''~~'')))~'('~^'^'~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~':'~^'('~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^(~(^(''~~'')))~^'~'~'('~^')'~^(~(^(''~~'')))~':'~^'~'~^'('~^(~(^(''~~'')))~'('~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~'^'~^(~(^(''~~'')))~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~^':'~^'~'~'~'~^')'~^(~(^(''~~'')))~^'^'~'~'~^':'~^'('~^(~(^(''~~'')))~'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'('~'('~^'~'~^'^'~^':'~(~(^(''~~'')))~(~(^(''~~'')))~^'('~^'~'~^':'~'^'~^'('~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'~'~^'('~^'^'~^':'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'~'~^(~(^(''~~'')))~^':'~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'('~^'^'~'('~^')'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~(~(^(''~~'')))~^'^'~^'('~'('~^(~(^(''~~'')))~^':'~^'~'~'('~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~':'~^'~'~^'^'~^'('~'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~'~'~^':'~^(~(^(''~~'')))~^'('~':'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~'^'~^')'~^':'~^'~'~'~'~^'^'~^':'~^')'~':'~^(~(^(''~~'')))~^'('~^'~'~'^'~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~'~'~^':'~^'^'~^')'~'~'~^':'~':'~^'('~^(~(^(''~~'')))~^'~'~'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^':'~'~'~^':'~^')'~^'^'~'~'~^':'~(~(^(''~~'')))~^'('~^':'~^'~'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~^'('~'~'~^'^'~^':'~^')'~(~(^(''~~'')))~':'~^(~(^(''~~'')))~^'~'~^'('~'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'^'~'^'~^')'~^'~'~^':'~'^'~^'('~^(~(^(''~~'')))~'~'~^'('~^(~(^(''~~'')))~^':'~':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^'^'~'~'~^')'~^':'~^'^'~(~(^(''~~'')))~^'('~^'^'~':'~^(~(^(''~~'')))~^'('~^'~'~'('~^':'~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~':'~^'('~^'^'~^'~'~(~(^(''~~'')))~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~^'~'~^'^'~(~(^(''~~'')))~^'~'~^'('~^':'~'('~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'('~^'^'~^':'~^(~(^(''~~'')))~^'~'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'('~^':'~^(~(^(''~~'')))~^'~'~'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~(~(^(''~~'')))~^'~'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^'^'~^':'~(~(^(''~~'')))~^'~'~^')'~^'^'~(~(^(''~~'')))~^'~'~^'('~^':'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^'^'~^':'~')'~^'^'~^'~'~^(~(^(''~~'')))~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~^':'~^'~'~^(~(^(''~~'')))~^'('~(~(^(''~~'')))~^':'~^'~'~^'('~'^'~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~')'~^'^'~^'~'~^':'~^(~(^(''~~'')))~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~(~(^(''~~'')))~^'('~^'~'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~^':'~'('~^'~'~^':'~^(~(^(''~~'')))~'^'~^'('~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~':'~^'^'~^'~'~^'('~(~(^(''~~'')))~^'~'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~^')'~'('~^(~(^(''~~'')))~^':'~^'~'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^':'~^'^'~'~'~^'^'~^')'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^(~(^(''~~'')))~^':'~'~'~^':'~^')'~^'('~':'~^'~'~^(~(^(''~~'')))~^'('~':'~^'('~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'~'~^':'~^'('~^'^'~(~(^(''~~'')))~^'('~^'~'~^'^'~(~(^(''~~'')))~^':'~^'~'~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~^'('~'^'~^'~'~^':'~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'('~^':'~^'~'~^(~(^(''~~'')))~'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'^'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^')'~'('~^'^'~^(~(^(''~~'')))~'~'~^':'~^'('~^(~(^(''~~'')))~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~^'('~'('~^':'~^'^'~^'~'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^')'~(~(^(''~~'')))~^':'~^'('~^'~'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'('~^'^'~')'~^':'~^'~'~^'^'~'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~'('~^'~'~^(~(^(''~~'')))~^':'~'('~^'^'~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'~'~^':'~^')'~^'^'~':'~^'~'~'~'~^'('~^(~(^(''~~'')))~^':'~'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'('~':'~^'~'~^')'~^'^'~'~'~^':'~'~'~^':'~^'('~^(~(^(''~~'')))~'('~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~':'~^'~'~^')'~^'^'~(~(^(''~~'')))~'~'~^'('~^':'~^(~(^(''~~'')))~'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^':'~'^'~^'~'~^':'~^')'~'^'~^(~(^(''~~'')))~^'('~'~'~^'('~^':'~^(~(^(''~~'')))~'^'~^'('~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'^'~^')'~^'~'~^':'~'('~^(~(^(''~~'')))~^'^'~'~'~^'('~^(~(^(''~~'')))~^':'~'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'('~'~'~^'^'~^':'~^'('~'~'~^'^'~^(~(^(''~~'')))~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~^':'~'('~^'~'~^(~(^(''~~'')))~^':'~'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^':'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'('~^'~'~^'^'~^':'~':'~^'('~^(~(^(''~~'')))~^'~'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^':'~^'^'~'^'~^')'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^(~(^(''~~'')))~^'~'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~^'('~'('~^'~'~^(~(^(''~~'')))~^':'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~^'~'~^'^'~^(~(^(''~~'')))~^':'~'('~^(~(^(''~~'')))~^':'~^'~'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~':'~^(~(^(''~~'')))~^'('~^'~'~'('~^':'~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'~'~^')'~^'^'~^':'~^(~(^(''~~'')))~'~'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^':'~^')'~^(~(^(''~~'')))~'~'~^'('~^':'~^(~(^(''~~'')))~'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~'('~^'~'~^':'~^'^'~'^'~^(~(^(''~~'')))~^':'~^'~'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~(~(^(''~~'')))~^':'~^'~'~^'('~'^'~^':'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'^'~^'('~^'~'~^':'~(~(^(''~~'')))~^')'~^'('~':'~^'('~^'~'~^(~(^(''~~'')))~'('~^'^'~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'~'~^'^'~^'('~^':'~')'~^'('~^(~(^(''~~'')))~'~'~^':'~^'('~^(~(^(''~~'')))~':'~^'('~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'~'~^':'~^'('~^'^'~'~'~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^(~(^(''~~'')))~^')'~':'~^'('~^(~(^(''~~'')))~^'~'~'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~'~'~^'^'~^':'~^'('~')'~^'^'~^'~'~^':'~^(~(^(''~~'')))~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~(~(^(''~~'')))~^':'~^'~'~^'('~':'~^'('~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'~'~^'^'~^'('~^':'~(~(^(''~~'')))~^'~'~^')'~^'^'~(~(^(''~~'')))~^'('~^'~'~^':'~':'~^'^'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'~'~^'^'~^':'~^'('~(~(^(''~~'')))~^')'~^'('~(~(^(''~~'')))~^':'~^'~'~^'('~':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^'('~'~'~^'('~^'^'~^':'~')'~^(~(^(''~~'')))~^'('~':'~^'('~^(~(^(''~~'')))~^'~'~'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~':'~^'('~^'^'~^'~'~'('~^'~'~^'^'~^(~(^(''~~'')))~'('~^':'~^'~'~^(~(^(''~~'')))~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^':'~^'^'~'~'~^':'~^'^'~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~(~(^(''~~'')))~^':'~^'~'~^'('~'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^')'~'('~^(~(^(''~~'')))~^'^'~'~'~^':'~^(~(^(''~~'')))~^'('~':'~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~'^'~^'('~^':'~^'~'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~^'('~':'~^'~'~^(~(^(''~~'')))~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'^'~^'('~')'~^'~'~^':'~^'^'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~^'('~':'~^'('~^'~'~^(~(^(''~~'')))~'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~':'~^')'~^'^'~^'~'~'~'~^':'~'~'~^(~(^(''~~'')))~^':'~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^'('~^':'~')'~^'~'~^':'~^'^'~':'~^'~'~(~(^(''~~'')))~^':'~^'('~^'~'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~^'('~'^'~^')'~^':'~^'~'~(~(^(''~~'')))~'~'~^'('~^':'~^(~(^(''~~'')))~':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^'('~':'~^')'~^'^'~^'~'~'('~^(~(^(''~~'')))~^'^'~'~'~^':'~^(~(^(''~~'')))~^'('~'('~^'^'~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'~'~^':'~^'^'~^')'~'^'~^'('~^(~(^(''~~'')))~':'~^'('~^'~'~^(~(^(''~~'')))~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~^'('~'^'~^'~'~^'('~^':'~'^'~^(~(^(''~~'')))~^')'~^':'~^'~'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~':'~^(~(^(''~~'')))~^'~'~^'('~'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'('~^'~'~^':'~^'^'~'~'~^'('~^(~(^(''~~'')))~^':'~'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'('~')'~^(~(^(''~~'')))~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'^'~^'~'~')'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~':'~^(~(^(''~~'')))~^'('~^'~'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^'^'~^':'~(~(^(''~~'')))~^'~'~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~^':'~'('~^(~(^(''~~'')))~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'~'~^')'~^':'~'~'~^':'~^(~(^(''~~'')))~^'('~'^'~^':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~'^'~^(~(^(''~~'')))~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^')'~^':'~^'~'~')'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^(~(^(''~~'')))~^'('~^':'~^'~'~':'~^'('~^'~'~^(~(^(''~~'')))~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'('~^'^'~':'~^'^'~^'('~^'~'~':'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'~'~^(~(^(''~~'')))~^')'~^'^'~(~(^(''~~'')))~^'~'~^'('~^':'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^':'~^'^'~'^'~^'~'~^'('~^':'~')'~^(~(^(''~~'')))~^'('~':'~^'('~^(~(^(''~~'')))~^'~'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~^'('~'^'~^'~'~^'('~^':'~(~(^(''~~'')))~^'('~^')'~(~(^(''~~'')))~^'('~^':'~^'~'~'('~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~'~'~^'('~^':'~^'^'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~':'~^(~(^(''~~'')))~^'('~^'~'~':'~^'^'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~')'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~'^'~^'('~^(~(^(''~~'')))~(~(^(''~~'')))~^':'~^'('~^'~'~':'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~'~'~^'('~^':'~^'^'~(~(^(''~~'')))~^')'~^'~'~^'^'~'~'~^':'~^'('~^(~(^(''~~'')))~':'~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~':'~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'~'~^(~(^(''~~'')))~^'('~'('~^':'~^'^'~^'~'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^(~(^(''~~'')))~(~(^(''~~'')))~^'('~^'~'~^':'~'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^':'~'~'~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'('~^(~(^(''~~'')))~'('~^'^'~^(~(^(''~~'')))~'('~^(~(^(''~~'')))~^'~'~^':'~':'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'~'~^(~(^(''~~'')))~^')'~^'^'~':'~^'('~^'^'~^'~'~'~'~^':'~^'('~^(~(^(''~~'')))~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^'^'~^':'~':'~^'^'~^'~'~^'('~(~(^(''~~'')))~'('~^'~'~^':'~^(~(^(''~~'')))~'^'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~')'~^'^'~^'~'~^':'~')'~^'('~^(~(^(''~~'')))~'('~^':'~^(~(^(''~~'')))~^'~'~'^'~^':'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'~'~^':'~^'('~^'^'~')'~^'~'~^':'~^'('~':'~^'~'~^'('~^(~(^(''~~'')))~'^'~^':'~^'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~'~'~^':'~^'^'~^'('~'('~^')'~^':'~^'~'~'~'~^':'~^'('~^(~(^(''~~'')))~':'~^'('~^'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~')'~^'^'~^'~'~^':'~(~(^(''~~'')))~^'('~^')'~':'~^(~(^(''~~'')))~^'~'~^'('~(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'^'~^':'~^'('~')'~^'^'~^'~'~^':'~(~(^(''~~'')))~'('~^'~'~^(~(^(''~~'')))~^':'~'('~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'^'~'~'~^':'~^')'~^'^'~(~(^(''~~'')))~'('~^':'~^(~(^(''~~'')))~'^'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^':'~^'~'~')'~^'~'~^':'~^'('~'('~^'~'~'~'~^(~(^(''~~'')))~^')'~^(~::('~'~^~(^(''~~''))~':'~^~(^(''~~''))~^'~'~^'('~^')'~')'~^':'~^'~')(')'~^~(^(''~~''))~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^~(^(''~~''))~^':'~^'~'~'^'~^':'~^'~'~^'('))~^'('~^':'~'^'~^'('~^':')

Perl6で記号Hello worldする

一番簡単なHello worldです。

::('!{.(?'~^'.~!)~'~^')^.^^'~^'?!^?('~^'??)!{')('!?}}~~(!^~{~))(.{~('~^'))?^?.).(?.}?)().!~'~^'~!.?}?~.^.{?!)~}!).'~^'}!!.~(}(!?}~{!}).(('~^')^(^.(.)~?!.()!})?)')

普通に実行できると思います。

$ cat hello.pl6
::('!{.(?'~^'.~!)~'~^')^.^^'~^'?!^?('~^'??)!{')('!?}}~~(!^~{~))(.{~('~^'))?^?.).(?.}?)().!~'~^'~!.?}?~.^.{?!)~}!).'~^'}!!.~(}(!?}~{!}).(('~^')^(^.(.)~?!.()!})?)')
$ perl6 hello.pl6
Hello, world!

String.uptoは引数によって挙動が違う

という呟きがあって。たしかに実行してみるとそうなる。

irb(main):001:0> ("\x00" .. "\x7f").to_a.size
=> 128
irb(main):002:0> ("\x00" .. "\x80").to_a.size
=> 58

RangeでASCII文字列を指定すると128種類のものが出てくるのは分かる。けど"\x80"までにするとなんで58に?

irb(main):003:0> ("\x00" .. "\x80").to_a
=> ["\u0000", "\u0001", "\u0002", "\u0003", "\u0004", "\u0005", "\u0006", "\a", "\b", "\t", "\n", "\v", "\f", "\r", "\u000E", "\u000F", "\u0010", "\u0011", "\u0012", "\u0013", "\u0014", "\u0015", "\u0016", "\u0017", "\u0018", "\u0019", "\u001A", "\e", "\u001C", "\u001D", "\u001E", "\u001F", " ", "!", "\"", "#", "$", "%", "&", "'", "(", ")", "*", "+", ",", "-", ".", "/", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]

どうやら"9"までで止まってしまい、その次にくるはずの":"から先が無くなっている模様。何故…?
と思ってソースコードとかを追いかけてみた。

Rangeのto_aはEnumerableのもので、これはRangeに定義されたeachを回しているに違いない、ということで見てみると range.cにrange_eachという関数がある。

https://github.com/ruby/ruby/blob/ruby_2_2/range.c#L768

ここの中では始点と終点の型によって処理が幾つかに分かれているらしい。fixnumやsymbolの場合は特殊な処理をするようになっているらしいが、文字列が始点にある場合に通る行には

	    rb_block_call(tmp, rb_intern("upto"), 2, args, each_i, 0);

という行がある。どうやらString.uptoを使って列挙していくようになっているようだ。
確かにRange使わずにString.uptoでも同じような現象が起きている。

irb(main):004:0> "\x00".upto("\x80").to_a
=> ["\u0000", "\u0001", "\u0002", "\u0003", "\u0004", "\u0005", "\u0006", "\a", "\b", "\t", "\n", "\v", "\f", "\r", "\u000E", "\u000F", "\u0010", "\u0011", "\u0012", "\u0013", "\u0014", "\u0015", "\u0016", "\u0017", "\u0018", "\u0019", "\u001A", "\e", "\u001C", "\u001D", "\u001E", "\u001F", " ", "!", "\"", "#", "$", "%", "&", "'", "(", ")", "*", "+", ",", "-", ".", "/", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]

で、string.cのrb_str_uptoという関数を見てみると…

https://github.com/ruby/ruby/blob/ruby_2_2/string.c#L3485

    /* single character */
    if (RSTRING_LEN(beg) == 1 && RSTRING_LEN(end) == 1 && ascii) {
        ...
    }
    /* both edges are all digits */
    if (ascii && ISDIGIT(RSTRING_PTR(beg)[0]) && ISDIGIT(RSTRING_PTR(end)[0])) {
        ...
    }
    /* normal case */
  no_digits:
    ...

という具合に、(1)「始点と終点がともに1文字のASCII文字の場合」という場合と(2)「始点と終点が数字(と見なすことのできる文字列)の場合」という場合と (3)それ以外の場合、と分かれている。
なので"\x00".."\x7F"の場合は(1)の分岐に入るし、"\x00".."\x80"だと(3)の分岐に入ることになる。
(1)の中では単純にascii codeの値がインクリメントされていくが、(3)の中では次の値を.succによって決定されているようだった。

ここで、String.succの動きは やはり文字列がアルファベットか数字か、など様々な条件で異なる。

instance method String#next (Ruby 2.2.0)

数字でもアルファベットでもないascii codeの場合は(1)のようにインクリメントするのと変わらないが、数字(と見なせる文字列)の場合は

irb(main):005:0> "9".succ
=> "10"

と、"9"の次は":"でなく"10"となる。これが終点の文字列より長くなってしまっているためにuptoのループがここで終わってしまう、ということのようだ。

irb(main):006:0> "\x40".upto("\x80").to_a
=> ["@", "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"]
irb(main):007:0> "\x50".upto("\x80").to_a
=> ["P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"]
irb(main):008:0> "\x60".upto("\x80").to_a
=> ["`", "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"]
irb(main):009:0> "\x70".upto("\x80").to_a
=> ["p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]
irb(main):010:0> "\x20".upto("\x80\x80").to_a
=> [" ", "!", "\"", "#", "$", "%", "&", "'", "(", ")", "*", "+", ",", "-", ".", "/", "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25", "26", "27", "28", "29", "30", "31", "32", "33", "34", "35", "36", "37", "38", "39", "40", "41", "42", "43", "44", "45", "46", "47", "48", "49", "50", "51", "52", "53", "54", "55", "56", "57", "58", "59", "60", "61", "62", "63", "64", "65", "66", "67", "68", "69", "70", "71", "72", "73", "74", "75", "76", "77", "78", "79", "80", "81", "82", "83", "84", "85", "86", "87", "88", "89", "90", "91", "92", "93", "94", "95", "96", "97", "98", "99"]

なるほど、"\x40"や"\x50"から開始すると"Z"の次が"AA"になるからここで止まるし、"\x60"や"\x70"から開始すると"z"の次が"aa"になるからここで止まる。
終点の文字列を2文字にすれば、"\x20"(" ")から"\x39"("9")まではascii codeで増えたあと、そこから"10"にsuccされた後"99"までは数字として増える不思議な配列が出来たりする。

面白い。

#isucon 2015予選に参加した

第5回目となる ISUCON 。今年も参加しています。

前回・前々回と社内選抜として同じチームで出場していた方々が別の会社に移ってしまって出題側に回ってしまっていたりで「どうしよう…」と思っていたところに 第1回 のときのメンバー(@さん、@さん)で再結成しよう、という話が上がったので有り難く乗っからせていただきました。

fujiwara on Twitter: "初代fujiwara組を再結成しよう"

予選は第1日目で参戦し、結果は1位通過!やったー!

ISUCON5 本選出場者決定のお知らせ : ISUCON公式Blog


忘れないうちに、何をやったか振り返っておこうと思います。

〜前日

以前一緒に働いていたとは言え、4年近く経過しているので一度顔合わせて作戦会議的なものをしておきましょう、と2日前くらいに軽く集まって話して。自分とsongmuさんはコード書いてfujiwaraさんにサーバやミドルウェア設定などインフラ側みていただくという役割分担ですよね、と確認。自分は最近もうあまり書いてないですけどPerlしかマトモに出来なそうです、ということでPerl実装でやることに決め。

SlackのTeamはチーム結成すぐに用意していただいて、事前の情報共有などはそこで行なっていました。当日の連携もそこで。ファイル添付もできるしGithubのPrivate repositoryへのpushやpull requestの作成もhookして流すようにしていただいていたのでそれぞれの作業がすぐに分かってとても便利でしたね。

fujiwaraさんがサーバ立ち上げてすぐに作業できるようにと諸々準備していただいていたのでそれにお任せして…
あとは寝坊しないように前日早寝する、だけ。

当日朝

はてな社さんの会議室を使わせていただける、とのことで表参道オフィスに集合。静かな環境で落ち着いて一日作業できました。ありがとうございます。
開始前になってまさかの1時間延期。まぁ一息ついて…ちょっと気が抜けかけたけど Twitterを見ながら開始を待ちました。

スタート

まずはfujiwaraさんにインスタンスの立ち上げ・諸設定を進めていただき、レギュレーション読んでお題のアプリの機能を把握して。Githubのprivate repositoryに突っ込んでローカルに落としてコードをザッと眺めつつベンチマークをまず流してみてアクセスログ、slow queryを確認。ここまでで40分くらい。

トップ重いよねー。うわーこのSQLやばそう…。ここindex貼ってないわー。とか色々手を加えたい場所は出てくるけどボリューム的に時間内に全部対処するのは無理だろう、優先順位を考えて順番にボトルネックを潰していきましょう、と。

まずはとにかくslow query。これを減らしていくためにまずindexを貼り、コードの変更が必要な部分はsongmuさんと相談し手分けして着手。その間にfujiwaraさんにミドルウェア周りのチューニングなどやっていただいたり deploy環境を整えていただいたり。is_friendWHERE (one = ? AND another = ?) OR (one = ? AND another = ?)って片方だけで十分だよね、って最初のSQL変更がmasterに入ったのが12:40くらい。開始100分後。

昼頃(ALTER TABLE, LIMIT 1000対策)

LIMIT 1000で取ってきてアプリ内でfor文まわしてフィルタリングしているところをとにかく消すぞ!とentries_of_friendsをrelationsとJOINして取るようにしてみようとしたところ、実際にSQL発行して試してみるとめっちゃ重い。こりゃまずbodyを全部取ってきてることが問題だからそっちを先に対処しないとアカン、と。どこか(第3回の予選でしたっけ?)で見たことのあるパターンでentries.titleカラム作ってそれだけを読むようにしようにしましょう、と。

しかしこのテーブルに対するALTERがめっちゃ重い、終わらないという罠。これをfujiwaraさんがSSDインスタンスを使ったウルテクで解決してくださっているのに感動しつつ無事にALTERされる前提でコードの変更を進めた。細かくpull request作ってお互いにチェックしつつ すぐにrevertも出来るよう意識しながら。

14時前後で、無事にLIMIT 1000のクエリを排除できて2800->5200->9400と一気に上昇。しかしひそかに狙っていた「最も早く3000点に到達で予選イチ抜け」は他チームに僅差で先に獲られてしまい。正直けっこうダメージありましたね。
ひとしきり凹んだあと、とにかくもうスコア上げていくしかない!!と気を取り直しお昼ご飯たべつつ午後の作戦を相談。

午後(Redisで高速化)

「足あと」、「あなたへのコメント」あたりが次のボトルネックだ、ということでここはキャッシュしていく戦略でいこう、と。足あとはユーザーと日付を繋げたものをキーにしたRedisのsorted setを使えば良いだろう、ということでRedisの導入を決定。

僕はRedisマトモに使ったことないのでそっちはsongmuさんにお任せします!ということで自分はcomments_for_meのキャッシュ化を担当。全5000ユーザに対しそれぞれlist型で必要最小限の情報だけをJSONで突っ込んでlrangeで先頭から取り出して復元できるようにしよう、と 初期データに対する処理とPOST時の更新処理を。初期化が30秒以内に終わらないかも、というのはとりあえず考えないことにしてこれが16時ちょい前にmasterに。動かしてみたらcommand sent is not an octet sequence in the native encoding (Latin-1).となってRedisにJSONが入らなくて慌ててJSON::XS->newしてた部分を->utf8つけたのだけどmasterではなく別ブランチにpushしてしまっていて、それに気付かずまだベンチがこけ続けるので悩む、という凡ミスで30分くらいロスしてしまった orz

これで11000くらいまで上がり、続いてsongmuさんの足あと対策をmerge。これまたベンチがこけ… 何が間違っているんだ?と3人でアレコレ調査。結果的にはsongmuさんがロジックのミスに気付いて修正されて、1時間くらいかかったけど無事に解決。17時半で12000点台に。

これらによって初期データからキャッシュを作っておく初期化処理が30秒で終わらなくなってしまったけど、ベンチマークごとに変わるものではなくデータセットとして用意してあれば良いだけのもの、ということでまずは別のエンドポイントで初期データを作るようにしてベンチマーク時には既に初期キャッシュがある状態にしておいて、その後でfujiwaraさんによってaofファイルから復元することで数秒でinitializeが終わるよう解決されて、そこについて悩む必要なくて安心して使うことができました。

夕方(さらなる最適化)

ここらへんでようやく、毎回ユーザー情報をSELECTする処理がボトルネックになってきているね、ということになり これも初期化時に全部ユーザー情報をRedisに突っ込んでMySQLには行かないように変更。ここでまたバグを埋め込んでしまいFAILして焦ったけど、ここは比較的すぐに解決して18時過ぎに17000点台に。

ここまでくると今度はMySQLよりRedisの方が負荷が高くなっている、とfujiwaraさんに素早く指摘していただき、毎回Redisから引くのではなくアプリ側でもメモリに保持しておいて 無かったら引く、とやるようにしたら songmuさんによるクエリ最適化も効いて一気に26000点台まで上がった。18時20分頃。

もうちょっと 最近の自分の日記一覧とかも何故か降順でなく昇順で5件だしてるだけだからキャッシュして問題ないよね、とかも書いてpull requestまでは作ったけどミスっていたのと流石に時間が無くなってきているのでコード変更はここまでにしよう、と決断。あとは再起動テストしてみたり最後の確認をするfujiwaraさんの作業を見守って、競技時間終了。

まとめ

実際に作業したリポジトリは以下で公開してあります。

80 commits, 20 pull requests.

時系列のスコア遷移( fujiwaraさん記事 からのコピペ):

timestamp    score   
11:41:25    305 
12:03:33    0   FAIL: 
12:08:14    587 
12:18:27    1333       < indexを2個足した (fujiwara)
12:24:22    0   FAIL: 
12:27:22    1888       < my.cnf調整(fujiwara)
12:31:27    1672    
12:52:11    2008       < Gazelleに入れ替え (fujiwara)
13:47:38    2832       < entriesからtitleカラムを分離(sugyan, fujiwara)
13:49:24    2867    
13:52:20    5206       < entriesから1000件取ってるのをなくす(sugyan)
13:58:35    5500    
14:03:53    9353   < relationsから or を削った(songmu)
14:37:46    9593    
15:05:11    20  FAIL: 
15:08:00    10009   
15:15:17    10092   
15:25:29    10137   
15:30:49    0   FAIL: 
15:36:53    10138   
16:27:23    11247   < comments_for_meをredisのlistに(sugyan)
16:43:50    17  FAIL: 
16:48:45    17  FAIL: 
16:58:10    17  FAIL: 
17:04:20    17  FAIL: 
17:39:28    12389   < footprintをredisのsorted setに(songmu)
17:47:06    0   FAIL: 
18:01:09    17039   < userをmysqlではなくredisから読む(sugyan)、3回相手の属性調べてたのを一発に(songmu)
18:11:22    16402   
18:16:07    18193   < / でコメント10件毎回entriesを取得していたのをwhere inに(songmu)
18:23:54    26338   < redisから引いたuserをプロセスのメモリにcache(sugyan)
18:30:44    26153   < initializeでaofからredisを初期化(fujiwara)  
18:40:11    26694
18:42:59    27232   < 再起動試験後の最終提出スコア

とにかく3人で上手く作業分担できたのが良かったな、と思います。常にfujiwaraさんが素早く的確にボトルネックを指摘してくれていたので、「何をすればいいか」に悩むことなくひたすら手を動かし続けることができました。songmuさんともお互いどれくらいのコード変更が出来るかだいたい把握できていたので分担もスムーズに出来たと思うし、pull requestベースでのコードレビューもある程度機能しつつ進められた(結局レビューしていてもバグっていたり、とかはあったけど…w)。最終的には手戻りするようなこともなく無駄な作業というのはほとんど無かった。
それにしてもボトルネックの指摘もだけど ALTER TABLEを別のインスタンスでやる、とかRedisの初期状態をサクっと作ったり、とかは僕だったらまったく思いつかずに完全に詰んでしまっていたと思うので、こういうのを素早く解決してくれる人が居るというのは本当に心強くて最高だ、と思います。
反省点としてはやっぱりバグを生んでしまってベンチマークがFAILしたときになかなか原因を発見できず時間をロスしてしまったこと、ここはもっと落ち着いて素早く解決できるようにならなければ、と思いました。
あとコード変更はすべてローカルでやってたわけですが今回の問題だとmysqldumpも重くて初期データセットをローカルまで持ってくることもできず 変更に対する動作確認はsyntax error無くアプリが起動する、くらいで「これで動く、はず」みたいになってしまったのはもうちょっとどうにかしたかったなぁ、と。


イチ抜けでの通過はできなかったものの、最終的な記録としては2日通しての最高スコアで予選通過できたのは嬉しい。本選も良い成績を残せるよう頑張りたいと思います。

とてもやり甲斐あって楽しい予選でした。問題を用意してくださった運営陣の皆様、おつかれさまでした&ありがとうございました。
本選もよろしくお願いします!