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.


hide comments
785227: 2014-03-09 07:09:58

If n=0 , what should i print, HAPPY or SAD ??

aqfaridi: 2014-03-07 12:24:12

weak test cases..

P_Quantum: 2014-03-03 08:31:06

Nice prblm :)

Ujjwal Prakash: 2014-02-25 12:41:47

In the constraints the value of N is 10^5 but the solutions with O(n^2) and O(n^2 logn) are also getting accepted which is not all possible to pass within the given time limit
See my solutions with id 11131847 and 11132648 respectively
--ans(francky)--> There's at least one test case with N>50000. Tested.

EDIT: It may be that the test cases for for which N>50000 ,contains values which may become invalid as per my algo in the beginnning of the loops and for those cases my code don't run for n^2 or n^2 logn

Last edit: 2014-02-25 18:06:17
Thomas Dybdahl Ahle: 2014-02-23 16:47:44

If people have read a solution to a problem, it is my opinion that they shouldn't try to submit it on SPOJ. Or if they do, at least they should disqualify it once they have tested their solution.

[Lakshman]: 2014-02-20 13:14:44

@ Thomas Dybdahl Ahle please disqualify all those solution who have submitted his solution.
@Nisant raj I checked yor profile today,please do not publish spoj solutions.

Last edit: 2014-02-20 16:26:44
Thomas Dybdahl Ahle: 2014-02-20 10:19:04

A lot of people seem to have copied the solution of NISHANT RAJ. Please only submit if you solve the problem yourself.

Kevin Sebastian: 2014-02-19 05:04:53

@author pls tell me what testcase my code fails id 11091475

Last edit: 2014-02-19 06:52:48
Thomas Dybdahl Ahle: 2014-02-18 16:20:38

You can easily generate testcases yourself: Just draw a random graph and read off the vertex degrees.
Or try to prove that your solution us correct.


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