Chitanda owns a farm with $n$ apple trees on it, labeled by $1, 2, \\dots, n$, the $i$-th apple tree has $a_i$ apples. There are $n -1$ bidirectional roads connecting them. For all $i > 1$, an apple tree number $i$ is connected by a road to the apple tree number $floor.l frac(i, 2) floor.r$. So the map of the farm is also like a tree.
Apple business is booming. There are $m$ requests, labeled by $1, 2, \\dots, m$. For the $i$-th request, Chitanda can sell the customer at most $c_i$ apples, and the customer will pay $w_i$ dollars for each apple. Unfortunately, different customers have different preferences. Specifically, for the $i$-th request, the customer will give two integers $u_i$ and $v_i$, denoting he only accepts apples from trees on the shortest path from the $u_i$-th apple tree to the $v_i$-th apple tree on the map(include $u_i$ and $v_i$).
Assume the root of the map is the $1$-th apple tree. It is amazing that $u_i$ is always $v_i$'s ancestor or $u_i = v_i$.
The farm may not be able to sell $c_i$ apples to each customer. Please write a program to help Chitanda sell apples that will maximize his profits.
The first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.
In each test case, there are two integers $n, m (1 <= n, m <= 100000)$ in the first line, denoting the number of apple trees and requests.
In the second line, there are $n$ integers $a_1, a_2,..., a_n (1 <= a_i <= 10^9)$, denoting the number of apples on each apple tree.
For the next $m$ lines, each line contains four integers $u_i, v_i, c_i, w_i (1 <= u_i, v_i <= n, 1 <= c_i <= 10^9, 1 <= w_i <= 10^4)$, denoting each request. It is guaranteed that $u_i$ is $v_i$'s ancestor or $u_i = v_i$.
It is guaranteed that $sum n <= 10^6$ and $sum m <= 10^6$.
For each test case, print a single line containing an integer, denoting the maximum profits.
## Input
The first line of the input contains an integer $T (1 <= T <= 1000)$, denoting the number of test cases.In each test case, there are two integers $n, m (1 <= n, m <= 100000)$ in the first line, denoting the number of apple trees and requests.In the second line, there are $n$ integers $a_1, a_2,..., a_n (1 <= a_i <= 10^9)$, denoting the number of apples on each apple tree.For the next $m$ lines, each line contains four integers $u_i, v_i, c_i, w_i (1 <= u_i, v_i <= n, 1 <= c_i <= 10^9, 1 <= w_i <= 10^4)$, denoting each request. It is guaranteed that $u_i$ is $v_i$'s ancestor or $u_i = v_i$.It is guaranteed that $sum n <= 10^6$ and $sum m <= 10^6$.
## Output
For each test case, print a single line containing an integer, denoting the maximum profits.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ n_k \in \mathbb{Z} $ be the number of operations.
- Let $ p_k, q_k, m_k \in \mathbb{Z} $, and $ SA_k, SB_k, SC_k \in \mathbb{Z} $ be seed parameters.
- Define the pseudorandom generator function $ \text{rng61}_k : \mathbb{Z} \to \mathbb{Z} $ as:
$$
\text{rng61}_k() =
\begin{cases}
SA_k \gets SA_k \oplus (SA_k \ll 16) \\
SA_k \gets SA_k \oplus (SA_k \gg 5) \\
SA_k \gets SA_k \oplus (SA_k \ll 1) \\
t \gets SA_k \\
SA_k \gets SB_k \\
SB_k \gets SC_k \\
SC_k \gets SC_k \oplus t \oplus SA_k \\
\text{return } SC_k
\end{cases}
$$
- Define the sequence of operations $ O_k = (o_{k,1}, \dots, o_{k,n_k}) $, where for each $ i \in \{1, \dots, n_k\} $:
$$
o_{k,i} =
\begin{cases}
\text{PUSH}(v) & \text{if } \text{rng61}_k() \bmod (p_k + q_k) < p_k, \text{ where } v = \text{rng61}_k() \bmod m_k + 1 \\
\text{POP}() & \text{otherwise}
\end{cases}
$$
- Let $ S_k = (s_{k,1}, s_{k,2}, \dots) $ be the stack state after each operation, initialized as empty.
- Let $ a_{k,i} \in \mathbb{Z}_{\ge 0} $ be the maximum element in $ S_k $ after the $ i $-th operation, or $ 0 $ if the stack is empty.
**Constraints**
1. $ 1 \le T \le 50 $
2. $ 1 \le n_k \le 5 \times 10^6 $
3. $ 1 \le p_k, q_k, m_k \le 10^9 $
4. $ 10^4 \le SA_k, SB_k, SC_k \le 10^6 $
**Objective**
For each test case $ k $, compute:
$$
y_k = \bigoplus_{i=1}^{n_k} (i \cdot a_{k,i})
$$
where $ \oplus $ denotes bitwise XOR.
Output: `Case #x: y` for each test case $ x = k $.