Siêu máy tính

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:
  1. Nhân $N$ với $a^b$;
  2. Chia $N$ cho $a^b$ (trong đó $a^b$ là ước của $N$);
  3. Tìm hai số nguyên dương $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ố $pmodM$ (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 ra hai số $pmodM$ và $q$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên dương $M,t$ ($M\le {10}^9$; $t\le {10}^5$);
• Dòng thứ $i$ trong $t$ dòng tiếp theo mô tả thao tác thứ $i$ theo khuôn dạng: bắt đầu là 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.

Dữ liệu đảm bảo ở mỗi thao tác loại $2$, $a_i^{b_i}$ là ước của $N$ hiện tại, và có ít nhất một thao tác loại $3$.

Dữ liệu ra

In ra một số dòng, mỗi dòng chứa hai số $pmodM$ và $q$ tìm được, tương ứng với các thao tác loại $3$ theo thứ tự xuất hiện.

Ràng buộc

• $1\le M\le {10}^9$; $1\le t\le {10}^5$;
• $k_i\in \{1,2,3\}$; $1\le a_i,b_i\le {10}^6$.

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}^{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$.

Ví dụ