Under construction

Still being built. Things may change

Robotopia

Time limit2sMemory limit512 MB

Summary
Given arms and legs per robot for two types and the group totals, find the unique positive counts of each type, or print ? if none or many.
Level

Medium4 of 10

Topics
Math, Brute force
Solved
No attempts yet

Problem

In Robotopia the robots work together and keep the town running. Each type of robot has a different number of arms and a different number of legs. By day the robots are gathered into groups so that work can be handed out, and by night your job is to count how many robots of each type sit in each group. The robots never hold still, so counting them one by one does not work. After many tries you managed to learn only the total number of legs and the total number of arms in the group.

Every group is made of exactly two different types of robots, and at least one robot of each type is present. You also know how many legs and arms a single robot of each type has. From the observed leg total and arm total, work out how many robots of each type the group holds.

Input

The first line contains the number of test cases nn (1≤n≤1001 \le n \le 100). Each of the next nn lines holds one test case as six integers l1l_1 a1a_1 l2l_2 a2a_2 ltl_t ata_t separated by spaces. Here l1l_1 and a1a_1 are the number of legs and arms of one robot of the first type, l2l_2 and a2a_2 are the same for the second type, and ltl_t and ata_t are the observed totals of legs and arms in the group. Every value is between 11 and 1000010000.

Output

For each test case print one line with the two robot counts separated by a space, the count for the first type first. Both counts must be positive integers, so an answer where either count is 00 is not accepted.

If no answer satisfies the conditions, or if two or more answers do, print a single question mark ? on that line instead.

Examples1

  1. Example 1

    Input
    3
    2 1 4 1 16 5
    3 2 5 1 9 4
    1 2 3 6 8 16
    
    Expected output
    2 3
    ?
    ?