Suiting Weavers

Time limit1sMemory limit128 MB

Summary
Given each weaver's circular territory and each fiber pile, decide whether Willy can end up with at least as many fibers as every rival under any assignment of piles to reachable weavers.
Level

Medium6 of 10

Topics
Greedy, Sorting, Geometry, Brute force
Solved
No attempts yet

Problem

Willy the Weaver desperately hopes to marry Wilmar, the most beautiful and delightful female weaver. Of course, Willy is not the only weaver interested in Wilmar.

To impress the females, weavers build elaborately woven nests from leaf fibers. Tomorrow is the big day, when Wilmar will inspect the nests in the hours before sunrise. A storm will produce many piles of leaf fibers, so every weaver will have a chance to improve its nest. Willy therefore wonders whether he can weave the most impressive nest, so that Wilmar finally decides to marry him. Since size matters, Willy tries to figure out how large his nest and those of his rivals may become.

For this, Willy considers all known places offering leaf fibers suitable for nest construction. Since weavers do not like to leave their known territory, many of these places can be accessed by only a subset of the weavers, and some might not be reachable by any weaver at all.

To keep things simple, Willy does not set up a flight plan. This means he does not consider any particular strategy of his rivals, nor does he make assumptions about how many fibers they can carry at a time or how fast and when they fly. It is therefore possible that a weaver picks up all the fibers in his territory. Finally, Willy assumes that all weavers are as honest as he is: they do not steal fibers from the nests of their rivals.

Is there any chance that, after all the leaf fibers have been picked up, no weaver will have a larger nest (in number of fibers) than Willy?

Input

The first line contains the number of test cases TT (1≤T≤1001 \le T \le 100).

Each test case starts with a line containing two integers. The first integer WW (1≤W≤1001 \le W \le 100) is the number of weavers (including Willy); the second, PP (1≤P≤4001 \le P \le 400), is the number of places with leaf fibers.

Next come WW lines describing the nest of each weaver with four integers xx, yy, ff, and rr (0≤x,y,r≤10,0000 \le x, y, r \le 10{,}000, 1≤f≤10,0001 \le f \le 10{,}000): xx and yy give the position of the nest, ff is the size of the nest in number of fibers, and rr is the radius of the territory in which the owner of the nest searches for additional fibers. A weaver can pick up the fibers at any place whose distance from its nest is at most rr. The first of these WW lines describes Willy's nest.

Thereafter follow PP lines defining the places with available leaf fibers with three integers xx, yy, and ff (0≤x,y≤10,0000 \le x, y \le 10{,}000, 1≤f≤10,0001 \le f \le 10{,}000): xx and yy give the position of the place, and ff is the number of available leaf fibers there.

Output

For each test case, print a single line containing Suiting Success if Willy has a chance to marry Wilmar after all fibers have been picked up (a tie in nest size is sufficient); otherwise print Lonesome Willy.

Examples1

  1. Example 1

    Input
    2
    3 2
    0 0 1 10
    10 0 1 10
    20 0 1 10
    5 0 2
    15 0 4
    3 2
    0 0 1 10
    10 0 1 10
    20 0 1 10
    5 0 2
    15 0 5
    
    Expected output
    Suiting Success
    Lonesome Willy