Jerry Loves Lines
题目背景
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$行,每一行一个整数表示答案.
输入输出样例
输入样例 #1
2 3 1
1 2
2 1
0
1
2
输出样例 #1
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!!!}}$