とここちゃんは友だちと $4$ 人でゲームをしています。

$4$ 人にはそれぞれ $1$ から $4$ の相異なる番号がつけられており、とここちゃんの番号は $X$ です。番号が $i$ の人の現在の点数は $A_i$ 点です。

とここちゃんは好きな非負整数 $S$ を選び、自分以外の $3$ 人からそれぞれ $S$ 点を奪い、さらに番号が $Y$ の人から $S$ 点追加で奪います。これにより、とここちゃんの点数は $4S$ 点増え、番号が $Y$ の人の点数は $2S$ 点減り、残りの $2$ 人の点数はそれぞれ $S$ 点減ります。

その後、点数が大きい順に順位をつけます。ただし、点数が等しい人の間では番号が小さい人がより上位になるものとします。

とここちゃんがちょうど $R$ 位になるような非負整数 $S$ が存在するか判定してください。もし存在するならば、そのような $S$ のうち最小のものを求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

• $1 \le T \le 30{,}000$
• $X \in \lbrace 1, 2, 3, 4 \rbrace$
• $Y \in \lbrace 1, 2, 3, 4 \rbrace \setminus {X}$
• $R \in \lbrace 1, 2, 3, 4 \rbrace$
• $-10^{18} \le A_i \le 10^{18}$
• 入力は全て整数

この問題に部分点は存在しません。

入力は以下の形式で標準入力から与えられます。

各テストケースは以下の形式で与えられます。

標準出力に $T$ 行出力してください。

$i$ 行目には、$\mathrm{case}_i$ に対する答えを以下の説明に従って出力してください。

とここちゃんがちょうど $R$ 位になるような非負整数 $S$ が存在する場合、そのような $S$ の中で最小のものを出力してください。存在しない場合、-1 を出力してください。