AT_abc448_g [ABC448G] Conquest

Takahashi and Aoki play a card game. The game proceeds according to the following rules. - Takahashi presents decks $ A_1, A_2, \dots, A_N $ . Here $ N \geq 3 $ . - Aoki presents decks $ B_1, B_2, B_3 $ . - Takahashi chooses one deck from Aoki's decks and bans it. Aoki also chooses one deck from Takahashi's decks and bans it. These two ban operations are performed **simultaneously**. (That is, neither player can act based on the other's choice.) - Then, Takahashi and Aoki each **simultaneously** declare which deck from their own presented decks they will use. However, the banned deck cannot be declared. - Then, the two players battle exactly once using their declared decks. As a result, one of them wins. You are given integers $ X_{i,j} $ $ (1 \leq i \leq N, 1 \leq j \leq 3) $ . Let $ p_{i,j} = \dfrac{X_{i,j}}{10^6} $ . $ p_{i,j} $ is Takahashi's win rate when Takahashi uses deck $ A_i $ and Aoki uses deck $ B_j $ . Both Takahashi and Aoki know the values of $ p_{i,j} $ in advance. Find Takahashi's win rate when both players act to maximize their own win rate. $ T $ test cases are given; solve each of them. What is Takahashi's win rate when both players act to maximize their own win rate?At each stage, each player assigns probabilities summing to $ 1 $ to the available choices based on the information revealed up to that point, and randomly selects one choice according to those probabilities. Each player chooses a strategy that maximizes "the minimum possible win rate," that is, "the win rate when the opponent chooses a strategy that minimizes the player's win rate." If there are multiple strategies satisfying this condition, any of them may be chosen. When both players act according to this policy, Takahashi's win rate is uniquely determined regardless of the specific strategy chosen. Find this value.

The input is given from Standard Input in the following format, where $ \mathrm{case}_i $ denotes the $ i $ -th test case. > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ For each test case, the input is given in the following format. > $ N $ $ X_{1,1} $ $ X_{1,2} $ $ X_{1,3} $ $ X_{2,1} $ $ X_{2,2} $ $ X_{2,3} $ $ \vdots $ $ X_{N,1} $ $ X_{N,2} $ $ X_{N,3} $

Output $ T $ lines. The $ i $ -th line should contain the answer to the $ i $ -th test case. For each test case, output Takahashi's win rate when both players act to maximize their own win rate. The output is considered correct if the absolute or relative error from the true value is at most $ 10^{-6} $ .

### Sample Explanation 1 Takahashi's win rate when both players act to maximize their own win rate is $ 0.5272727 \cdots $ . ### Constraints - $ 1 \leq T \leq 500 $ - $ 3 \leq N \leq 5 \times 10^4 $ - $ 0 \leq X_{i,j} \leq 10^6 $ - The sum of $ N $ over all test cases is at most $ 5 \times 10^4 $ . - All input values are integers.