Effective Resistance in a Power Strip Tree

Allison has bought n identical power strips. Her home has a single wall socket. She connects the power strips in a tree‐like structure: each power strip (except the root, which is numbered 1) is plugged into some socket of another power strip, and no cycles occur.

Each power strip has three wires: hot (1), neutral (2) and ground (3). When a power strip with number a_i is connected to its parent f_i, the connection is modeled by nine resistance values. In particular, for each pair x,y in \(\{1,2,3\}\), the resistor R(a_i,f_i,x,y) represents the resistance between the x-wire on power strip a_i and the y-wire on its parent power strip f_i. (Note that even connections such as hot to neutral or other combinations may have non‐negligible resistances.)

Assume that within each power strip the three wires are internally connected with negligible resistance. Therefore, when current passes from one power strip to its parent, the only resistance encountered is that on the connecting cable, which depends on the starting wire at the child and the target wire at the parent.

Since the internal wiring makes all wires of a power strip effectively at the same potential, when traveling along the tree, you are free to choose the optimal connection at every intermediate power strip so as to minimize the resistance contribution. However, at the first edge on the upward journey from a queried power strip, you must use the specified starting wire, and at the last edge on the downward journey toward the queried power strip, you must end at the specified target wire.

Formally, for every power strip i (\(2\le i\le n\)) with parent f_i, define:

[ \text{cost_up}(i, x) = \min_{1\le y\le 3} R(i, f_i, x, y),\quad \text{for } x\in{1,2,3}, ]

[ U(i) = \min_{x,y\in{1,2,3}} R(i, f_i, x, y). ]

Similarly, define

[ \text{cost_down}(i, y) = \min_{1\le x\le 3} R(i, f_i, x, y),\quad \text{for } y\in{1,2,3}. ]

</p>

Consider a query that asks for the effective resistance between the x-wire of power strip u and the y-wire of power strip v. Let L be the lowest common ancestor (LCA) of u and v in the tree. Then the effective resistance is calculated as the sum of the contributions along the unique path from u to L plus the sum along the unique path from v to L, where:

• For the upward path from u to L: if u = L, the cost is 0; otherwise, let the first edge (from u to its parent) contribute \(\text{cost_up}(u, x)\) (using the query‐specified starting wire). Every subsequent edge on this path contributes \(U(\cdot)\) (since the parent's wiring is free to choose).
• For the downward path from L to v: if v = L, the cost is 0; otherwise, let the last edge (into v) contribute \(\text{cost_down}(v, y)\) (using the query‐specified target wire). Every preceding edge on this path (when moving upward from v to L) contributes \(U(\cdot)\).

Your task is to answer q queries. For each query, given u, x, v, y, compute the effective resistance between the x-wire of u and the y-wire of v by summing the contributions along the unique path from u to v (via their LCA).

---

Input Format:

• The first line contains an integer n (the number of power strips).
• The next n-1 lines describe power strips 2 through n. Each of these lines begins with an integer f (the parent's index) followed by 9 integers representing the 9 resistance values for that power strip in row-major order: first the three values for x=1 (for y=1,2,3), then for x=2, and then for x=3.
• The next line contains an integer q (the number of queries).
• Each of the next q lines contains four integers: u x v y representing a query asking for the effective resistance between the x-wire of power strip u and the y-wire of power strip v.

Output Format:

• For each query, output a single integer representing the effective resistance.

Note: It is guaranteed that power strip 1 is the root (with no parent), and the tree connections do not form any cycles.

inputFormat

The input begins with an integer n.

• Then n-1 lines follow. Each line contains an integer f and 9 integers: the resistance values for the connection between the current power strip and its parent.
• Next, an integer q is given.
• Then q lines follow, each with four integers: u x v y.

outputFormat

Output q lines. Each line contains the effective resistance (an integer) for the corresponding query.

sample

3
1 1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 2 2
3
2 1 3 1
2 2 2 3
3 3 2 2

3
0
3

</p>