Metal Recycling

Time Limit : 2 sec, Memory Limit : 262144 KB

貴金属リサイクル

会津特産の貴金属であるアイヅニウムをリサイクルするPCK社は、全国各地にネットワークを持ち、たくさんの回収車でアイヅニウムを集めてきます。この会社は、処理の効率化のために、塊の重さと個数の単位を規格で定めています。

塊の重さには「ボッコ」という単位を使います。x ボッコのアイヅニウムの重さは 2xグラムです。宝石で例えると、「カラット」のようなものです。また、塊の個数には「マルグ」という単位を使います。y マルグは 2y 個です。1箱に入っている品物の個数である「ダース」のようなものです。ただし、xy は 0 以上の整数でなければいけません。

回収車 i は、 ai ボッコの重さのアイヅニウムを bi マルグずつ集めます。こうして集まったアイヅニウムを、炉の中に入れて溶かし、いくつかのアイヅニウムの塊を再生しますが、なるべくアイヅニウムの塊の数が少なくなるようにします。このとき、集めてきたアイヅニウムの重さの合計と、再生してできるアイヅニウムの重さの合計は変わりません。

回収車が集めたアイヅニウムの塊のボッコ単位の重さとマルグ単位の個数が与えられたとき、再生後のアイヅニウムの塊の数が最小になるような結果を求めるプログラムを作成せよ。

Input

入力は以下の形式で与えられる。

N
a1 b1
a2 b2
:
aN bN

1行目に、回収車の数 N (1 ≤ N ≤ 100000) が与えられる。続く N 行に、回収車 i が回収したアイヅニウムの塊の、「ボッコ」単位の重さを表す整数 ai (0 ≤ ai ≤ 100000) と「マルグ」単位の個数を表す整数 bi (0 ≤ bi ≤ 100000) が与えられる。

Output

再生した後に得られるアイヅニウムの塊の数が最小になるような、ボッコ単位の重さとマルグ単位の個数を、重さの小さい順に出力する。

Sample Input 1

3
2 1
1 3
2 2

Sample Output 1

3 0
5 0

Sample Input 2

1
100000 2

Sample Output 2

100002 0

Source: PC Koshien 2015 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2015-11-7
http://web-ext.u-aizu.ac.jp/pc-concours/