Công ty Alpha giới thiệu siêu máy tính có khả năng thực hiện được tỉ tỉ phép toán trong vòng 1 giây. Để chứng minh sức mạnh của siêu máy tính, công ty đã cho máy tính thực hiện một số lượng rất lớn các phép toán như sau:

• Ban đầu, số ~N~ được đặt giá trị bằng 1;
• Có ~t~ thao tác, mỗi thao tác thuộc một trong ba loại:
  • Nhân ~N~ với ~a^b~;
  • Chia ~N~ cho ~a^b~ (trong đó ~a^b~ là ước của ~N~);
  • Tìm hai số ~p, q~ mà ~p^q = N~ và ~q~ là lớn nhất, nếu ~N = 1~ thì ~p = 1, q = 1~.

Công ty sẽ trao thưởng cho người nào kiểm chứng được kết quả mà siêu máy tính đưa ra. Nhận thấy, các thí sinh tham gia kỳ thi Duyên Hải năm 2018 có thể kiểm chứng được, do đó, Ban giám khảo kỳ thi quyết định ra đề thi yêu cầu thí sinh viết chương trình nhận ~t~ thao tác, nhưng với mỗi thao tác loại 3 chỉ cần đưa ra hai số ~p \pmod M~ (phần dư của phép chia ~p~ cho ~M~) và ~q~.

Yêu cầu: Cho ~M~ và ~t~ thao tác, với mỗi thao tác loại 3 hãy đưa hai số ra ~p \pmod M~ và ~q~.

Input

• Dòng đầu chứa hai số nguyên dương ~M, t~ (~M \le 10^9~);
• Dòng thứ ~i~ trong ~t~ dòng tiếp theo mô tả thao tác thứ ~i~ là một trong ba loại thao tác theo khuôn dạng: Bắt đầu số ~k_i~ (~k_i~ bằng 1 hoặc 2 hoặc 3). Nếu là thao tác loại 1 và loại 2 thì tiếp theo là hai số nguyên dương ~a_i, b_i~ (~a_i, b_i \le 10^6~). Nếu là thao tác loại 3 thì không có thêm dữ liệu.

Output

Gồm một số dòng, mỗi dòng chứa hai số ~p \pmod M~ và ~q~ tìm được tương ứng với mỗi thao tác loại 3.

Sample Input 1

100 4
1 36 2
3
2 3 2
3

Sample Output 1

6 4
12 2

Subtasks

• Có 20% số test ứng với 20% số điểm của bài có ~t \le 100~ và số ~N~ không vượt quá ~10^{18}~ trong quá trình thực hiện dãy thao tác;
• Có 40% số test khác ứng với 40% số điểm của bài có ~t \le 100~ và số ~N~ không vượt quá ~10^{10^{180}}~ trong quá trình thực hiện dãy thao tác;
• Có 40% số test còn lại ứng với 40% số điểm còn lại của bài có ~t \le 10^5~.