B'You are given a special undirected graph. It consists of 2n vertices numbered from 1 to 2n . The following properties hold for the graph: So, the graph can be represented as two trees having the same structure, and n edges connecting each vertex of the first tree to the corresponding vertex of the second tree. Edges of the graph are weighted. The length of some simple path in the graph is the sum of weights of traversed edges. You are given q queries to this graph; in each query, you are asked to compute the length of the shortest path between some pair of vertices in this graph. Can you answer all of the queries? The first line of the input contains one integer n ( 2 <= n <= 3 cdot 10^5 ). The second line contains n integers w_{1, 2} , w_{3,4} , ..., w_{2n - 1, 2n} ( 1 <= w_{i, i + 1} <= 10^{12} ). These integers describe the weights of the edges connecting odd vertices with even ones. Then n-1 lines follow. i -th line contains four integers x_i , y_i , w_{i, 1} and w_{i, 2} ( 1 <= x_i, y_i <= n , x_i ne y_i , 1 <= w_{i, j} <= 10^{12} ); it describes two edges: one connecting 2x_i - 1 with 2y_i - 1 and having weight w_{i, 1} ; another connecting 2x_i with 2y_i and having weight w_{i, 2} . The next line contains one integer q ( 1 <= q <= 6 cdot 10^5 ) -- the number of queries. Then q lines follow, i -th line contains two integers u_i and v_i ( 1 <= u_i, v_i <= 2n , u_i ne v_i ), describing a query "compute the length of the shortest path between vertices u_i and v_i ". Print q integers, i -th integer should be equal to the answer to the i -th query. The graph in the first test looks like that: '...