Every time when Rikka faces to a great nature sight, she will recall a line of ants moving in a hurry. Rikka loves ants and keeps two large colonies of ants in her drawer. Observing ants hurrying in moving has controlled her life.
That is why she prepares $n$ different nests in her drawer, and $n$ undirected channels between these nests form a circular orbit. All nests are numbered by $1$ to $n$ in order, and the lengths of channels are known. The first colony of ants is living in the $s_1$-th nest, and the second colony is living in the $s_2$-th nest.
Now, ants decide to move to new nests together. The new home for these two colonies of ants will be the $e_1$-th nest and the $e_2$-th nest respectively.
For each colony, all ants should queue up one by one to crawl from the origin to the destination along a path. They cannot be split into several groups crawling moving along different paths. Then, they can measure the complexity of their plan moving to new nest using the total length of channels in the path selected.
If these two colonies of ants select paths sharing some common channels, they will walk through these channels slowly for security. Specifically, for each common channel, we can consider equivalently that its measured length will be tripled.
Ants are highly intelligent and they all want to minimize the complexities of their plan. They will choose the best strategies for themselves respectively without negotiation. All they know are the lengths of channels, and the nests where their colony and the other one will start and end respectively.
Rikka wants you to calculate the expected complexities of plans for each colony of ants. For more details about the best strategy, please refer to note.
The input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 5000$), the number of test cases.
For each test case, the first line contains a single integer $n$ ($2 <= n <= 50$), the number of nests and also the number of channels between them.
The second line contains $n$ integers $a_1, a_2, \\\\cdots, a_n$ ($1 <= a_i <= 50$), where the $i$-th one, $a_i$, represents the length of the undirected channel between the $i$-th nest and the $((i bmod n) + 1)$-th nest. It is guaranteed that the total length of the $n$ channels is odd.
The third line contains four integers $s_1, e_1, s_2$ and $e_2$ ($1 <= s_1, s_2, e_1, e_2 <= n$, $s_1 != e_1$, $s_2 != e_2$), representing the original nests where these ants live and their new nests.
For each test case, output a line with two space-separated numbers, representing the expected complexity for the first colony of ant and the expected complexity for the second colony respectively. Your answer is considered correct if the absolute or relative error between each number in your output and the corresponding one in Rikka's answer does not exceed $10^(-9)$. Formally, let a number of your answer be $a$, and the corresponding number of Rikka's answer be $b$. Your answer is considered correct if $frac(| a -b |, max (1 , | b |)) <= 10^(-9)$.
What we are talking about including strategies, best strategies and expectations are actually what about Nash Equilibrium and mixed strategies.
In the theory of games, a player is said to use a mixed strategy whenever the player chooses to randomize over the set of available actions. Formally, a mixed strategy is a probability distribution that assigns to each available action a likelihood of being selected. If only one action has a positive probability of being selected, the player is said to use a pure strategy. In the first sample case, the best strategies for both colonies are pure strategies.
A mixed strategy profile is a list of strategies, one for each player in the game. A mixed strategy profile induces a probability distribution or lottery over the possible outcomes of the game. In this problem, the profiles are those plans that we discussed before.
A Nash equilibrium (mixed strategy) is a strategy profile with the property that no single player can, by deviating unilaterally to another strategy, induce a lottery that he or she finds strictly preferable. In $1950$, the mathematician John Nash proved that every game with a finite set of players and actions has at least one equilibrium.
In this problem, a Nash equilibrium is what you need to find. You may find out several different equilibriums. If some of them have the same unilateral strategy, their earnings must be constant.
We still need to discuss when several different equilibriums without fixed unilateral strategy exist. Notice that in this case, we have a unique equilibrium with mixed, impure strategies. Since ants like to show-off their intelligence, this equilibrium is exactly their final choices.
In the second test case, though we have three different equilibriums whose earnings are $(8, 10)$, $(13, 11)$ and $(14. 666 \\\\cdots, 14. 666 \\\\cdots)$, the last one is the earnings for the only equilibrium with mixed, impure strategies and thus is what we need.
## Input
The input contains several test cases, and the first line contains a single integer $T$ ($1 <= T <= 5000$), the number of test cases.For each test case, the first line contains a single integer $n$ ($2 <= n <= 50$), the number of nests and also the number of channels between them.The second line contains $n$ integers $a_1, a_2, \\\\cdots, a_n$ ($1 <= a_i <= 50$), where the $i$-th one, $a_i$, represents the length of the undirected channel between the $i$-th nest and the $((i bmod n) + 1)$-th nest. It is guaranteed that the total length of the $n$ channels is odd.The third line contains four integers $s_1, e_1, s_2$ and $e_2$ ($1 <= s_1, s_2, e_1, e_2 <= n$, $s_1 != e_1$, $s_2 != e_2$), representing the original nests where these ants live and their new nests.
## Output
For each test case, output a line with two space-separated numbers, representing the expected complexity for the first colony of ant and the expected complexity for the second colony respectively. Your answer is considered correct if the absolute or relative error between each number in your output and the corresponding one in Rikka's answer does not exceed $10^(-9)$. Formally, let a number of your answer be $a$, and the corresponding number of Rikka's answer be $b$. Your answer is considered correct if $frac(| a -b |, max (1 , | b |)) <= 10^(-9)$.
[samples]
## Note
What we are talking about including strategies, best strategies and expectations are actually what about Nash Equilibrium and mixed strategies.In the theory of games, a player is said to use a mixed strategy whenever the player chooses to randomize over the set of available actions. Formally, a mixed strategy is a probability distribution that assigns to each available action a likelihood of being selected. If only one action has a positive probability of being selected, the player is said to use a pure strategy. In the first sample case, the best strategies for both colonies are pure strategies.A mixed strategy profile is a list of strategies, one for each player in the game. A mixed strategy profile induces a probability distribution or lottery over the possible outcomes of the game. In this problem, the profiles are those plans that we discussed before.A Nash equilibrium (mixed strategy) is a strategy profile with the property that no single player can, by deviating unilaterally to another strategy, induce a lottery that he or she finds strictly preferable. In $1950$, the mathematician John Nash proved that every game with a finite set of players and actions has at least one equilibrium.In this problem, a Nash equilibrium is what you need to find. You may find out several different equilibriums. If some of them have the same unilateral strategy, their earnings must be constant.We still need to discuss when several different equilibriums without fixed unilateral strategy exist. Notice that in this case, we have a unique equilibrium with mixed, impure strategies. Since ants like to show-off their intelligence, this equilibrium is exactly their final choices.In the second test case, though we have three different equilibriums whose earnings are $(8, 10)$, $(13, 11)$ and $(14. 666 \\\\cdots, 14. 666 \\\\cdots)$, the last one is the earnings for the only equilibrium with mixed, impure strategies and thus is what we need.
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of nests and channels, arranged in a cycle.
Let $ a_i \in \mathbb{R}^+ $ for $ i \in \{1, \dots, n\} $ denote the length of the channel between nest $ i $ and nest $ (i \bmod n) + 1 $.
Let $ s_1, e_1, s_2, e_2 \in \{1, \dots, n\} $ be the start and end nests for colony 1 and colony 2, respectively, with $ s_1 \ne e_1 $, $ s_2 \ne e_2 $.
Let $ P_1 $ and $ P_2 $ denote the set of simple paths from $ s_1 $ to $ e_1 $ and from $ s_2 $ to $ e_2 $ along the cycle, respectively.
Each path is uniquely determined by its direction (clockwise or counterclockwise) due to the cycle structure.
Let $ L(p) = \sum_{e \in p} a_e $ denote the length of path $ p $.
For a pair of paths $ (p_1, p_2) \in P_1 \times P_2 $, define the **cost** for colony 1 as:
$$
C_1(p_1, p_2) = L(p_1) + 2 \cdot \sum_{e \in p_1 \cap p_2} a_e
$$
and for colony 2 as:
$$
C_2(p_1, p_2) = L(p_2) + 2 \cdot \sum_{e \in p_1 \cap p_2} a_e
$$
(since shared edges are tripled, adding an extra 2× their length).
**Constraints**
1. $ 1 \le T \le 5000 $
2. $ 2 \le n \le 50 $
3. $ 1 \le a_i \le 50 $ for all $ i $
4. Total length $ \sum_{i=1}^n a_i $ is odd
5. $ s_1 \ne e_1 $, $ s_2 \ne e_2 $
**Objective**
Find the unique Nash equilibrium in mixed strategies. Since each colony has at most two pure strategies (clockwise or counterclockwise path), the game is a $ 2 \times 2 $ bimatrix game.
Let the two pure strategies for colony 1 be $ p_1^{\text{cw}}, p_1^{\text{ccw}} $, and for colony 2 be $ p_2^{\text{cw}}, p_2^{\text{ccw}} $.
Construct the payoff matrix $ (C_1, C_2) $ for all 4 strategy pairs.
Due to the structure of the cycle and the odd total length, the game has a **unique** mixed-strategy Nash equilibrium (as guaranteed by the problem).
Let $ x \in [0,1] $ be the probability that colony 1 chooses its clockwise path, and $ y \in [0,1] $ the probability that colony 2 chooses its clockwise path.
The equilibrium $ (x^*, y^*) $ satisfies:
- Colony 1 is indifferent between its two pure strategies given $ y^* $:
$$
C_1(p_1^{\text{cw}}, y^*) = C_1(p_1^{\text{ccw}}, y^*)
$$
- Colony 2 is indifferent between its two pure strategies given $ x^* $:
$$
C_2(x^*, p_2^{\text{cw}}) = C_2(x^*, p_2^{\text{ccw}})
$$
Solve for $ x^* $ and $ y^* $, then compute the expected costs:
$$
\mathbb{E}[C_1] = x^* y^* C_1(p_1^{\text{cw}}, p_2^{\text{cw}}) + x^* (1 - y^*) C_1(p_1^{\text{cw}}, p_2^{\text{ccw}}) + (1 - x^*) y^* C_1(p_1^{\text{ccw}}, p_2^{\text{cw}}) + (1 - x^*) (1 - y^*) C_1(p_1^{\text{ccw}}, p_2^{\text{ccw}})
$$
$$
\mathbb{E}[C_2] = x^* y^* C_2(p_1^{\text{cw}}, p_2^{\text{cw}}) + x^* (1 - y^*) C_2(p_1^{\text{cw}}, p_2^{\text{ccw}}) + (1 - x^*) y^* C_2(p_1^{\text{ccw}}, p_2^{\text{cw}}) + (1 - x^*) (1 - y^*) C_2(p_1^{\text{ccw}}, p_2^{\text{ccw}})
$$
Output $ \mathbb{E}[C_1] $ and $ \mathbb{E}[C_2] $.