题目描述

有 $n$ 个线性序列，第 $i$ 个序列可以表示成 $k_i×x+b_i$ 的形式 $(x=0,1,2,…)$。

现在询问将这些序列的数从小到大合并起来，前 $m$ 个数分别是多少（重复出现的数合并后也会多次出现）。

输入格式

输入第一行一个数 $n$。

接下来 $n$ 行每行两个数表示 $k_i,b_i$。

最后一行一个数 $m$，代表答案需要前 $m$ 个数。

输出格式

输出 $m$ 个数，表示答案。

2
1 2
5 2
8

2 2 3 4 5 6 7 7

样例解释

两个数列分别为 $[2,3,4,5,6,7,8,…]$ 和 $[2,7,12,…]$。

数据规模

对于100%的数据，保证 $1≤n≤20000,1≤m≤10000,1≤k_i,b_i≤1000$。