VFRIENDS - Very Friends

NOTICE: The test cases for this problem are not as hard as intended. If you've solved this problem, and think your solution is up for it, try VFRIEND2!

You are creating a new soical network for dogs. Wow. The dogs don't have many possibilities for interacting with your website, but they can bark how many friends they want. E.g. if a dog wants to have much 8 friends it will bark 8 times, and if it doesn't want any friends, it'll just stay quiet.

After spending a good year of your life collecting these barks, you are finally ready to assign a friend list for each dog. The only problem is: You are not sure whether it is actually possible. Thus before you proceed you would like to write a program, that given a list of N wishes wi, outputs HAPPY if it is possible to make a friend list for each dog i of length wi, or SAD if some dog will have to get more or fewer friends than it wished for.

Notice: Being friends is considered an irreflexive, symetric relation.

Update: If you manage to solve this problem much efficiently, have a look at VFRIEND2, which is a so harder version of this problem.

Input

The first line will contain a single integer T - the number of test cases to process.

Each following lines will start with an integer 0 ≤ N ≤ 105 followed by an ordered list of N wishes 0 ≤ wi ≤ 105.

Output

Write the answer - HAPPY or SAD - for each test case on a separate line.

Example

Input:
3
3 0 1 1
5 0 1 2 3 4
6 1 1 2 2 3 3 Output: HAPPY
SAD
HAPPY

Explanation

In the first case we can make dog 2 and 3 be friends.

In the second case no assignment that works, since dog 5 would have to be friends with everyone, but dog 1 doesn't want that.


Added by:Thomas Dybdahl Ahle
Date:2014-02-17
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2018-06-08 20:32:33
Got AC in 1.22s with a clumsy PyPy solution and realized there's something I need to learn to get AC in pure Python. But before investigating, I've decided to debug an earlier idea taking advantage of efficient Python idioms and was absolutely floored with the result. Learned something new afterwards, but didn't beat the time of my own adhoc =) Python has just obsoleted a bit of graph teory.

Thanks to psetter for lenient TL that made it worthwhile to experiment, othwerise I would have missed one of the biggest WTF moments in my coding experience.
2017-09-02 17:33:09
Hi , is there Russian translation??
2016-01-02 13:54:31 Thomas Dybdahl Ahle
@Filip, @aqfaridi @Ujjwal Prakash: There is a harder version (not allowing O(n^2) solutions) at VFRIEND2. I've updated this problem description with a link.

Last edit: 2016-01-02 13:57:26
2015-12-08 15:02:57 Filip Sollar
nice problem, learned a lot but weak test cases
2014-08-19 21:56:33 Joker
@thomas
can u check my id and tell where my algo fails
12169560
2014-04-25 23:32:50 مجد
a really good problem ... learned something new :)
2014-03-12 18:35:33 Avinash
@ author
Got it ! Silly mistake !

Last edit: 2014-03-13 04:32:46
2014-03-09 07:37:52 Dhandapani
@785227
HAPPY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.