Background

Jerry really likes drawing straight lines on paper.

Problem Description

Jerry has drawn $N$ lines on paper. Each line can be written as $y = k_i x + b_i$. Now Jerry wants to know, for each of the $M$ lines that can be written as $X = A_j$, what the $y$-coordinate is of the intersection point that ranks $K$-th when counted from bottom to top.

If $x$ lines intersect a line $X = A_j$ at the same point, it is counted as $x$ points.

Input Format

The first line contains three positive integers $N, M, K$.

The next $N$ lines each contain two non-zero integers $k_i$ and $b_i$, describing one line.

The next $M$ lines each contain one integer $A_j$, representing a query.

Output Format

Output $M$ lines. Each line contains one integer, representing the answer.

2 3 1
1 2
2 1
0
1
2

1
3
4

Hint

For $30\%$ of the testdata, $1 \leqslant N, M \leqslant 2000$.
For $100\%$ of the testdata, $1 \leqslant N \leqslant 2000$, $1 \leqslant M \leqslant 5 \times 10^5$.

All other input numbers are within the int range, and it is guaranteed that $1 \leqslant K \leqslant N$.

Friendly reminder: if you are not confident about the constant factor of your solution, please inhale oxygen (use O2 optimization). If you are fully confident, go ahead and do whatever you want.

$\color{white}{\text{int*int会爆int!!!}}$

Translated by ChatGPT 5