URI Online Judge | 2723

Balancing Gifts

By Cristhian Bonilha, UTFPR BR Brazil

Timelimit: 1

Its almost Christmas, and as usual the Santa is getting ready to board his sleigh with all N gifts to be delivered.

The space in which the gifts will be put into in the sleigh can be divided in two sides: side A and side B. To ensure that the sleigh will be balanced, the difference in the sum of gifts on the side A and on the side B can't be greater than 5kg.

You've got the task to help Santa this year. Given the N gifts, you must find out if there's a way to divide them on the sides A and B, ensuring that the sleigh never gets unbalanced.

Notice that the gifts must be alocated one at a time, in the order they are given on the test case, and at every moment the sleigh should be balanced.


There will be T test cases.

Each test case starts with an integer N, indicating the number of gifts to be alocated (1 <= N <= 16*, or 1 <= N <= 10000**).

Following there will be N integers pi, representing the weight of the N gifts (1 <= pi <= 10, for every 1 <= i <= N).

* Will happen at approximately 90% of the test cases.
** Will happen at approximately 10% of the test cases.


For each test case you should print a row, containing the sentence "Feliz Natal!" if its possible to divide the gifts without never losing balance, or "Ho Ho Ho!" otherwise.

Input Sample Output Sample

4 6 2
6 6

Feliz Natal!
Ho Ho Ho!