VFRIEND2  Very Friends 2
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 w_{i}, outputs HAPPY if it is possible to make a friend list for each dog i of length w_{i}, or SAD if some dog will have to get more or fewer friends than it wished for.
Notice: Being friends is considered a reflexive relation.
Input
The first line will contain a single integer T  the number of test cases to process.
Because of I/O constraints, the sequence of wishes is not given explicitly. Each of the T lines will consist of 5 integers N, a, b, c, m in the range [0, 10^7] (except m which is in [1, 10^7]). These integers describe the sequence
x_{0} = 0
x_{i+1} = (a*x_{i }+ b) % m
The sequence of wishes is w_{i} = x_{i} + c.
Output
Write the answer  HAPPY or SAD  for each test case on a separate line.
Example
Input: 3 3 2 1 0 2 5 1 1 0 5 6 1 1 1 3 Output: HAPPY
SAD
HAPPY
Explanation
In the first case we get the wishes "0 1 1", and we can make dog 2 and 3 be friends.
In the second case we get the wishes "0 1 2 3 4". No assignment that works, since dog 5 would have to be friends with everyone, but dog 1 doesn't want that.
In the third case we get the wishes "1 2 3 1 2 3".
hide comments
shubh011:
20180710 16:44:20
can someone please help in O(n) solution i am not getting O(n) 

be1035016:
20180615 09:40:36
learnt something new and interesting:) 

Eric Gross:
20150121 03:35:54
@Tanmay


Tanmay:
20140601 06:59:40
How is O(N) solution possible? Both algorithms I'm aware of (EG and HH) require at least O(N^2) time. Can someone help? 

Apoorv Jindal:
20140305 00:07:53
Last edit: 20140316 15:46:40 

Francky:
20140223 02:08:42
I want to thank the psetter ; input file is made of strong cases. I tried some probabilistic heuristics to attack some corners with relations between N,M,C and input resisted ; so good choices of parameters ;)


NISHANT RAJ:
20140221 23:45:32
how O(N) solution is possible forthis


Jacob Plachta:
20140218 04:46:01
Yeah, it might be best to only have one version of this problem. 

Thomas Dybdahl Ahle:
20140218 00:19:37
I think it's very hard to make time limits that rule out something as optimised as sorting. On the other hand, I have code for this problem that doesn't need to store the sequence, so perhaps I could make a memory limit.. 

Jacob Plachta:
20140217 19:30:43
Last edit: 20140217 20:18:07 
Added by:  Thomas Dybdahl Ahle 
Date:  20140217 
Time limit:  1s3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 