問題文

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 個のテストケースについて答えてください。

制約

• 入力はすべて整数
• 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 以下

部分点

次の条件をすべて満たした場合、部分点 25 点が与えられる。

• 良い旗の立て方がないテストケースについて、構築不可能と報告している。
• 良い旗の立て方があるテストケースについて、構築可能と報告しており、構築した旗の立て方が良い立て方であり、立てた旗の本数が 8N 本以下である。
• いずれかのテストケースにおいて、良い旗の立て方があるが、旗の本数が最小化されていない。

入力例 1

4
1 3 6
0
2 5 5
-15 -5
2 3 4
0 2
3 100 100
-100 0 100

出力例 1

1
6 
1
-10 
2
-3 6 
-1

1 番目のテストケースでは座標 0 に人がおり、座標 0 から最も近い旗までの距離が 3 以上 6 以下でないといけません。

出力例では、1 本の旗を座標 6 に立ててあり、座標 0 から最も近い旗（座標 6）までの距離は 6 であるので、良い旗の立て方であり、立てる旗の本数の最小化も達成されています。一方で、

1
-2

という出力の場合、座標 0 から最も近い旗（座標 -2）までの距離は 2 であり、3 以上 6 以下ではないので良い旗の立て方ではありません。