Alice: Hi Bob! Let's play a game.

Bob: Oh no! It's boring because both of us always choose the optimal strategy.

Alice: Well, then let's solve some Diophantine equations. What's the integer solutions of `x`^{2} + `y`^{2} = `n` if `n` is a fixed positive integer?

Bob: Er.. It's easy to get the solutions when `n` is a prime or 1. But it's a bit hard to solve this equation when `n` is a composite number.

Alice: Do you know Brahmagupta-Fibonacci identity? It says that the product of two sums each of two squares is itself a sum of two squares. Specifically: (`a`^{2} + `b`^{2})(`c`^{2} + `d`^{2}) = (`ac` + `bd`)^{2} + (`ad` - `bc`)^{2} = (`ac` - `bd`)^{2} + (`ad` + `bc`)^{2}. When `n` is a composite number, perhaps the solutions when `n` is a prime can be combined via this indentity.

Bob: Yes, the Brahmagupta-Fibonacci identity helps a lot. Now we can solve the equation easily. Let's solve some other equations. What about the integer solutions of `x`^{2} + `y`^{2} + `z`^{2} = `A` and `x` + `y` + `z` = `B`?

Alice: It's similar to the former equation but more complicated. Let's write a program to solve it.

Bob: Ok! It seems that we should get the decomposition of 3`A` - `B`^{2} first. And when 3`A` - `B`^{2} is less than zero, there cannot be any integer solutions.

Alice: I can write the prime factorization part. Can you complete the remaining part?

Bob doesn't know how to write a program. He turned to you for help. You are given two integers `A` and `B`. The prime factors of 3`A` - `B`^{2} will also be given. You should output all the integer solutions of `x`^{2} + `y`^{2} + `z`^{2} = `A` and `x` + `y` + `z` = `B`. Because of the symmetry, only the integer solutions (`x`, `y`, `z`) that `x` <= `y` <= `z` are required.

There are multiple test cases. The first line of input contains an integer `T` (about 2000) indicating the number of test cases. For each test case:

There are two or more integers in one line. The first two integers are `A` (0 <= `A` <= 10^{18}) and `B` (-10^{9} <= `B` <= 10^{9}) respectively. The following integers in the same line are the prime factors of 3`A` - `B`^{2}. If 3`A` - `B`^{2} is less than 2, no prime factors will be given.

For each test case, output a label "Case #`id`:" first where `id` (starting from 1) is the case number. The following lines should be all the integer solutions (listed in `x` increasing order). For each integer solution, there should be three integer numbers `x`, `y` and `z` separated by a space.

You can assume that the total output will be no more than 20000 lines.

7 10 2 2 13 3 -3 1 1 2 15 -7 467716406 4 2 7 13 19 999278059394184698 1000000000 2 999007 999907 1000003 666666666666666645 -1 2 999999999999999967

Case #1: -1 0 3 Case #2: -1 -1 -1 Case #3: 0 0 1 Case #4: Case #5: -17655 8609 9050 -17641 8175 9470 -17554 7131 10427 -17494 6677 10821 -17410 6159 11255 -17215 5210 12009 -17059 4586 12477 -16773 3611 13166 -16591 3065 13530 -15954 1427 14531 -15499 426 15077 -15225 -130 15359 -14641 -1225 15870 -14323 -1779 16106 -14029 -2269 16302 -13714 -2773 16491 -13398 -3259 16661 -12966 -3895 16865 -12615 -4390 17009 -12265 -4866 17135 -11859 -5398 17261 -10585 -6945 17534 -9766 -7855 17625 -9298 -8349 17651 Case #6: -325445947 576237380 749208567 -325096053 574086620 751009433 -324917875 573008543 751909332 -324556125 570853457 753702668 Case #7: -641498974 163610588 477888385

提交代码