Hôm nay, Dung muốn cho Huy một thử thách nho nhỏ về Toán học.

Dung có một dải băng dài được chia thành ~n~ ô vuông được đánh số thứ tự từ ~1~ đến ~n~ từ trái sang phải. Ban đầu, mỗi ô vuông trên băng đều ghi số ~1~. Huy có thể yêu cầu Dung thực hiện các thao tác sau:

• ~+\ i\ j\ k~: Cộng hai số ở vị trí ~i~ và ~j~, sau đó ghi kết quả vào ô ở vị trí ~k~.
• ~*\ i\ j\ k~: Nhân hai số ở vị trí ~i~ và ~j~, sau đó ghi kết quả vào ô ở vị trí ~k~.

Lưu ý, ~i, j, k~ có thể giống nhau.

Dung sẽ cho Huy một số nguyên dương ~n~. Gọi ~p_i~ là số nguyên tố thứ ~i~. Cô có 4 loại thử thách như sau:

• Loại 1: Với mọi ô từ ~1~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi giá trị ~i~.
• Loại 2: Với mọi ô từ ~1~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi giá trị ~p_i~.
• Loại 3: Với mọi ô từ ~1~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi tổng các giá trị ~j^3~ với ~j~ là ước của ~i~. Ví dụ, ô ~4~ sẽ ghi giá trị ~1^3 + 2^3 + 4^3 = 73~.
• Loại 4: Với mọi ô từ ~2~ đến ~n~, Huy cần biến đổi sao cho ô ~i~ ghi lập phương tổng các giá trị ~p_j~ với ~j~ là ước nguyên tố của ~i~. Ví dụ, ô ~6~ sẽ ghi giá trị ~(p_2 + p_3)^3 = (3 + 5)^3 = 512~. Ô ~1~ cần ghi giá trị ~1~.

Để hoàn thành thử thách, Huy được phép yêu cầu Dung thực hiện thao tác biến đổi không quá ~50000~ lần.

Các bạn hãy viết chương trình giúp Huy hoàn thành thử thách nhé.

Dữ liệu - Nhập từ tệp văn bản ARRAY.inp:

• Một dòng duy nhất gồm hai số nguyên dương ~n, \theta~, với ~\theta~ là loại thử thách của Dung. ~(1 \le n \le 20000, 1 \le \theta \le 4)~

Kết quả - Ghi ra tệp văn bản ARRAY.out:

• Dòng đầu tiên gồm một số nguyên dương ~k~ là số lần Dung cần thực hiện thao tác biến đổi. ~(0 \le k \le 50000)~
• ~k~ dòng tiếp theo, mỗi dòng thuộc một trong hai dạng sau:
  • ~+\ i\ j\ k~: mô tả thao tác cộng. ~(1 \le i, j, k \le n)~
  • ~*\ i\ j\ k~: mô tả thao tác nhân. ~(1 \le i, j, k \le n)~

Chấm điểm

Ví dụ

Dữ liệu (ARRAY.inp)

2 2

Kết quả (ARRAY.out)

2
+ 1 1 1
+ 1 2 2

Giải thích

• Đầu tiên, Huy lấy giá trị của ô đầu tiên cộng với chính nó và ghi vào ô đầu tiên. Kết quả là ~1 + 1 = 2~.
• Tiếp theo, Huy lấy giá trị của ô đầu tiên cộng với giá trị của ô thứ hai và ghi vào ô thứ hai. Kết quả là ~2 + 1 = 3~.