Intersection Order Query

Jerry draws \(N\) lines on paper, where each line is given by the equation \(y=k_ix+b_i\). Then, for each of \(M\) vertical lines defined by \(X=A_j\), Jerry wants to know the \(y\)-coordinate of the intersection that ranks \(K\)th from the bottom. Note that if \(x\) lines intersect \(X=A_j\) at the same point, that point is counted \(x\) times.

Input Format: The first line contains three integers \(N\), \(M\) and \(K\). Then \(N\) lines follow, each containing two integers \(k_i\) and \(b_i\). After that, \(M\) lines follow, each containing an integer \(A_j\) representing a vertical line \(X=A_j\).

Output Format: For each of the \(M\) queries, output the \(y\)-coordinate of the \(K\)th smallest intersection (when counting from the bottom) on a new line.

inputFormat

The first line of input consists of three integers \(N\), \(M\), and \(K\). The next \(N\) lines each contain two integers \(k_i\) and \(b_i\) which define the line \(y=k_ix+b_i\). The following \(M\) lines each contain one integer \(A_j\), representing the vertical line \(X=A_j\).

outputFormat

For each vertical line query, print a single number representing the \(y\)-coordinate of the \(K\)th smallest intersection point from the bottom. Each answer should be printed on a separate line.

sample

3 2 2
1 1
2 0
0 3
1
2

2
3