怪物城には巨大な公園があり、この公園はいくつかの観光スポットと、それらを結ぶ一方通行の道路で構成されています。観光スポットは全部で $v$ 個あり、$1, 2, \dots, v$ と番号が振られています。これらのスポットには $n$ 個の入口と $1$ 個の出口が含まれており、スポット $1, 2, \dots, n$ が入口、スポット $v$ が出口です。公園内には $e$ 本の道路があり、$i$ 番目の道路はスポット $a_i$ からスポット $b_i$ へ向かいます。
各スポット $i$ にはフラグ $s_i$ があり、これは & または | のいずれかです。同様に、各道路 $i$ にもフラグ $t_i$ があり、これは &、|、~、<、> のいずれかです。$t_i$ が ~ でない場合、道路 $i$ にはさらに重み $l_i$ が設定されています。
毎日、$n$ 匹のモンスターが1つのグループとして公園に入ります。$i$ 日目には、初期体力 $h_{i,1}, h_{i,2}, \dots, h_{i,n}$ を持つ $n$ 匹のモンスターが同時にそれぞれ入口 $1, 2, \dots, n$ から公園に入り、公園内を移動します。毎分、各モンスターは現在のスポットから伸びる道路の数 $k$ に応じて、$k$ 匹の分身に分裂します（分身の体力は分裂前と同じです）。それぞれの分身は、そのスポットから伸びる $k$ 本の道路に沿って進みます。
モンスターが道路を通過するのにはちょうど $1$ 分かかります。体力 $h$ のモンスターが道路 $i$ を通過した後の体力 $h'$ は、以下の表に従って変化します。
| $t_i=$ | $h'=$ | 説明 |
|---|---|---|
& |
$h\ \mathrm{AND}\ l_i$ | $h$ と $l_i$ のビット単位の論理積 |
| |
$h\ \mathrm{OR}\ l_i$ | $h$ と $l_i$ のビット単位の論理和 |
~ |
$\mathrm{NOT}\ h$ | $h$ のビット単位の反転 |
< |
$h\ \mathrm{SHL}\ l_i$ | $h$ を左シフトし、下位に $l_i$ 個の $0$ を補い、上位 $l_i$ ビットを捨てる |
> |
$h\ \mathrm{SHR}\ l_i$ | $h$ を右シフトし、上位に $l_i$ 個の $0$ を補い、下位 $l_i$ ビットを捨てる |
表中の $\mathrm{AND}, \mathrm{OR}, \mathrm{NOT}, \mathrm{SHL}, \mathrm{SHR}$ はそれぞれビット単位の論理積、論理和、反転、左シフト、右シフトに対応します。ここで $h, l_i, h'$ はすべて $32$ ビット符号なし整数です。$\mathrm{AND}, \mathrm{OR}$ 演算では $0 \le l_i < 2^{32}$ を満たし、$\mathrm{SHL}, \mathrm{SHR}$ 演算では $0 \le l_i < 32$ を満たします。
体力 $h_1, h_2, \dots, h_c$ を持つ複数のモンスターが同じスポット $i$ で出会った場合、それらは $1$ 匹のモンスターに合体します。合体後の体力 $h'$ は $h_1, h_2, \dots, h_c$ に対してスポット $i$ のフラグ $s_i$ を適用した結果となります。すなわち、$s_i$ が & ならば $h' = h_1\ \mathrm{AND}\ h_2\ \mathrm{AND}\ \dots\ \mathrm{AND}\ h_c$、$s_i$ が | ならば $h' = h_1\ \mathrm{OR}\ h_2\ \mathrm{OR}\ \dots\ \mathrm{OR}\ h_c$ となります。その後、もしそのモンスターが公園の出口に位置していれば、公園から退出します。各グループにおいて、最初に公園から退出したモンスターを「Winner」と呼びます。 すべてのモンスターの初期体力と、Winner が公園から退出した際の体力が記録されます。
モンスターは以下のいずれかの場合に死亡します（死亡したモンスターは二度と行動せず、合体にも参加しません）。
- モンスターがいるスポットから伸びる道路が存在せず、かつそのスポットが出口ではない場合。
- モンスターの体力が $0$ になった場合。これは道路上での移動中や、合体直後に発生する可能性があります。
- モンスターが公園に入ってから経過した時間が、そのモンスターの寿命 $k$ を超えた場合。
$i+1$ 日目には、$i$ 日目に入ったモンスターはすべて公園から退出しているか死亡しているものとみなせます。
しかし、$m$ 日後、天災により公園は深刻な被害を受けました。怪物城は $m$ 日間の記録に基づいて公園を再建したいと考えていますが、これは困難な作業です。あなたの仕事は、$m$ 日間のすべての記録を満たす公園の構成を任意に設計することです。
入力
すべての入力データ rebuild1.in ～ rebuild10.in はデータダウンロードを参照してください。
入力の第 $1$ 行には、$3$ つの整数 $n, m, k$ が含まれており、それぞれ毎日入るモンスターの数、日数、モンスターの寿命を表します。
第 $2$ 行から第 $2m+1$ 行までは $m$ 日間の記録です。第 $2i$ 行には $n$ 個の整数 $h_{i,1}, h_{i,2}, \dots, h_{i,n}$ が含まれ、$i$ 日目の $n$ 匹のモンスターの初期体力を表します。第 $2i+1$ 行には $1$ つの整数 $w_i$ が含まれ、$i$ 日目の Winner が公園から退出した際の体力を表します。毎日必ず Winner が存在することが保証されています。
出力
与えられた $10$ 個の入力ファイル rebuild1.in ～ rebuild10.in に対して、それぞれ出力ファイル rebuild1.out ～ rebuild10.out を提出してください。
出力の第 $1$ 行には、$2$ つの整数 $v, e$ が含まれ、それぞれスポット数と道路数を表します（$n < v \le 100$、$0 \le e \le 500$）。
第 $2$ 行には長さ $v$ の文字列 $s$ が含まれ、第 $i$ 文字 $s_i$ はスポット $i$ のフラグ（& または |）を表します。
第 $3$ 行から第 $e+2$ 行までは、各行に道路を記述します。第 $i+2$ 行には $a_i, b_i, t_i, l_i$ の $4$ つの値（または文字）が含まれ、それぞれ道路の始点、終点、フラグ、重みを表します。$1 \le a_i, b_i \le v$ であり、フラグは &、|、~、<、> のいずれかです。特に、$t_i$ が ~ の場合、$l_i$ は入力されません。 2つのスポット間に複数の道路が存在することや、始点と終点が同じ道路が存在することも許容されます。
条件を満たす任意の構成を出力してください。そのような構成が存在することは保証されています。
入出力例
入力 1
2 4 2 11 1 20 11 2 18 11 3 16 18 12 12
出力 1
4 4 ||&& 1 3 | 0 2 3 ~ 2 4 & 12 3 4 < 1
注記
出力例は考えられる公園の再建案の一つです。1日目のモンスターを例に挙げます。
最初、2匹のモンスターがスポット1と2に位置しており、体力はそれぞれ11と1です。
1分目、スポット1のモンスターは道路を通ってスポット3に入り、体力は $11\ \mathrm{OR}\ 0 = 11$ になります。スポット2のモンスターは2匹に分裂し、一方は道路を通ってスポット3に入り、体力は $\mathrm{NOT}\ 1 = 4294967294$ になります。もう一方は道路を通ってスポット4に入り、体力は $1\ \mathrm{AND}\ 12 = 0$ となるため、スポットに入る前に死亡します。その後、スポット3にいる2匹のモンスターは合体し、体力 $11\ \mathrm{AND}\ 4294967294 = 10$ のモンスターが1匹になります。この時点でスポット3にのみモンスターが1匹存在します。
2分目、スポット3のモンスターは道路を通ってスポット4に入り、体力は $10\ \mathrm{SHL}\ 1 = 20$ になります。スポット4は出口であるため、このモンスターは公園から退出します。これがWinnerとなります。
したがって、このグループのWinnerの体力は20となります。
小課題
$10$ 個の評価ファイル rebuild1.ans ～ rebuild10.ans が提供されます。各評価ファイルは $10$ 行からなり、第 $i$ 行には評価パラメータ $a_i$ が記載されています。
各テストケースは個別に評価されます。出力形式が不正な場合は $0$ 点となります。出力が正当であっても、$m$ 個の記録のうち一部しか満たしていない場合は部分点が得られる可能性があります。
あなたの構成において満たされた記録の数を $x_{user}$ とすると、スコアは以下の表に従って決定されます。
| 得点 | 条件 | 得点 | 条件 |
|---|---|---|---|
| $10$ | $x_{user} \ge a_{10}$ | $5$ | $x_{user} \le a_5$ |
| $9$ | $x_{user} \ge a_9$ | $4$ | $x_{user} \ge a_4$ |
| $8$ | $x_{user} \ge a_8$ | $3$ | $x_{user} \ge a_3$ |
| $7$ | $x_{user} \ge a_7$ | $2$ | $x_{user} \ge a_2$ |
| $6$ | $x_{user} \ge a_6$ | $1$ | $x_{user} \ge a_1$ |
表中のすべての条件を満たさない場合は $0$ 点となります。複数の条件を満たす場合は、最も高い点数が与えられます。
出力のテスト方法
ターミナルで試題のディレクトリに移動してください（Windowsユーザーはcmdを使用してください）。（入力ファイル、出力ファイル、checkerなどが rebuild フォルダにあると仮定します）
cd rebuild
出力ファイルが許容範囲内かどうかをテストするための checker ツールを提供しています。ターミナルで以下を実行してください。
./checker_linux64 <case_no>
ここで <case_no> はテストデータの番号です。例えば、
./checker_linux64 3
とすると、rebuild3.out が許容されるかテストされます。（Windowsユーザーは checker_win32 3 を使用してください。Windows 64bit環境でもwin32アプリケーションを実行可能です。）
Linux 32bit版の checker_linux32 も用意されています。Linuxユーザーでプログラムが実行できない場合は、chmod +x checker_linux64 または chmod +x checker_linux32 を実行してから再試行してください。
このプログラムを実行すると、checkerは出力ファイルに基づいたテスト結果を表示します。
checkerが予期せぬエラーを起こさないよう、入力ファイルを変更しないでください。
また、ターミナルで以下のコマンドを使用すると、
./checker_linux64 –w <case_no>
テストケース <case_no> における毎日のモンスターの移動過程での位置と体力が report.log ファイルに出力されます。report.log は非常に大きくなる可能性があることに注意してください（極端な場合、約 $150\texttt{MB}$ になります）。