Dãy số mạnh nhất Sức mạnh của một dãy số là tổng bình phương độ dài của những đoạn gồm các phần tử đứng liên tiếp nhau và có giá trị bằng nhau. Ví dụ dãy số: 2, 3, 3, 4, 2, 2, 2 có sức mạnh là 1^2+2^2+1^2+3^2 = 15. Ta có thể đổi chỗ các phần tử của dãy số đã cho để thu được dãy mới có sức mạnh lớn hơn. Trong ví dụ trên, ta có thể đổi chỗ phần tử đầu tiên với phần tử thứ tư để thu được dãy mới là: 4, 3, 3, 2, 2, 2, 2 có sức mạnh là 1^2+2^2+4^2 = 21. Đây cũng là dãy số mạnh nhất có thể tạo ra từ dãy đã cho. Yêu cầu: Cho một dãy số gồm n phần tử. Tìm sức mạnh lớn nhất có được bằng cách đổi chỗ các phần tử của dãy, số lần đổi chỗ trong dãy là không giới hạn. Dữ liệu vào: từ tệp văn bản DSMN.INP có cấu trúc như sau: • Dòng đầu ghi số nguyên dương T (1 ≤ T ≤ 100) là số lượng dãy số; • Trong T dòng tiếp theo, mỗi dòng ghi 4 số nguyên lần lượt A[1], A[2], n, M đại diện cho một dãy số. Mỗi dãy số gồm n phần tử được tạo ra như sau: o A[1] và A[2] đã được cho trước (max(A[1], A[2])<M); o A[i] = (A[i-1] + A[i-2]) Mod M với mọi i tính từ 3 đến n; (Mod: là phép chia lấy phần dư). • Các số trong tệp đều là số nguyên không âm và có giá trị không vượt quá 106 . Kết quả: ghi ra tệp văn bản DSMN.OUT gồm T dòng là sức mạnh tương ứng của từng dãy số. Ví dụ: DSMN.INP DSMN.OUT 2 12 0 1 6 4 10 1 1 4 2 Ràng buộc: • Có 40 % test có n ≤ 100 tương ứng 40 % số điểm; • Có 40 % test có 100 ≤ n ≤ 50.000 và T = 1 tương ứng 40 % số điểm; • Có 20 % test có 50.000 ≤ n ≤ 1.000.000 tương ứng 20 % số điểm.