题目背景

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*10^5$

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

温馨提示:如果对自己的做法的常数感到不放心,请吸入氧气..(食用O2优化)如果有着充足自信,尽管放手浪..

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