Background

小 $Q$ 研究了一个序列！

Description

小 $Q$ 想到了一个序列，第 $i$ 个集合就是 $k_i\times x+b_i(x=0,1,2...)$ 的形式。

小 $Q$ 想知道前 $m$ 小的项，由于他不会，所以他就来求助你啦。

Format

Input

第一行一个整数 $n$。

然后有 $n$ 行，每行两个数 $k_i,b_i$。

最后一个数 $m$。

Output

$m$ 个数，表示前 $m$ 小的数。

Samples

2
1 2
5 2
8

2 2 3 4 5 6 7 7

Limitation

两组序列分别为：$2,3,4,5,6,7,8...$，$2,7,12...$。

对于 $100\%$ 的数据：$1 \le n \le 10^7, 1\le m \le 10^7, 1\le k, b\le 1000$。