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.
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