配点 : $1800$ 点

問題文

これは output-only 問題です。入力は与えられません。

簡潔に述べると、整数の掛け算を、比較 $(x < y)$ と加算 $(x + y)$ のみを用いてシミュレートする問題です。 入力はありません。操作列の出力のみを行ってください。

長さ $N$ の長大な配列 $a[0], a[1], ..., a[N-1]$ があるとします。 先頭の二要素の初期値は非負整数 $A, B$ であり (あなたには知らされません)、残りの要素の初期値は $0$ です。 あなたの目的は、最終的に $a[2]$ を積 $A \cdot B$ とすることです。

あなたが行えるのは、以下の形式の二種類の操作です (ここで、$0 \leq i, j, k < N$ です)。

• + i j k: $a[k] = a[i] + a[j]$ とする。
• < i j k: $a[k] = a[i] < a[j]$ とする。すなわち、$a[i] < a[j]$ であれば $a[k]$ は $1$ となり、そうでなければ $a[k]$ は $0$ となる。

操作を行える回数は最大で $Q$ 回であり、操作中に $a$ の要素が $V$ より大きくなってはなりません。 ただし、一回の操作で指定する添字 $(i, j, k)$ に重複があっても構わず、(先頭二要素を含む) 配列のどの要素も書き換えて構いません。 なお、この問題の正誤判定機は、単一テストケースにおいて実際には複数のペア $(A, B)$ について操作列を実行します。 各回について、判定機は値 $A, B$ を選んで配列 $a = [A, B, 0, 0, \ldots, 0]$ を生成し、提出された操作列を適用して最終的に $a[2] = A \cdot B$ となるかを検証します。

制約

• $0 \leq A, B \leq 10^9$
• $N = Q = 200\,000$
• $V = 10^{19} = 10\,000\,000\,000\,000\,000\,000$

部分点

• $A, B \leq 10$ を満たすテストケースを通過すると、$800$ 点が与えられる。
• すべてのテストケースを通過すると、さらに $1000$ 点が与えられる。

入力

標準入力から与えられる入力は空である。

出力

$1$ 行目に、操作を行う回数を出力せよ。 続けて、行う操作をそれぞれ + i j k または < i j k という形式で一行に出力せよ。

4
< 0 1 8
+ 0 1 2
+ 2 8 2
+ 0 0 0

入力例 1 では、正誤判定機はペア $(A, B) = (2, 3)$ についてのみ提出された操作列を検証します。 上記の出力は、このテストケースを通過します。その過程は次の通りです。

• はじめ、$a[0] = 2$, $a[1] = 3$, $a[2] = a[3] = \ldots = a[N-1] = 0$ である。
• < 0 1 8 により、$a[0] < a[1]$ であるため $a[8] = 1$ となる。
• + 0 1 2 により、$a[2] = a[0] + a[1] = 5$ となる。
• + 2 8 2 により、$a[2] = a[2] + a[8] = 6$ となる。
• + 0 0 0 により、$a[0] = a[0] + a[0] = 4$ となる。
• 要求された通り、最終的に $a[2] = 6 = A \cdot B$ となっている。