Under construction

Still being built. Things may change

Russian Dolls

Time limit1sMemory limit128 MB

Summary
Given 2n dolls with height, diameter, and wall thickness, decide whether they can be split into two chains of n that each nest perfectly.
Level

Medium6 of 10

Topics
Sorting, Greedy
Solved
No attempts yet

Problem

Russian nesting dolls are hollow wooden figures. Within a set the dolls have the same shape but different sizes: the largest doll holds the second largest, which holds the third largest, and so on.

Model each doll as a cylinder of height hh, diameter dd, and wall thickness ww. Its hollow interior then has height h−2wh - 2w and diameter d−2wd - 2w. Doll BB fits inside doll AA, standing straight up, exactly when BB's outer height and outer diameter both fit within AA's hollow: that is, when BB's height is at most A.h−2 A.wA.h - 2\,A.w and BB's diameter is at most A.d−2 A.wA.d - 2\,A.w.

Boris and Natasha each own a set of nn dolls. Their two sets were mixed together into a single pile of 2n2n dolls. Decide whether the pile can be sorted back into two proper nesting sets of exactly nn dolls each — that is, whether the 2n2n dolls can be partitioned into two groups of nn so that, within each group, every doll nests inside the next-larger one.

Input

The input contains several test cases. Each test case begins with a line containing nn, the number of dolls in one set (1<n≤1001 < n \le 100). The next 2n2n lines each contain three integers hh, dd, ww — the height, diameter, and wall thickness of one doll (h,d≥2w>0h, d \ge 2w > 0). A line containing a single 00 follows the last test case.

Output

For each test case, print a single line: YES if the 2n2n dolls can be separated into two nesting sets of exactly nn dolls each, or NO otherwise.

Examples5

  1. Example 1

    Input
    3
100 100 3
97 97 3
94 94 3
91 91 3
88 88 3
85 85 3
5
100 100 1
97 97 3
98 98 1
96 96 1
94 94 1
92 92 1
90 90 1
88 88 1
86 86 1
84 84 1
0
    Expected output
    YES
YES

  2. Example 2

    Input
    2
100 100 1
98 98 1
97 97 1
95 95 1
0
    Expected output
    YES

  3. Example 3

    Input
    2
10 10 1
10 10 1
10 10 1
10 10 1
0
    Expected output
    NO

  4. Example 4

    Input
    2
20 30 2
16 26 1
18 18 1
16 16 1
0
    Expected output
    YES

  5. Example 5

    Input
    2
100 100 1
98 98 1
97 97 1
95 95 1
2
10 10 1
10 10 1
10 10 1
10 10 1
2
20 30 2
16 26 1
18 18 1
16 16 1
0
    Expected output
    YES
NO
YES