Hand Detection

Time limit1sMemory limit128 MB

Summary

For each five-card hand, check whether all ten pairwise value differences are distinct and whether the five suits are all different.

Level: Easy3 of 10
Topics: Implementation, Hash map
Solved: No attempts yet

Problem

Hobbits enjoy games of chance and skill. One of them is much like our poker, though their decks and rules differ a little.

Each card has one of 21 values (1 to 21, inclusive).
Each card has one of 5 suits (Elf, Man, Hobbit, Ent, Orc).

A full deck therefore has $21 \times 5 = 105$ cards, and — just like poker — every "hand" consists of 5 cards.

Your task is to detect two properties of a hand: whether it is a spread and whether it is a rainbow.

Spread. The suits are ignored; only the values matter. A hand is a spread when the difference between any two of its cards is never equal to the difference between any other two cards — that is, when all of its pairwise value differences are distinct.

For example, a hand with values 1, 2, 4, 8, 16 is a spread, because every pair of values has a unique absolute difference:

First card	Second card	Difference
1	2	1
1	4	3
1	8	7
1	16	15
2	4	2
2	8	6
2	16	14
4	8	4
4	16	12
8	16	8

Rainbow. A hand is a rainbow when it contains exactly one card of each of the 5 suits.

Input

The first line contains the number of test cases $T$ ( $T < 100$ ).

Each of the next $T$ lines describes one hand. A hand is given as 10 integers — two per card, for 5 cards. For each card, the first integer is its suit (an integer from 0 to 4, inclusive) and the second integer is its value (an integer from 1 to 21, inclusive).

Output

For each test case, print one line stating whether the hand is a spread and whether it is a rainbow.

Format every line exactly as follows: first the spread verdict, left-justified in a field 24 characters wide (padded on the right with spaces), immediately followed by the rainbow verdict.

The spread verdict is Have a spread. or Do not have a spread.
The rainbow verdict is Have a rainbow. or Do not have a rainbow.

Examples4

Example 1

Input

2
0 1 0 2 0 4 0 8 0 16
0 1 1 1 2 1 3 1 4 1

Expected output

Have a spread.          Do not have a rainbow.
Do not have a spread.   Have a rainbow.

Example 2

Input

1
0 1 1 2 2 4 3 8 4 16

Expected output

Have a spread.          Have a rainbow.

Example 3

Input

1
0 1 0 2 1 3 1 4 2 5

Expected output

Do not have a spread.   Do not have a rainbow.

Example 4

Input

4
0 1 0 2 0 4 0 8 0 16
0 1 1 2 2 4 3 8 4 16
0 1 1 1 2 1 3 1 4 1
0 5 0 5 0 5 0 5 0 5

Expected output

Have a spread.          Do not have a rainbow.
Have a spread.          Have a rainbow.
Do not have a spread.   Have a rainbow.
Do not have a spread.   Do not have a rainbow.