Cho hai phương trình đồng dư: \(x \equiv a_1 \pmod{m_1}\) \(x \equiv a_2 \pmod{m_2}\) với \(\gcd(m_1, m_2) = 1\). Giải hệ phương trình này.

Định dạng đầu vào

• Một dòng chứa bốn số \(a_1, m_1, a_2, m_2\) (\(0 \le a_i < m_i \le 10^9\), \(\gcd(m_1, m_2) = 1\)).

Định dạng đầu ra

• Hai số nguyên \(x\) và \(M\), với \(x\) là nghiệm không âm nhỏ nhất, \(M = m_1 \times m_2\).

Ví dụ

Input:

2 3 3 5

Output:

8 15

Giải thích: \(x = 8\) thỏa \(8 \equiv 2 \pmod{3}\) và \(8 \equiv 3 \pmod{5}\). \(M = 15\).

Ràng buộc

• 100% số điểm: \(m_i \le 10^9\).