Như các bạn đã biết, mọi số nguyên \(n,|n|>1\) đều có thể biểu diễn dưới dạng tích các số nguyên tố.

Không chỉ vậy, các số hữu tỉ cũng biểu diễn được dưới dạng này, nếu như ta coi phép chia có vai trò tương tự như phép nhân. Ví dụ \(\frac{2}{15} = 2^1*3^{-1}*5^{-1}\). Hôm nay tôi dạy các bé tiểu học, vừa hay cũng đến bài "Nhân 2 số", "Chia 2 số". Có bài toán như sau: Cho 2 số nguyên dương \(x\) và \(y\) dưới dạng phân tích TSNT (thừa số nguyên tố), ghi ra số \(x \times y\) và \(x/y\) cũng dưới dạng đó trên 2 dòng.

Mời các bạn thử sức với BTVN này.

Input

• Dòng đầu tiên chứa số \(n_x\) là số lượng TSNT của số \(x\).

• Dòng thứ 2 chứa \(n_x\) số \(a_i, b_i\) với ý nghĩa \(x = a_1^{b_1} . a_2^{b_2} . \cdots a_i^{b_i} . \cdots . a_{n_x}^{b_{n_x}}\)

• Dòng thứ 3 chứa số \(n_y\) là số lượng TSNT của số \(y\).

• Dòng thứ 4 chứa \(n_y\) số \(c_j, d_j\) với ý nghĩa \(y = c_1^{d_1} . c_2^{d_2} . \cdots c_j^{d_j} . \cdots . c_{n_y}^{d_{n_y}}\)

Dữ kiện vào đảm bảo

• \(a_i,c_j\) là các SNT \(\le 10^6 + 500\).
• \(b_i,d_j\) là các số nguyên dương, \(1 \le b_i,d_j \le 10^6\)
• \(a,c\) là 2 dãy tăng nghiêm ngặt
• \(1 \le n_x, n_y \le 100\) và \(x \neq y\).

Output

• Hai dòng đầu tiên chứa số lượng TSNT và các cặp thừa số, số mũ sắp tăng dần (như input) biểu diễn giá trị \(x \times y\)

• Hai dòng kế tiếp biểu diễn giá trị \(x/y\)

Example

    3
    2 2 3 1 5 1
    1
    5 2

    3
    2 2 3 1 5 3
    3
    2 2 3 1 5 -1