VFRIEND2 - Very Friends 2

You are creating a new social 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 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

x0 = 0
xi+1 = (a*xi + b) % m

The sequence of wishes is wi = xi + 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".


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

hide comments
2023-08-08 10:17:11
CAN ANYONE MENTION FULL FORM FOR EG ALGORITHM o(n) way to do this ?? I GOT HH IS HAVEL HAKIMI ALGO, CANT FIND WHATS EG


Last edit: 2023-08-08 10:17:37
2018-07-10 16:44:20
can someone please help in O(n) solution i am not getting O(n)
2018-06-15 09:40:36
learnt something new and interesting:)
2015-01-21 03:35:54 Eric Gross
@Tanmay
There's an O(N) implementation of EG
2014-06-01 06:59:40 Tanmay
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?
2014-02-23 02:08:42 Francky
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 ;-)
2014-02-21 23:45:32 NISHANT RAJ
how O(N) solution is possible forthis
@ Thomas Dybdahl Ahle
2014-02-18 04:46:01 Jacob Plachta
Yeah, it might be best to only have one version of this problem.
2014-02-18 00:19:37 Thomas Dybdahl Ahle
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..
2014-02-17 19:15:12 Jacob Plachta
After submitting an O(N) solution, I also thought to try submitting my O(N log N) solution from VFRIENDS, which ran in time. It might be too hard to really rule out such a solution, though you can try increasing the bounds and decreasing the time limit a bit.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.