Team Split

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef wants to split a team of new chef into two teams to play a game. In order to make the split, he first designates two team captains who take alternate turns selecting players for their teams. During each turn, the captain selects a single player for his team. Since each captain wants to make the strongest possible team, he will always select the best available player. The players have strengths as integer number, where higher strength indicate better players. After all the players have been selected, the team strength is computed as the sum of the strengths of the players on that team.
For example, if strengths of 5 players are 5,7,8,4 and 2, then the first captain selects the player with strength 8 for his team, the second captain gets the player with strength 7, the first gets the one with strength 5, the second the one with strength 4, and the last one (strength 2) goes to the first team. The first team now has a total strength 8+5+2=15, and the second team has strength 7+4=11.
Now Chef wants to find the absolute strength difference between the two teams. For the example above the answer is 4(=1511).
But Chef does not know exact strengths of each player. He knows some parameter a, b, c and d and a formula to find the strength of each player. The formula is
S_{0} = d,
S_{i} = (a * S_{i1}^{2} + b * S_{i1} + c) mod 1000000, for i = 1 to N  1
There are N players numbering 0 to N1 and S_{i} is the strength of player i.
Input
First line of the input contains an integer T, number of test cases to follow. Each test consist of single line containing five integers N, a, b, c and d.
Output
For each test case, you have to print a single line containing the absolute strength difference between the two teams.
Constraints
 1 ≤ T ≤ 50
 1 ≤ N ≤ 3000000
 0 ≤ a, b, c, d ≤ 100
Example
Input: 4 1 1 1 1 1 2 1 1 1 1 3 1 2 3 4 4 2 3 4 1 Output: 1 2 763 74896
Author:  shiplu 
Editorial  http://discuss.codechef.com/problems/TMSLT 
Tags  march14, shiplu, simple, sorting 
Date Added:  18122013 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 