Problem A: Add polynomials together

Problem A: Add polynomials together

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2500  Solved: 427
[Submit][Status][Web Board]

Description

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.

Input

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}]\).

Output

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

Sample Input

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

Sample Output

1 0 1 5

HINT

[Submit][Status]