Problem Description

In this world, there are $ N $ countries, each with the numbers $1, 2, 3, \ldots, N$. These countries have not cooperated with each other until now. However, due to increasing disparities between countries and the growing number of countries seeking support, they have decided to establish diplomatic relations and support each other.

The current situation of each country is represented by two integers $ X_i, P_i $, where $ X_i $ is the maximum amount of support that country $ i $ can give or receive, and $ P_i $ represents the number of citizens that can be helped according to the amount of support.

Specifically,
Countries with $X_i \ge 0$ can provide support to other countries, and can provide a total of $ |X_i| $ support in one year.
Countries with $ X_i < 0 $ can receive support from other countries, and can receive a total of $ |X_i| $ support in one year.
It is known that if country $ i $ receives a total of $x (x \le |X_i|)$ support, $P_i \times x$ citizens can be helped.

Currently, no countries have diplomatic relations, but they have plans to establish $ Q $ years of diplomatic relations. The plan is to establish one diplomatic relation each year, where at the beginning of the $ j $-th year, countries $ a_j $ and $ b_j $ will establish diplomatic relations.

Following this $ Q $ year plan, determine the maximum number of people that can be saved through support for each $ j $-th year.

Note that a country can provide support to countries with which it has direct diplomatic relations or countries that are indirectly connected through multiple diplomatic relations.

Input Format

The input is given from the standard input in the following format:

$ N $ $ X_1 $ $ P_1 $ $ X_2 $ $ P_2 $ $\vdots$ $ X_N $ $ P_N $ $ Q $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $\vdots$ $ a_Q $ $ b_Q $

Output Format

Output $ Q $ lines. The $ i $-th line should contain the maximum number of people that can be helped in the $ i $-th year according to the planned diplomatic relations.

Sample Input and Output

Sample Input #1

3
2 0
3 0
-4 2
2
1 3
1 2

Sample Output #1

4
8

Sample Input #2

4
-5 1
-3 3
1 0
6 0
5
1 4
1 2
2 4
2 3
3 4

Sample Output #2

5
12
12
13
13

Sample Input #3

4
-2 1
-3 5
-1 2
-3 8
3
1 2
2 3
3 4

Sample Output #3

0
0
0

Notes/Hints

Constraints

• All inputs are integers.
• $2 \le N \le 10^5$
• $1 \le Q \le \min(10^5, N(N-1)/2)$
• $0 \le |X_i| \le 10^9$
• $\sum |X_i| \le 10^9$
• $1 \le P_i \le 10^9 \ (X_i < 0)$
• $P_i = 0 \ (X_i \ge 0)$
• $1 \le a_i, b_i \le N$
• $a_i \ne b_i$
• $(a_i, b_i) \ne (a_j, b_j)$ for $i \ne j$

Sample Explanation 1

• In the 1st year, providing $ 2 $ units of support from country 1 to country 3 can help $ 4 $ people.
• In the 2nd year, providing $ 1 $ unit of support from country 1 to country 3 and $ 3 $ units of support from country 2 to country 3 via country 1 can help a total of $ 8 $ people.

Sample Explanation 3

• Since there are no countries that can provide support, no matter how many diplomatic relations are established, the number of people saved will be $ 0 $.

见题面 Input 部分

见题面 Output 部分