Một ngày Chủ nhật tháng 10 năm 20XX, cậu ~T~, một cựu học sinh chuyên Toán - Tin của trường THPT Chuyên Học Lỏm và hiện đang là sinh viên trường Học đại Mấy khoa, khi đang tìm kiếm tập tài liệu "Cấu trúc dữ liệu và giải thuật" thì bỗng nhiên một tờ giấy từ trên nóc rơi xuống đất. Khi nhặt tờ giấy đó lên, một số dòng chữ đập thẳng vào mắt cậu ta:

• Một phố nhỏ có 44 người trong độ tuổi từ 1 đến 85 (tuổi của mỗi người là một số nguyên dương).
• Chứng minh rằng trong số những người trên có hai người cùng tuổi hoặc có ba người mà tuổi của một người bằng tổng số tuổi của hai người kia.

--- Trích câu 5 đề thi chọn HSG cấp tỉnh Toán THCS năm 2022-2023, Sở GD&ĐT Quảng Ninh.

Được biết rằng bài toán trên có thể giải bằng cách áp dụng Nguyên lý ngăn kéo Dirichlet. Bài toán HSG thời cấp 2 ấy vô tình khiến ~T~ khơi gợi lại cảm giác ham học với môn Toán đã chôn vùi trong tâm trí của anh. Ngay ngày hôm sau, ~T~ đã rủ mấy ông bạn cùng giường, à nhầm cùng phòng, để cùng chui đầu vào thử chế những bài toán "kinh dị" để thử sức làm cùng nhau cho đỡ chán vì đang trong kỳ nghỉ dài nhưng không được về nhà.

Tuy nhiên, sau 6636 phút mà chưa nghĩ ra bài toán nào thực sự hay để cùng thử giải (có thể do bài đó quá dễ, hoặc cũng có thể bị bí ý tưởng), bỗng cậu ~N~, bạn cùng phòng của ~T~, nảy ra ý kiến:

• Hay là anh em mình làm tí marathon giải toán nhỉ? Ai làm được hết trong thời gian nhanh nhất thì được ae mời cơm cả ngày :)))

Sau lời gợi ý nho nhỏ của ~N~, ai cũng thấy rằng đó là trường hợp khả thi nhất có thể. Được sự nhất trí của mọi người trong phòng, ~T~ --- sinh viên khoa I(love)T1 "duy nhất" của phòng (chắc do cả phòng fan GenG, BLG, ...) --- bắt đầu mở laptop của mình để nhờ "công cụ hỗ trợ học tập và làm việc thời đại mới - ChatFFT" sinh ra ~N~ bài tập để cả phòng cùng làm. Anh ta dự kiến rằng có đúng ~36~ dạng bài tập để mọi người thử sức bao gồm ~2~ mức độ khó chính:

Mức 1 (Dễ / Vừa): 18 loại truy vấn đầu thuộc loại "cơ bản"

1. cmp x y: So sánh hai số nguyên ~x, y~ (~|x|, |y| \le 1.8 \times 10^{3*6}~).

2. + x y: Cộng hai số nguyên ~x, y~ (~|x|, |y| \le 3.6 \times 10^{3 \times 6}~).

3. * x y: Nhân hai số nguyên ~x, y~ (~|x|, |y| \le 10^{3+6}~).

4. rn x: Làm tròn xuống số thực ~x~ (~|x| \le 3.6 \times 10^{3+6}~).

5. / x y: Tính ~\lfloor \frac{x}{y} \rfloor~ (~|x|, |y| \le 1.8 \times 10^{3+6}; y \ne 0~).

6. % x y: Tính ~x \bmod y~ (~|x|, |y| \le 3.6 \times 10^{3 \times 6}; x,y \in \mathbb{Z}; y \ne 0~).

7. tg x y: Tối giản phân số ~\frac{x}{y}~ (~0 \le x,y \le 10^{3+6}; x,y \in \mathbb{Z}; y \ne 0~).

8. comp u v x y: So sánh hai phân số ~\frac{u}{v}, \frac{x}{y}~ (~|u|, |v|, |x|, |y| \le 1.8 \times 10^{3+6}; u,v,x,y \in \mathbb{Z}; v,y \ne 0~).

9. ++ u v x y: Tính và rút gọn ~\frac{u}{v}+\frac{x}{y}~ (~|u|, |v|, |x|, |y| \le 1.8 \times 10^{3+6}; u,v,x,y \in \mathbb{Z}; v,y \ne 0~).

10. ** u v x y: Tính và rút gọn ~\frac{u}{v}\cdot\frac{x}{y}~ (~|u|, |v|, |x|, |y| \le 1.8 \times 10^{3+6}; u,v,x,y \in \mathbb{Z}; v,y \ne 0~).

11. digit n: Tính tổng các chữ số của số nguyên dương ~n~. (~n \le 1.8 \times 10^{3 \times 6}~).

12. sq n: Kiểm tra xem số nguyên dương ~n~ có phải là số chính phương hay không. (~n \le 1.8 \times 10^{3 \times 6}~).

13. prm x: Kiểm tra tính nguyên tố của số nguyên dương ~x~ (~x \le 3.6 \times 10^{\sqrt{36}}; x \in \mathbb{N}^{*}~).

14. gcd x y: Tính ước chung lớn nhất của hai số ~x, y~ (~|x|, |y| \le 3.6 \times 10^{3 \times 6}; x,y \in \mathbb{N}~).

15. lcm x y: Tính bội chung nhỏ nhất của hai số ~x, y~ (~|x|, |y| \le 1.8 \times 10^{3+6}; x,y \in \mathbb{N}~).

16. sigma n: Tính ~\sum_{x=1}^{n} x~, tức tổng các số nguyên dương từ ~1~ tới ~n~. (~n \le 10^{3+6}~).

17. ptg x y: Tính độ dài cạnh huyền của tam giác vuông có hai cạnh bên có số đo ~a, b~ (~0 \le a,b \le 1.8 \times 10^{3+6}; a,b \in \mathbb{N}^{*}~).

18. xor x y: Tính ~x \oplus y~. Phép XOR (~\oplus~) có thể tham khảo ở đây. (~0 \le x,y \le 3.6 \times 10^{3+6}; x,y \in \mathbb{N}~).

Mức 2 (Trung bình / Khó): 18 loại truy vấn cuối thuộc loại "không cơ bản"

1. im x: Tính nghịch đảo modulo của ~x~ modulo ~18\,36\,67\,67~ (~x \le 36 \times 10^{\sqrt{36}}; x \in \mathbb{N}^{*}~).

2. log x y: Tính ~\mathrm{log}_{y} x~ (~1 \le x \le 10^{3+6}; 1 \le y \le 36; x,y \in \mathbb{N}~).

3. dist x_1 y_1 x_2 y_2: Tính khoảng cách Euclid giữa hai điểm ~(x_1,y_1)~ và ~(x_2,y_2)~. (~|x_1|, |y_1|, |x_2|, |y_2| \le 1.8 \times 10^{\sqrt{36}}; x_1,y_1,x_2,y_2 \in \mathbb{Z}~).

4. pt1 a b: Giải phương trình bậc nhất một ẩn: ~ax+b=0~ (~|a|, |b| \le 3.6 \times 10^{3+6}; a \ne 0; a,b \in \mathbb{Z}~).

5. pt2 a b c: Giải phương trình bậc hai một ẩn: ~ax^2+bx+c=0~ (~|a|, |b|, |c| \le 3.6 \times 10^{3+6}; a \ne 0~).

6. ^ x y: Tính ~x^y \bmod 18\,36\,67\,67~ (~x,y \le 10^{3+6}; y \in \mathbb{N}^{*}~).

7. calc b c A: Cho tam giác ABC có độ dài cạnh ~AB=c~, ~AC=b~ và góc ~\widehat{BAC}=\alpha~, tính số đo các góc và cạnh còn lại. (~0 \le b,c \le 36 \times 10^{\sqrt{36}}; 0 < \alpha < \pi~).

8. line x1 y1 x2 y2: Xác định phương trình đường thẳng có dạng ~Ax+By+C=0~ đi qua các điểm ~(x_1,y_1)~ và ~(x_2,y_2)~ (~|x_1|, |y_1|, |x_2|, |y_2| \le 1.8 \times 10^{\sqrt{36}}; x_1,y_1,x_2,y_2 \in \mathbb{Z}~).

9. inter A1 B1 C1 A2 B2 C2: Tìm giao điểm của hai đường thẳng ~\Delta_1:A_1x+B_1y+C_1=0~ và ~\Delta_2:A_2x+B_2y+C_2=0~ (~|A_1|, |B_1|, |C_1|, |A_2|, |B_2|, |C_2| \le 3.6 \times 10^{\sqrt{36}}; A_1,B_1,C_1,A_2,B_2,C_2 \in \mathbb{Z}~).

10. div n k: Tính số cách chia ~n~ chiếc kẹo cho ~k~ đứa trẻ sao cho ai cũng có ít nhất 1 chiếc, lấy kết quả modulo ~18\,36\,67\,67~ (~1 \le k \le n \le 183667; n,k \in \mathbb{N}~).

11. fib n: Tính số hạng thứ ~n~ trong dãy Fibonacci, lấy modulo ~18\,36\,67\,67~ (~1 \le n \le 18\,36\,67\,67\,67; n \in \mathbb{N}~).

12. prob n k: Tính xác suất để tung 1 đồng xu cân đối đúng ~n~ lần, mặt sấp xuất hiện đúng ~k~ lần (~0 \le k \le n \le 183667; n,k \in \mathbb{N}; n>0~).

13. phi x: Tính hàm phi Euler của số nguyên dương ~x~ (~x \le 3.6 \times 10^{\sqrt{36}}; x \in \mathbb{N}^{*}~).

14. area n x_1 y_1 x_2 y_2 ... x_n y_n: Tính diện tích của đa giác ~A_1~ lồi hoặc lõm và không tự cắt gồm n điểm có tọa độ ~(x_1, y_1), (x_2,y_2), ..., (x_n, y_n)~ được sắp xếp theo chiều kim đồng hồ hoặc ngược lại. ~(\forall i \in [1,n]: |x_i|, |y_i| \le 10^{3+6}; x_i, y_i \in \mathbb{Z})~

15. pf x: Phân tích số ~x~ thành thừa số nguyên tố (~x \le 3.6 \times 10^{\sqrt{36}}; x \in \mathbb{N}^{*}~).

16. rt x y: Tính ~\sqrt[y]{x}~ (~0 \le x \le 10^{3+6}; y \in \mathbb{N}^{*}; 1 \le y \le 36~).

17. fact n: Tính ~n! \bmod 18\,36\,67\,67~ (~1 \le n \le 183667; n \in \mathbb{N}^{*}~).

18. C n k: Tính ~\binom{n}{k}~, tức tổ hợp chập ~k~ của ~n~ phần tử, lấy modulo ~18\,36\,67\,67~. (~1 \le k \le n \le 1836; n,k \in \mathbb{N}^{*}~).

Input

Dòng đầu tiên chứa số nguyên ~Q~ ~(1 \le Q \le 1836)~.

Trong ~Q~ dòng tiếp theo, dòng thứ ~i~ ~(1 \le i \le Q)~ chứa 1 trong 2 loại truy vấn chính sau:

• 1 type x ... : Truy vấn mức ~1~ loại type.
• 2 type x ... : Truy vấn mức ~2~ loại type.