Để chuẩn bị cho đêm hội ánh sáng bên bờ sông Hàn, Ban Tổ chức huy động một đoàn gồm ~n~ du khách quốc tế tham gia diễu hành trên các xe điện du lịch. Ban Tổ chức cần phân chia ~n~ du khách này vào các xe điện khác nhau. Để đảm bảo an toàn và quy định tổ chức, mỗi xe điện phải chở ít nhất một hành khách.

Mỗi xe điện sau khi nhận đủ hành khách sẽ được kích hoạt một hệ thống đèn LED nghệ thuật tự động. Để tạo sự độc đáo và ấn tượng, chu kì tự động đổi màu đèn (tính bằng giây) của mỗi xe được cài đặt bằng đúng số lượng hành khách ngồi trên xe đó. Ví dụ xe chở ~3~ khách thì cứ đúng ~3~ giây hệ thống đèn của xe đó lại tự động đổi màu một lần.

Đêm hội diễu hành sẽ đạt đến khoảnh khắc bùng nổ, mãn nhãn nhất khi tất cả các xe điện đồng loạt đổi màu đèn cùng lúc, tạo nên hiệu ứng ánh sáng khổng lồ lan tỏa dọc khắp tuyến phố đi bộ Bạch Đằng. Ban Tổ chức muốn khoảng thời gian từ lúc đoàn xe xuất phát cho đến lần đầu tiên tất cả các xe cùng kích hoạt đổi màu đèn đồng bộ phải là lâu nhất có thể, nhằm kéo dài sự tò mò và tạo sự phấn khích cho khán giả.

Yêu cầu: Hãy giúp Ban Tổ chức tìm phương án phân chia ~n~ du khách vào các xe điện sao cho khoảng thời gian chờ đến lúc tất cả các xe cùng đổi màu đèn đồng loạt lần đầu tiên là lớn nhất.

Input

Số nguyên dương ~n~ là tổng số lượng du khách quốc tế tham gia diễu hành.

Output

• Dòng thứ nhất ghi một số nguyên duy nhất là khoảng thời gian lớn nhất (tính bằng giây) mà khán giả phải chờ để chứng kiến tất cả các xe đổi màu đồng loạt lần đầu tiên.

• Dòng thứ hai ghi số lượng hành khách trên mỗi xe điện được phân chia, các số cách nhau bởi một khoảng trắng và được in theo thứ tự tăng dần.

Nếu có nhiều phương án cho cùng một kết quả tối ưu, hãy in ra phương án sử dụng ít xe điện nhất.

Scoring

Sample Input 1

14

Sample Output 1

84
3 4 7

Sample Input 2

45

Sample Output 2

60060
2 3 4 5 7 11 13

Notes

Với ví dụ 1: Với ~14~ vị khách, Ban Tổ chức có thể phân thành các phương án (PA):

• PA1: ~2, 5, 7 \Rightarrow~ thời gian là: ~70~

• PA2: ~3, 4, 7 \Rightarrow~ thời gian là: ~84~

• PA3: ~1, 2, 4, 7 \Rightarrow~ thời gian là: ~28~

• PA4: ~1, 1, 5, 7 \Rightarrow~ thời gian là: ~35~

~\Rightarrow~ Phương án 2 là tối ưu. Cần ~3~ xe điện chở lần lượt ~3, 4, 7~ khách. Thời gian đồng bộ đổi màu lần đầu tiên là ~84~ giây.

Với ví dụ 2: Với ~45~ vị khách, phương án tối ưu Ban Tổ chức phân ~7~ xe điện chở lần lượt ~2, 3, 4, 5, 7, 11, 13~ khách. Thời gian đồng bộ đổi màu lần đầu tiên là ~60060~ giây.