AT_stpc2025_2_n Fair Flags

$ N $ 人が数直線上におり、左から $ i $ 番目の人は座標 $ A_i $ にいます。また、正整数 $ L, R \ (L \le R) $ が与えられます。 この数直線上に $ 1 $ 本以上の旗を立てることを考えます。立てた旗の本数を $ k $ 本として、それらの座標を $ x_1, x_2, \dots, x_k $ とします。次の条件をともに満たすとき、この旗の立て方は**良い立て方**であると言います。 - すべての旗は整数座標にある。すなわち、すべての $ j = 1, 2, \dots, k $ に対し $ x_j $ は整数である。 - すべての人について、その人からその人と最も近い旗との距離は $ L $ 以上 $ R $ 以下である。すなわち、すべての $ i = 1, 2, \dots, N $ に対し $ L \le \bigl( \min_{1\le j\le k} |A_i - x_j| \bigr) \le R $ である。 良い旗の立て方がある場合は**立てる旗の本数を最小化**して構築し、ない場合はそれを報告してください。なお、良い旗の立て方がある場合は立てるべき旗の最小本数 $ k $ が $ 8N $ 以下であることが証明できます。 $ T $ 個のテストケースについて答えてください。

入力は以下の形式で与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ ここで、 $ \mathrm{case}_i $ は $ i $ 番目のテストケースを表す。各テストケースは以下の形式で与えられる。 > $ N $ $ L $ $ R $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

各テストケースの答えを次のように出力せよ。 良い旗の立て方が存在するならば、立てた旗の本数を $ k \ (1 \le k \le 8N) $ 、座標をそれぞれ $ x_1, x_2, \dots, x_k \ (-10^9 \le x_i \le 10^9) $ として次のように出力せよ。解は複数ある可能性があるが、どれを出力してもよい。 > $ k $ $ x_1 $ $ x_2 $ $ \cdots $ $ x_k $ 良い旗の立て方が存在しないならば、`-1` と出力せよ。

### 部分点 次の条件をすべて満たした場合、部分点 $ 25 $ 点が与えられる。 - 良い旗の立て方がないテストケースについて、構築不可能と報告している。 - 良い旗の立て方があるテストケースについて、構築可能と報告しており、構築した旗の立て方が良い立て方であり、立てた旗の本数が $ 8N $ 本以下である。 - いずれかのテストケースにおいて、良い旗の立て方があるが、旗の本数が最小化されていない。 ### Sample Explanation 1 $ 1 $ 番目のテストケースでは座標 $ 0 $ に人がおり、座標 $ 0 $ から最も近い旗までの距離が $ 3 $ 以上 $ 6 $ 以下でないといけません。 出力例では、 $ 1 $ 本の旗を座標 $ 6 $ に立ててあり、座標 $ 0 $ から最も近い旗（座標 $ 6 $ ）までの距離は $ 6 $ であるので、良い旗の立て方であり、立てる旗の本数の最小化も達成されています。一方で、 ``` 1 -2 ``` という出力の場合、座標 $ 0 $ から最も近い旗（座標 $ -2 $ ）までの距離は $ 2 $ であり、 $ 3 $ 以上 $ 6 $ 以下ではないので良い旗の立て方ではありません。 ### Constraints - 入力はすべて整数 - $ 1 \le T \le 2 \times 10^4 $ - $ 1 \le N \le 2\times 10^5 $ - $ 1 \le L \le R \le 5 \times 10^8 $ - $ -5\times 10^8 \le A_1 \lt A_2 \lt \dots \lt A_N \le 5\times 10^8 $ - テストケース全体で $ N $ の総和は $ 4 \times 10^5 $ 以下