Từ thời cổ đại, mỗi chiến binh có một bộ ba loại vũ khí: một thanh kiếm laser, một lưỡi dao laser và một dao găm laser để trát bơ trên bánh mì (khi đói).

Những vũ khí này có ràng buộc về độ dài như sau:

• Chiều dài dao găm - ~d_1~, chiều dài của lưỡi dao - ~d_2~, chiều dài của thanh kiếm - ~d_3~ đều là các số nguyên tố;
• ~d_1 \leq d_2 \leq d_3~;
• ~(d_1 + d_2)^2 - 1~ chia hết cho ~d_3~;
• ~(d_2 + d_3)^2 - 1~ chia hết cho ~d_1~;
• ~(d_3 + d_1)^2 - 1~ chia hết cho ~d_2~.

Công ty bán bất kỳ bộ vũ khí theo số thứ tự từ điển. Cụ thể, sắp xếp tất cả các bộ theo ~d_1~ không giảm, nếu ~d_1~ như nhau thì xét ~d_2~ không giảm, và nếu ~d_1~ và ~d_2~ bằng nhau thì xét ~d_3~ tăng và đánh số chúng theo thứ tự từ ~1~ đến vô cùng.

Cho ~k~, hãy mua tập vũ khí thứ ~k~ theo thứ tự này.

Input

Dòng đầu tiên ghi số nguyên ~k~ ~(1 \leq k \leq 60000)~.

Output

In ra độ dài ~3~ loại vũ khí trong tập thứ ~k~.

Sample Input

1

Sample Output

2 2 3

Note

Đề gốc thi thử duyên hải 2021 lần 1