問題一覧 > 通常問題

No.1404 誕生日プレゼント

レベル : / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 4
作問者 : CuriousFairy315CuriousFairy315 / テスター : cn_449cn_449
2 ProblemId : 4950 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-02-18 13:52:04

問題文

315さんは、親友のネッコアラさんに誕生日プレゼントとして数列を送ろうとしています。
ネッコアラさんは長さ $N$ の数列 $B_i$ が好きなので、315さんはこの数列を用意してネッコアラさんの家に向かいました。
しかし、電車に乗っている途中で数列を確認すると、間違えて別の数列 $A_i$ を持ってきたことに気付いてしまいました。
幸い、まだ到着まで $P$ 分あります。315さんは、 $1$ 分あたり次の操作のどちらかを1回だけ行うことができます。
操作1. $1 \leq i, j \leq N$ となる整数 $i, j$ を選び、 $A_i$ に $A_j$ を加算する。
操作2. 数列の全ての要素を、 $P$ で割った余りに置き換える。
さて、315さんは無事に数列 $B_i$ を送ることができるでしょうか?

入力

$N \ P$
$A_1 \ A_2 \ \cdots \ A_N$
$B_1 \ B_2 \ \cdots \ B_N$

  • $1 \leq N \leq 10^5$
  • $P = 223577$ (素数)
  • $0 \leq A_i, B_i < P$
  • 入力は全て整数である

出力

時間内に数列 $B_i$ を作れない場合、-1を出力してください。
そうでない場合、まず $1$ 行目に操作を行った回数 $n$ を出力してください。
続く $n$ 行の各行には、操作 $1$ を行ったのならば $1 \ i \ j$ を、操作 $2$ を行ったのならば $2$ を出力してください。
いずれの場合も、最後に改行をしてください。

サンプル

サンプル1
入力
2 223577
1 1
4 5
出力
5
1 1 2
1 1 2
1 1 2
1 2 1
2

操作2は最後のみ行うとしても問題ないことが分かります。

サンプル2
入力
1 223577
101090
9
出力
11
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
2

同じ数字を指定することができます。

サンプル3
入力
5 223577
1 2 3 4 5
1 3 6 10 15
出力
10
1 5 4
1 5 3
1 5 2
1 5 1
1 4 3
1 4 2
1 4 1
1 3 2
1 3 1
1 2 1

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。