問題の配置

$N$ 個の問題をすべて、Div.3、Div.2、Div.1 のうちちょうど 1 つに配置したい。各 Div には少なくとも 1 問を配置しなければならない。

問題 $i$ の難易度は $A_i$ である。$S_i$ が E ならば易しい問題であり、Div.3 または Div.2 にのみ配置できる。$S_i$ が H ならば難しい問題であり、Div.2 または Div.1 にのみ配置できる。易しいか難しいかは難易度とは無関係である。Div 間の難易度の大小関係に関する条件はない。

ある Div の幅とは、配置した問題の難易度の最大値から最小値を引いた値である。問題が 1 つならば幅は $0$ である。

3 つの Div の幅の最大値を最小化せよ。配置が不可能な場合は -1 を出力する。

入力は以下の形式で与えられる。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

各テストケースについて、3 つの Div の幅の最大値の最小値を 1 行に出力する。

不可能な場合は -1 を出力する。

• $1\le T\le100\,000$.
• $1\le N\le200\,000$.
• $1\le A_{}$ ().