Johann is a Recording Engineer, tasked with recording a choir of singers.
Each singer has a specific vocal range R, with R=1 being the lowest-pitched voice and R=9 being the highest-pitched voice.
When it is time to perform, the singers stand in a single line in no particular order.
singers: 3 1 3 3 2 1 2 2 2 1
While unpacking his equipment, Johann makes a terrible discovery - he has only remembered to bring a single microphone along with him! In order to achieve the best recorded sound possible, Johann must be very careful where he places of the microphone, which he can set up between any two performers. Note that the microphone positions are 0-indexed.
singers: 3 1 3 3 2 1 2 2 2 1
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
positions: 0 1 2 3 4 5 6 7 8 9 10
He wants to achieve a balanced sound, and so he creates a simple formula to calculate a score to rank microphone placement.
To score a microphone position, he counts the quantity of singers with vocal range R_i standing to the left of the microphone, then the quantity with R_i standing to the right of the microphone, then squares the difference between these two quantities.
The score for that position is the total sum score for all vocal ranges, with lower scores being better than highers scores.
For example, in the example above at position 7, there are two 1s to the left, one 1 to the right, two 2s to the left, two 2s to the right, three 3s to the left, and no 3s to the right.
Therefore the score is (1 - 2)^2 + (2 - 2)^2 + (3 - 0)^2 = 10.
It can be shown that 10 is the lowest score possible in any position.
Note that depending on the configuration of singers, it can be possible for multiple positions to be tied for the lowest score. If that is the case, then Johann will choose the position closest to the center of the line. If two spots are tied for lowest score and also equidistant from the center, he will choose the left position of the two.
The actual choir that Johann will record will be very large.
So large, in fact, that it makes more sense to provide a choir size n and a seed value x0 for a Linear Congruential Generator
(use a = 445, c = 700001 and m = 2097151) to pseudo-randomly generate the vocal ranges of the singers. Use the LCG to generate n values, then for each value v_i calculate the range of that singer as R_i = (v_i mod 8) + 1.
Input Data
First line is Q, the quantity of testcases.
Q lines then follow, each in the format x0 n.
Answer
Should consist of Q pairs of space-separated integers, with each pair corresponding to the position and score of the microphone in each testcase.
Example
input data:
1232444 10
1853967 12
1234567 7654
answer:
8 3 4 4 8814 3856