Phân số

Hồng và Hà đang ôn tập kiến thức về phân số. Cho một dãy các phân số, mỗi phân số có tử số và mẫu số đều là các số nguyên dương. Hãy tính tổng của các phân số đó.

Các phân số trong dãy chưa chắc đã tối giản. Dữ liệu được cho sao cho trong quá trình tính toán hợp lí (khi rút gọn phân số ở mỗi bước cộng), các kết quả đều nằm trong phạm vi kiểu số nguyên 32 bit có dấu.

Yêu cầu: Tính tổng các phân số và in kết quả ở dạng tối giản theo quy tắc ở phần Dữ liệu ra.

Input

Dữ liệu vào Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương \(n\) là số lượng phân số.

• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(x_i\) và \(y_i\) lần lượt là tử số và mẫu số của phân số thứ \(i\).

Ràng buộc:

• \(80\%\) số test ứng với \(80\%\) số điểm thỏa mãn \(1 < n \le 3\), \(x_i, y_i \le 10^9\).

• \(20\%\) số test ứng với \(20\%\) số điểm thỏa mãn \(3 < n \le 100\), \(x_i, y_i \le 50\).

Output

In ra

• Nếu kết quả là một số nguyên thì chỉ in ra số nguyên đó.

• Nếu tử số nhỏ hơn mẫu số thì in tử số và mẫu số (của phân số tối giản) trên cùng một dòng, cách nhau một dấu cách.

• Nếu tử số lớn hơn mẫu số thì in phân số dưới dạng hỗn số: lần lượt phần nguyên, tử số, mẫu số (phần phân số tối giản), trên cùng một dòng, cách nhau một dấu cách.

Example 1

Input:

2
4 3
3 2

Output:

2 5 6

Example 2

Input:

2
1 2
1 3

Output:

5 6

Example 3

Input:

2
4 3
2 3

Output:

2

Note

Ví dụ 1: \(\frac{4}{3} + \frac{3}{2} = \frac{17}{6}\). Vì \(17 > 6\) nên chia \(17\) cho \(6\) được phần nguyên là \(2\) và dư \(5\), hỗn số là \(2\frac{5}{6}\), kết quả in ra là 2 5 6.

Ví dụ 2: \(\frac{1}{2} + \frac{1}{3} = \frac{5}{6}\). Vì \(5 < 6\) nên in ra tử số và mẫu số là 5 6.

Ví dụ 3: \(\frac{4}{3} + \frac{2}{3} = \frac{6}{3} = 2\) là số nguyên nên in ra 2.