Bạn được cho một số nguyên dương ~N~. Xét dãy số ~A~ gồm ~N~ phần tử thỏa mãn ~A_i=1~ với mọi ~i~ từ ~1~ đến ~N~. Nhiệm vụ của bạn là thực hiện một số thao tác sao cho sau khi thực hiện, với mọi ~i~ từ ~1~ đến ~N~ phải thỏa mãn ~A_i=i^i~. Bạn được phép thực hiện hai loại thao tác sau:

• + i j k (~1\le i,j,k\le N~): Cập nhật ~A_k=A_i+A_j~.
• * i j k (~1\le i,j,k\le N~): Cập nhật ~A_k=A_i\times A_j~.

Lưu ý: Trong một thao tác, các giá trị ~i,j,k~ không nhất thiết phải đôi một phân biệt mà có thể bằng nhau.

Dữ liệu vào

Gồm duy nhất một số nguyên dương ~N\ (1\le N\le 2\times 10^4)~.

Dữ liệu ra

Dòng đầu tiên gồm một số nguyên không âm ~M~ là số thao tác cần thực hiện ~(0\le M\le 4\times 10^5)~.

Sau đó là ~M~ dòng, mỗi dòng mô tả một trong hai thao tác ở trên.

Subtask

Cách tính điểm

Giả sử test có tối đa ~1~ điểm. Gọi ~Q=\frac{M}N~. Khi đó:

• Nếu ~Q>20~ thì bạn được ~0~ điểm.
• Nếu ~5 < Q \le 20~ thì bạn được ~{0.9}^{Q-5}~ điểm.
• Nếu ~Q\le 5~ thì bạn được ~1~ điểm.

Ví dụ

Dữ liệu vào

2

Dữ liệu ra

2
+ 1 1 2
* 2 2 2