Giai thừa của một số tự nhiên là tích của tất cả các số nguyên dương nhỏ hơn hoặc bằng nó. Ví dụ, giai thừa của 4 là \(1 × 2 × 3 × 4 = 24\). Giả giai thừa của \(n\) giống với giai thừa của \(n\), nhưng có một điểm khác là có đúng một thừa số bị thay thế bởi một số nguyên dương nhỏ hơn nó. Ví dụ: !1 × 2 × 2 × 4 = 16$ là một giả giai thừa của 4.

Yêu cầu: Cho số tự nhiên \(n\), một môđun nguyên tố \(p\) và một số dư \(r\), hãy tìm giả giai thừa của \(n\) sao cho nó có số dư \(r\) khi chia cho \(p\).

Input

• Một dòng chứa 3 số nguyên \(n, p\) và \(r\) (\(2 \le n \le 10^{18}, 2 \le p < 10^7, 0 \le r < p\)) như mô tả ở trên.

Output

• Nếu không có giả giai thừa nào thỏa mãn thì ghi ra “-1 -1”. Ngược lại ghi ra hai số nguyên tương ứng là thừa số \(k\) (\(2 \le k \le n\)) và giá trị \(v\) của số thay thế thừa số (\(1 \le v < k\)). Nếu có nhiều cặp (\(k, v\)) thỏa mãn thì đưa ra cặp (\(k, v\)) nhỏ nhất theo thứ tự từ điển.

Scoring

• Subtask \(1\) (\(41\%\) số điểm): \(n \le 14.\)
• Subtask \(2\) (\(21\%\) số điểm): \(r = 0.\)
• Subtask \(3\) (\(38\%\) số điểm): Như ràng buộc gốc.

Example

4 5 1

3 2

4 127 24

-1 -1