As Narnal has learned in the class, a polynomial can be represented as a linked list, but he failed to add two given polynomials together. He asks you to help him to get the summation of two polynomials.

Submit: 1675 Solved: 247

[Submit][Status][Web Board]

As Narnal has learned in the class, a polynomial can be represented as a linked list, but he failed to add two given polynomials together. He asks you to help him to get the summation of two polynomials.

First line will be a positive integer \(T\), which is the number of test cases.

In each test case, the first line will be an integer \(n\) for the number of terms of the first polynomial. Then the next \(n\) lines will be the coefficients and exponents of the terms with the order of **increasing** exponents.

After \(n + 1\) lines, there will be an integer \(m\) for the number of terms of the second polynomial. Then the next \(m\) lines will be the coefficients and exponents of the terms with the order of **increasing** exponents.

After \(n + m + 2\) lines, there will be an integer \(q\) denoting the number of queries. Then one line containing \(q\) **ascending** numbers will follow, where each number \(k\) represents a query for the coefficient of exponent of \(k\).

\(1 \leq T \leq 200, 1 \leq n, m \leq 10^{3}, 1 \leq q \leq 2 \times 10^{3}, 0 \leq k \leq 10^{9}\). The **coefficients** will be in range \([-10^{4}, 10^{4}]\). The **exponents** will be in range \([0, 10^{9}]\).

For each case, output one line contains \(q\) answers of the corresponding queries.

```
1
2
1 1
2 3
3
1 100
3 150
5 170
4
1 20 100 170
```

`1 0 1 5`