"Take that money, watch it burn, sink in the river, the lessons I've learnt." The audience were so touched and bursted into tears after listening to the song "Counting Stars" performed by Onbert's band — Dawns In Drums.

Ulverc, being fascinated by the performance, decides to form a band by himself, but he quickly realises a problem: he cannot play the drum and sing at the same time! So, he finds two other (un)professional drummers, __jk__ and sharky to form a band.

Each and every drummer, whether professional or not (and so obviously including __jk__ and sharky), has a drum set which consists of $n$ drums, conveniently numbered from $1$ to $n$. For each integer $1 \le i \le n$, the $i$-th drum has a loudness of $a_i$.

The song Ulverc's band is performing has $m$ beats. For each beat $1 \le j \le m$, __jk__ hits drums numbered $w_j$ and $x_j$ on his own set of drums, where $w_j \neq x_j$, and sharky hits drums numbered $y_j$ and $z_j$ on his own set of drums, where $y_j \neq z_j$, simultaneously.

After recording a take that that they believe is perfect, they have sent it to Aniv the music producer. Aniv, being a professional music producer with extremely high standards, is unimpressed by their awful recording: the two drummers, __jk__ and sharky, have too contrasting and inconsistent volumes!

Aniv quantifies the "loudness difference" of a beat as the absolute difference between the sum of loudness of drums that __jk__ hits, and the sum of loudness of drums that sharky hits. Aniv's total dissatisfaction is then the sum of loudness differences over all $m$ beats. More formally, Aniv's dissatisfaction is given by $\sum_{j=1}^{m} |(a_{w_j}+a_{x_j}) - (a_{y_j} + a_{z_j})|$.

Aniv wants to edit their recording to minimise his final dissatisfaction. It takes exactly $1$ minute of time for him to pick any one of $w_1$, $w_2$, $\ldots$, $w_m$, $x_1$, $x_2$, $\ldots$, $x_m$, $y_1$, $y_2$, $\ldots$, $y_m$, $z_1$, $z_2$, $\ldots$, $z_m$, and change its value to any arbitrary integer between $1$ and $n$ inclusive, subject to the constraint that $w_j \neq x_j$ and $y_j \neq z_j$ still holds for all $1 \le j \le m$.

However, Aniv is not sure how much time he has left to edit their terrible recording! So, he asks you, a clever HKOI 2025 contestant for help. Aniv has now given you $q$ queries: for each query, tell him the minimum possible final dissatisfaction if he has $k$ minutes to edit their recording.

Input

The first line of the input contains a single positive integer $n$, denoting the number of drums.

The second line of the input contains $n$ positive integers $a_1$, $a_2$, $\ldots$, $a_n$, denoting the loudness of the drums.

The third line of the input contains a single positive integer $m$, denoting the number of beats of the piece.

The $i$-th ($1 \le i \le m$) of the next $m$ lines contain four positive integers each, representing the values of $w_i$, $x_i$, $y_i$ and $z_i$ respectively.

The $(m+4)$-th line of the input contains a single positive integer $q$, denoting the number of queries from Aniv.

The $i$-th ($1 \le i \le q$) of the next $q$ lines contain one positive integer each, denoting the number of minutes that Aniv has to edit the recording.

Output

Output $q$ lines. For each query, output, on one new line, a non-negative integer, denoting Aniv's minimum dissatisfaction for the corresponding value of $k$.

Constraints

For all test cases, $1 \le n,m \le 2 \times 10^5$, $1 \le a_i \le 10^9$ for all $1 \le i \le n$, $1 \le w_j, x_j, y_j, z_j \le n$, $w_j \neq x_j$, $y_j \neq z_j$ for all $1 \le j \le m$, $1 \le q \le 4 \times 10^5$, and $1 \le k \le 4 \times 10^5$ for all queries.

Subtask 1 (14 points): $a_i \le a_{i+1}$ for all $1 \le i < n$, and $w_j \le x_j \le y_j \le z_j$ for all $1 \le j \le m$.

Subtask 2 (7 points): $k \le 2$ for all queries.

Subtask 3 (21 points): $q \le 10$.

Subtask 4 (10 points): $m \le 15$.

Subtask 5 (21 points): $m \le 3000$.

Subtask 6 (27 points): No additional constraints.