Trường THPT Chuyên Hoàng Văn Thụ - Hòa Bình

Steve đang nghiên cứu một chủng loại vi khuẩn mới. Số vi khuẩn trên đĩa Petry (đĩa nuôi cấy vi khuẩn) hiện đang có n cá thể (1 ≤ n ≤ 1000). Với mỗi số nguyên tố p, Steve có thể điều chế chất C_pH_2p+1OH. Khi cho chất này vào đĩa Petry, nếu n chia hết cho p thì số vi khuẩn sẽ giảm đi đúng p lần. Nếu n không chia hết cho p – kết quả sẽ là bất định và điều này sẽ cản trở các nghiên cứu tiếp theo. Trong phòng thí nghiệm, Steve có một số lượng không hạn chế Acid điatilamid lizergin (C₂₀H₂₅N₃O). Nếu cho acid này vào đĩa cấy vi khuẩn, sau một thời gian ngắn số vi khuẩn sẽ tăng thành bình phương của số lượng trước khi cho. Tuy nhiên do diện tích đĩa Petry có giới hạn nên không thể chứa được số lượng vi khuẩn quá C cá thể (1 <= C <= 10000).

Ví dụ, ban đầu, trong đĩa Petry có 12 cá thể vi khuẩn. Nếu cho C₂H₅OH vào, số vi khuẩn rút xuống còn 6, cho tiếp C₂0H₂₅N_3O, số vi khuẩn trở thành 36, bây giờ nếu cho vào C₂H₅OH số vi khuẩn trong đĩa sẽ là 18.

Yêu cầu: Cho các số nguyên n, m (1 ≤ m ≤ 10000). Hãy xác định quy trình cho hóa chất với ít bước nhất để có được đúng m vi khuẩn hoặc đưa ra thông báo Impossible nếu không thể nhận được số vi khuẩn cần thiết.

Dữ liệu: Vào từ file văn bản BACTERIA.INP gồm một dòng chứa 3 số nguyên n và m và C.

Kết quả: Đưa ra file văn bản BACTERIA.OUT thông báo Impossible nếu không thể nhận được số vi khuẩn cần thiết, nếu có cách làm:

-          Dòng 1 đưa ra số k là số bước ít nhất.

-          Dòng 2 đưa ra dãy k số nguyên, mỗi số tương ứng với một lần cho hóa chất vào đĩa cấy, số nguyên thứ i là 0 nếu cho C₂₀H₂₅N₃O và là p nếu cho C_pH_2p+1OH. Các số cách nhau ít nhất một dấu cách.

Ví dụ: