arrays-force-easy-contest

Let's consider some array A. The following algorithm calculates it's force:
Find all the continuous blocks where all the elemens of A are equal.
Calculate sum of squared lengths of these blocks.

For example if array A = {2, 3, 3, 1, 1, 1, 4, 2, 2} its force will be 1^2 + 2^2 + 3^2 + 1^2 + 2^2 = 19

We can reorder some elements and get array with greater force. In the example above we can move the first element of A to the end and get array A = {3, 3, 1, 1, 1, 4, 2, 2, 2}  with force  2^2 + 3^2 + 1^2 + 3^2 = 23.

You are given an array. What is the maximum force you can get by reordering some of its elements?

Input
The first line contains integer T denoting the number of test cases.
The following T lines contain 4 integers each: A[0], A[1], N, MOD.

Array A of N elements is generated by the following way:
A[0], A[1] are given
A[i] = (A[i - 1] + A[i - 2]) modulo MOD for 1 < i < N.

Output
For each test case output one integer on the separate line  - answer for the question.

Constraints
 1 ≤ T ≤100  
0 ≤ A[0], A[1] ≤ 10^6
 2 ≤ N ≤ 10^6  
 max(A[0] , A[1]) < MOD < 10^6  

SAMPLE INPUT
2
0 1 6 4
1 1 4 2

SAMPLE OUTPUT
12
10

Explanation

Test case 1: array A = {0, 1, 1, 2, 3, 1}. The greatest possible force will be with the reordering {2, 0, 1, 1, 1, 3}

Test case 2: array A = {1, 1, 0, 1}.  The greatest possible force will be with the reordering {1, 1, 1, 0}

Source: hackerearth | Difficulty: EASY
Tags: Mathematics

Greedy algorithms


Solutions: