2509 - 纸币
Description

有 n 种纸币,其中对于第 i(1≤i≤n) 种纸币,它的面值是 a_i 元,我们有 b_i 张这种纸币。

请求出在不找零的情况下,用这些纸币能否**正好**付 x元,请你从小到大输出这些钱



Input

第一行一个数字n,表示钱币的种类

接下来每行两个数字a_i,b_i用来表示面值和几张 


Output

按顺序输出所有能支付的x_i

Examples

Input

2
1 2
2 3

Output

1
2
3
4
5
6
7
8

Input

2
1 2
5 3

Output

1 
2 
5 
6 
7 
10 
11 
12 
15 
16 
17
Hint

保证 1≤n≤50,1≤ai≤100,1≤bi≤50。

题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 39
通过次数 21