Facebook Hacker Cup 2015 Round 2

Mr. Fox sure loves his socks! He stores his many indistinguishable socks in a set of ~N~ bins, which are arranged in a circle and numbered in clockwise order. For every ~1 \le i < N~, the next bin clockwise of bin ~i~ is bin ~i+1~, and the next bin clockwise of bin ~N~ is bin ~1~. Initially, the ~i^\text{th}~ bin contains ~S_i~ socks.

Never being quite satisfied with his sock collection, Mr. Fox would like to perform ~M~ operations on it, one after another. Each operation ~i~ may be of one of the following 4 types, determined by the value of ~O_i~:

1. Given integers ~A_i~, ~B_i~, ~C_i~, and ~D_i~, add ~C_i + 0 * D_i~ socks to bin ~A_i~, add ~C_i + 1 * D_i~ socks to the next bin clockwise of bin ~A_i~, add ~C_i + 2 * D_i~ to the next bin clockwise of that one, and so on until this has been done for ~B_i~ bins. Determine the total number of socks added in this process.
2. Given integers ~A_i~, ~B_i~, and ~C_i~, remove all of the socks from bin ~A_i~ and then add ~C_i~ socks to it. Do the same for the next bin clockwise of ~A_i~, and so on until this has been done for ~B_i~ bins. Determine the sum of two values: the total number of socks removed in this process, and the total number of socks added in this process.
3. Given integers ~A_i~ and ~B_i~, count the number of socks in bin ~A_i~ (without removing them), the number of socks in the next bin clockwise of ~A_i~, and so on until the socks in ~B_i~ bins have been counted. Determine the total number of socks counted in this process.
4. Given integers ~A_i~ and ~B_i~, check if bin ~A_i~ contains an odd number of socks. Do the same for the next bin clockwise of ~A_i~, and so on until this has been done for ~B_i~ bins. Determine the total number of these bins that contain an odd number of socks.

Can you help Mr. Fox keep track of his socks?
Note the value calculated during each of the ~M~ operations as they're performed, and then output the sum of all ~M~ of the values modulo ~10^9~.

Input

Input begins with an integer ~T~, the number of sock collections Mr. Fox has. For each sock collection, there are 7 lines containing the following space-separated integers:

1. ~N~ ~M~
2. ~S_1~ ~S_2~ ~X_S~ ~Y_S~ ~Z_S~
3. ~O_1~ ~O_2~ ~X_O~ ~Y_O~ ~Z_O~
4. ~A_1~ ~A_2~ ~X_A~ ~Y_A~ ~Z_A~
5. ~B_1~ ~B_2~ ~X_B~ ~Y_B~ ~Z_B~
6. ~C_1~ ~C_2~ ~X_C~ ~Y_C~ ~Z_C~
7. ~D_1~ ~D_2~ ~X_D~ ~Y_D~ ~Z_D~

The first two elements of each sequence of integers (~S~, ~O~, ~A~, ~B~, ~C~, and ~D~) are given, and the rest are computed with the following pseudorandom generators:

• ~S_i = (X_S * S_{i-2} + Y_S * S_{i-1} + Z_S) \bmod 10^9~, for ~3 \le i \le N~
• ~O_i = ((X_O * O_{i-2} + Y_O * O_{i-1} + Z_O) \bmod 4) + 1~, for ~3 \le i \le M~
• ~A_i = ((X_A * A_{i-2} + Y_A * A_{i-1} + Z_A) \bmod N) + 1~, for ~3 \le i \le M~
• ~B_i = ((X_B * B_{i-2} + Y_B * B_{i-1} + Z_B) \bmod N) + 1~, for ~3 \le i \le M~
• ~C_i = (X_C * C_{i-2} + Y_C * C_{i-1} + Z_C) \bmod 10^9~, for ~3 \le i \le M~
• ~D_i = (X_D * D_{i-2} + Y_D * D_{i-1} + Z_D) \bmod 10^9~, for ~3 \le i \le M~

Output

For the ~i^\text{th}~ sock collection, print a line containing Case #i: followed by the sum of all values calculated during each operation, modulo ~10^9~.

Constraints

~1 \le T \le 20~
~2 \le N \le 1\,000\,000~
~2 \le M \le 1\,000\,000~
~0 \le S_i < 10^9~
~1 \le O_i \le 4~
~1 \le A_i \le N~
~1 \le B_i \le N~
~0 \le C_i < 10^9~
~0 \le D_i < 10^9~

~0 \le X_S, X_O, X_A, X_B, X_C, X_D < 10^9~

~0 \le Y_S, Y_O, Y_A, Y_B, Y_C, Y_D < 10^9~

~0 \le Z_S, Z_O, Z_A, Z_B, Z_C, Z_D < 10^9~

Explanation of Sample

The first collection has 5 bins that all have 0 socks. None of the operations involve any socks at all, so the answer is 0.

The second collection has 5 bins with 1, 2, 3, 4, and 5 socks. Mr. Fox performs the operations 1, 2, 3, and 4 in order. For each operation, ~A = 1~, ~B = 5~, ~C = 0~, ~D = 0~. He first adds 0 socks to the bins, then removes all 15 socks, then counts the 0 remaining socks, and then counts 0 odd bins, for a total of 15.

The third collection also has 5 bins with 1, 2, 3, 4, and 5 socks. Mr. Fox performs the same operations, but this time ~C~ and ~D~ take on the values 1, 2, 3, and 4 in that order. He adds 15 socks to the bins, then removes all 30 socks and adds 2 socks to each bin, then counts those 10 socks, and then counts 0 odd bins. The total is then ~15+30+10+10 = 65~.

Sample Input

5
5 4
0 0 0 0 0
1 2 0 1 0
1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 0 0
5 4
1 2 0 1 1
1 2 0 1 0
1 1 0 0 0
5 5 0 1 4
0 0 0 0 0
0 0 0 0 0
5 4
1 2 0 1 1
1 2 0 1 0
1 1 0 0 0
5 5 0 1 4
1 2 0 1 1
1 2 0 1 1
5 2
1 2 0 1 1
4 4 0 0 0
1 1 0 0 0
5 5 0 0 0
0 0 0 0 0
0 0 0 0 0
100 100
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

Sample Output

Case #1: 0
Case #2: 15
Case #3: 65
Case #4: 6
Case #5: 505274484