U427747 [LdOI-(-9)] 16 - Mining for Diamonds

小鈴は、最近ハマっているマインクラフト1.17のサーバー、ヘルメスSMPの世界にログインした。今日の目標は、ダイヤモンドを手に入れることだ。彼女は既にしっかりとした家を建て、村人たちとも友好関係を築いたが、より強力な装備が必要だと感じていた。ダイヤモンドの剣、鎧、そしてツールがあれば、彼女の旅はさらにスムーズに進むに違いない。 「さて、今日もダイヤモンドを探しに行こうか！」小鈴は元気にそう呟いて、彼女の手に持った鉄のツルハシを見つめた。このツルハシは、彼女が何時間もかけて深い洞窟を掘り進めた証だ。鉱石を掘り、モンスターと戦い、時には溶岩に足を滑らせそうになることもあったが、彼女はそれでも諦めずに探求を続けていた。 彼女はサーバーにログインして、自分の小さな拠点の中にあるチェストを開けた。中には食料、松明、余分なツルハシが整然と並べられていた。食料と松明を少し持ち、ツルハシも予備を持っておくことにした。今回の採掘は長丁場になるかもしれないと考え、十分な準備を整えてから出発することにした。 地下へと向かう階段を下り始めた。ヘルメスSMPは自然の生成が美しく、洞窟の構造も複雑だが、小鈴はその美しさを感じる余裕もなく、ただひたすらに深く掘り進んでいく。石の壁をツルハシで掘りながら、彼女の頭の中には一つの考えが浮かんでいた。「どうやって効率よくダイヤモンドを見つけることができるんだろう？」 マインクラフトの世界では、ダイヤモンドはY座標の低い場所に生成されることは知っているが、どこに生成されるかは運次第だ。まっすぐに掘り進めばいいのか、あるいはランダムに掘ってみるべきか。これまでの採掘ではなかなか思うように見つからず、少しだけ疲れてきていた。 「何か方法はないかな…」小鈴は独り言をつぶやいた。その時、彼女はふと、以前読んだプログラミングの本のことを思い出した。東方の世界では古本を扱っている彼女だが、実はその本には、基本的なプログラムの組み方が書かれていたのだ。もし、プログラムでダイヤモンドを見つける方法が作れたら、どんなに楽だろう、と彼女は思った。 「そうだ、プログラムを作ってみよう！」彼女はそのアイデアに興奮した。彼女は手元にあるパソコンのコーディングソフトを立ち上げ、すぐに作業に取り掛かることにした。

入力は以下の形式で標準入力から与えられる。 > $seed\enspace cnt$

合計で $cnt$ 行を出力します。各行には $3$ つの整数 $x_i, y_i, z_i$ が含まれます。$|x_i|, |z_i| \le 10^4$、$1 \le y_i \le 16$ を満たすようにしてください。また、異なる $i\,(1 \le i \le n)$ に対して、$(x_i, y_i, z_i)$ はすべて異なる組み合わせでなければなりません。 一定の誤差を許す。

| # | $seed =$ | $cnt =$ | | :-: | :-: | :-: | | $1$ | $0$ | $1$ | | $2$ | $340\,221$ | $4$ | | $3$ | $20\,200\,720$ | $95$ |