Problem Arrangement

We want to place each of the $N$ problems into exactly one of Div.3, Div.2, and Div.1. Each Div must contain at least one problem.

The difficulty of problem $i$ is $A_i$. If $S_i$ is E, it is an easy problem and can be placed only in Div.3 or Div.2. If $S_i$ is H, it is a hard problem and can be placed only in Div.2 or Div.1. Whether a problem is easy or hard is unrelated to its difficulty. There is no condition on the relative difficulties between Divs.

The width of a Div is the maximum difficulty of the problems placed in it minus the minimum difficulty. If it contains only one problem, its width is $0$.

Minimize the maximum of the widths of the three Divs. If no valid placement exists, output -1.

The input is given in the following format.

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

For each test case, output the minimum possible value of the maximum of the widths of the three Divs on a single line.

If it is impossible, output -1.

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