题目背景

Jerry 很喜欢在纸上面画直线呢。

题目描述

Jerry 在纸上面画上了 $N$ 条直线，每一条直线都可以用 $y=k_ix+b_i$ 来表示。现在 Jerry 想知道对于 $M$ 条可以表示为 $X=A_j$ 的直线，从下往上数排名第 $K$ 的交点的 $y$ 坐标是多少。

如有 $x$ 条直线与一条 $X=A_j$ 的直线交于同一点，算 $x$ 个点。

输入格式

第一行三个正整数 $N,M,K$。

接下来 $N$ 行，每一行两个非零整数 $k_i$ 和 $b_i$ 描述了一条直线。

接下来 $M$ 行，每行一个整数 $A_j$ 表示一个询问。

输出格式

$M$ 行，每一行一个整数表示答案。

2 3 1
1 2
2 1
0
1
2

1
3
4

提示

对于 $30\%$ 的数据，$1 \leqslant N,M \leqslant 2000$；
对于 $100\%$ 的数据，$1 \leqslant N \leqslant 2000$，$1 \leqslant M \leqslant 5\times10^5$。

其他所有读入的数全在 int 范围内，且保证 $1 \leqslant K \leqslant N$。

温馨提示：如果对自己的做法的常数感到不放心，请吸入氧气（食用 O2 优化）如果有着充足自信，尽管放手浪。

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