VO 19 Bài 3 - Bánh phu thê


Submit solution

Points: 1.50 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

Cuối cùng thì ngày đó cũng tới, ngày đôi bạn trẻ chính thức nên duyên vợ chồng. Đám cưới linh đình tại cái nôi của làn điệu Quan Họ là thành quả ngọt ngào của cuộc tình dài bắt đầu từ những ngày học đội tuyển tin, cộng thêm một chút lỡ tay của tạo hoá.

Cùng với việc mở tiệc linh đình, đôi vợ chồng trẻ chuẩn bị những món quà đặc biệt cho quan khách tới dự đám cưới. Họ đặt ~m~ hộp bánh phu thê để tặng khách nhà trai, các hộp lần lượt có ~S_0~, ~S_1~, ~\dots~, ~S_{m−1}~ bánh bên trong. Họ cũng chuẩn bị ~n~ hộp bánh với số bánh lần lượt là ~T_0, T_1, \dots, T_{n−1}~ tặng khách nhà gái.

Không may cho họ, Liinhh và Trà, hai đứa sửu nhi tham ăn trong làng lén lút lấy đi vài hộp bánh, và ăn bớt vài chiếc bánh trong những hộp khác. Khi sự việc bị phát giác thì mọi thứ đã muộn - đôi trẻ đã cao chạy xa bay với những chiếc bánh nằm yên trong bụng.

Đen đủi hơn, đôi tân lang & tân nương còn không nhớ được đơn đặt hàng (hay dãy số ~S_0, S_1, \dots, S_{m−1}~ và ~T_0, T_1, \dots, T_{n−1}~) ban đầu. Giờ chỉ còn một manh mối nhỏ: Con trai chủ cửa hàng bán bánh đã ghi lại một mẩu giấy, ở đó có số nguyên tố ~MOD~ và một dãy ~k~ số ~P_0~, ~P_1, \dots, P_{k−1}~, cùng một số thông tin sau:

  • ~2 \leq m~, ~n \leq k~
  • ~m \times n = k~
  • ~0 \leq S_0, S_1, \dots, S_{m−1} < MOD~
  • ~0 \leq T_0, T_1, \dots, T_{n−1} < MOD~
  • Với mọi ~0 \leq i~ < ~m~ và ~0 \leq j~ < ~n~, ~(S_i \times T_j - P_{in + j})~ chia hết cho ~MOD~.

Các bạn hãy giúp đôi vợ chồng kia tìm lại đơn đặt hàng ban đầu nhé. Cũng có thể mẩu giấy chứa thông tin không chính xác, bạn phải phát hiện được trường hợp này

Input

  • Dòng đầu tiên chứa số nguyên ~k~ ~(4 \leq k \leq 15 \times 10^{5})~ và số nguyên tố ~MOD~ ~(2 \leq MOD \leq 10^{6})~.
  • Dòng thứ hai chứa ~k~ số nguyên ~P_0~ ~P_1~ ~\dots~ ~P_{k−1}~ ~(0 \leq P_0, P_1, \dots, P_{k−1} < MOD)~.

Output

  • Dòng đầu tiên gồm từ "YES" nếu tồn tại lời giải, "NO" nếu không tồn tại hai dãy ~S~ và ~T~ thoả mãn các điều kiện của đề bài. Nếu tồn tại lời giải,
  • Dòng thứ hai chứa ~m + 1~ số nguyên ~m~ ~S_0~ ~S_1~ ~\dots~ ~S_{m−1}~.
  • Dòng thứ ba chứa ~n + 1~ số nguyên ~n~ ~T_0~ ~T_1~ ~\dots~ ~T_{n−1}~.

Các số cần thoả mãn mọi điều kiện ở trên. Nếu tồn tại nhiều đáp án, bạn có thể in ra đáp án bất kì.

Giới hạn

  • Subtask ~1~ ~(12/60~ điểm): ~k \leq 12~, ~MOD \leq 7~
  • Subtask ~2~ ~(14/60~ điểm): ~k \leq 10^5~, ~MOD = 2~
  • Subtask ~3~ ~(16/60~ điểm): ~k \leq 10^5~
  • Subtask ~4~ ~(18/60~ điểm): Không có ràng buộc gì thêm.

Sample Input 1

4 7
1 2 4 1

Sample Output 1

YES
2 1 4
2 1 2

Sample Input 2

6 2
0 0 0 1 1 1

Sample Output 2

YES
2 0 1
3 1 1 1

Comments

There are no comments at the moment.