AT_utpc2020_c Range Flip

[problemUrl]: https://atcoder.jp/contests/utpc2020/tasks/utpc2020_c 長さ $ N $ の整数列 $ A_1,\ \ldots,\ A_N $ と $ 1 $ 以上 $ N $ 以下の正の整数 $ D $ が与えられます。以下の操作を繰り返すことを考えます。 - $ 1\ \leq\ L\ \leq\ R\ \leq\ N $ かつ $ R-L+1=D $ であるような整数 $ L $ , $ R $ および整数 $ X $ を選び、$ A_L,\ A_{L+1},\ \ldots\ ,A_R $ を一斉に、$ (X-A_L),\ (X-A_{L+1}),\ \ldots,\ (X-A_R) $ に書きかえる。 $ A_1,\ A_2,\ \ldots,\ A_N $ を有限回の操作で $ B_1,\ B_2,\ \ldots,\ B_N $ に一致させられるかを判定し、可能な場合はその操作手順の中で以下の条件をすべて満たすものを $ 1 $ つ構成してください。 - 操作回数が $ 3\times\ 10^5 $ 回以下。( $ 0 $ 回でも良い。) - 各操作における $ X $ の絶対値が $ 10^{13} $ 以下。 なお、この問題の制約下で、有限回の操作で一致させることが可能な場合には上記の条件をすべて満たすような手順が存在することが証明できます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ D $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_N $

一致させられるならば `Yes` を、そうでなければ `No` を出力せよ。 `Yes` の場合は $ 2 $ 行目に操作回数 $ K\ (0\ \leq\ K\ \leq\ 3\times\ 10^5) $ を出力し、 その下に操作手順を以下の形式で $ K $ 行出力せよ。 > $ L_1 $ $ R_1 $ $ X_1 $ $ \vdots $ $ L_K $ $ R_K $ $ X_K $ ただし、$ L_i,\ R_i,X_i(1\ \leq\ i\ \leq\ K) $は $ i $ 回目の操作における $ L,R,X $ の値を表す。 条件を満たす解が複数存在する場合は、どれを出力してもよい。

### 制約 - 入力は全て整数である。 - $ 1\ \leq\ D\ \leq\ N\ \leq\ 3\times\ 10^5 $ - $ \lvert\ A_i\ \rvert\ \leq\ 10^6 $ - $ \lvert\ B_i\ \rvert\ \leq\ 10^6 $ ### 部分点 - $ 1\ \leq\ N\ \leq\ 3\times\ 10^4 $ を満たすデータセットに正解した場合は $ 50 $ 点が与えられる。 ### Sample Explanation 1 \- 初期状態から$ (L,R,X)=(1,2,5) $として操作を行うと $ [1,2,3,4]\to\ [4,3,3,4] $ となります。 - 次に$ (L,R,X)=(3,4,7) $として操作を行うと $ [4,3,3,4]\to\ [4,3,4,3] $ となります。 - 最後に$ (L,R,X)=(2,3,7) $として操作を行うと$ [4,3,4,3]\to\ [4,4,3,3] $ となり、 $ B $ と一致しています。 ### Sample Explanation 2 どのように操作しても一致させることができません。