This page is still under construction.

Parts of this page are still being built. What you see may change.

JaWs

Time limit1sMemory limit128 MB

Summary
Given two rows of equilateral triangles, drop the upper row onto the lower one and report where it settles or which side it slides off.
Level

Hard8 of 10

Topics
Geometry, Simulation, Implementation
Solved
No attempts yet

Problem

"Sigh! Where are those good old bloody days?" pondered Bob, the old shark — once the fearsome slayer of the deep blue waters — as his tears joined the endless water of the ocean. After years of butchering, Bob's teeth have lost their regular shape, and the poor old shark now has trouble closing his jaws. He wants to program his PDA to help him find the shape his teeth take when his jaws are closed, and we want to help him write that program!

Call the sequence of Bob's lower teeth LT and the sequence of his upper teeth UT. For simplicity, treat LT as a row of adjacent equilateral triangles (all sides equal), with the bases of every triangle lying on one horizontal line. UT has the same structure, except that its triangles are upside down (see Figure 1).

Bob's teeth

Figure 1. A snapshot of Bob's teeth.

Assume the left endpoint of the base of the leftmost tooth in LT is at (0,0)(0, 0), so the bases of all LT triangles lie on the x-axis. Call the left endpoint of the base of the leftmost tooth in UT the reference point. Initially the reference point is placed so that:

  • no tooth tip in LT and no tooth tip in UT share the same x-coordinate,
  • UT lies above LT (the y-coordinate of the reference point is greater than zero),
  • LT and UT do not overlap anywhere.

Starting from such a placement, UT falls straight down; its bases stay horizontal during the fall (UT never rotates). UT keeps falling until it touches some point of LT. From that moment UT slides downward along LT (to the left or to the right) until it can slide no further. Throughout the motion LT stays fixed and UT never rotates. Depending on its starting position, UT may slide off to the left or to the right and drop below LT (imagine the old shark in that state!); it is also possible for the tips of some upper teeth to end up below the line y=0y = 0 (the Dracula style!). Your program must decide whether UT falls off to the left or to the right; otherwise it must report the final position of the reference point after UT stops moving.

Input

The first line contains a single integer tt (1≤t≤101 \le t \le 10), the number of test cases. The data for each test case follows.

The first line of a test case contains an integer LL (1≤L≤101 \le L \le 10), the number of triangles in LT. Each of the next LL lines contains one integer bb (1≤b≤1001 \le b \le 100), the side length of an LT triangle, listed from left to right.

The next line contains three numbers xx, yy, and UU. The first two are the initial coordinates (x,y)(x, y) of the reference point and may be arbitrary real numbers; UU is the number of triangles in UT (1≤U≤101 \le U \le 10). Each of the following UU lines contains one integer bb (1≤b≤1001 \le b \le 100), the side length of a UT triangle, listed from left to right.

To avoid floating-point trouble, you may assume that during the motion of UT the distance between the tips of any two triangles (one from LT and one from UT) is never less than 0.10.1.

Output

Print one line per test case. If UT comes to rest on LT, print two real numbers — the xx and yy coordinates of the reference point after UT stops — each rounded to exactly three digits after the decimal point. If instead UT slides off to the left of LT, print WM; if it slides off to the right of LT, print MW. The output is case-sensitive.

Examples5

  1. Example 1

    Input
    2
    2
    10
    10
    2 20 2
    10
    10
    1
    10
    50 50 1
    10
    
    Expected output
    5.000 8.660
    MW
    
  2. Example 2

    Input
    1
    2
    10
    10
    7 20 2
    10
    10
    
    Expected output
    5.000 8.660
    
  3. Example 3

    Input
    1
    1
    10
    -2 20 1
    10
    
    Expected output
    WM
    
  4. Example 4

    Input
    1
    1
    10
    2 20 1
    10
    
    Expected output
    MW
    
  5. Example 5

    Input
    1
    1
    10
    50 50 1
    10
    
    Expected output
    MW