L. Emoticons
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bob has received a text message from his girlfriend Alice. The message consists only of colons (":") and brackets ("(" and ")"). Two consecutive characters in the message form an emoticon if one of them is a colon and the other one is a bracket. If the bracket's inner side faces the colon, the emoticon is a smiley; otherwise it is a frowney. So, ":)" and "(:" are smilies, and ":(" and "):" are frownies. One character can belong to two emoticons: for example, there are both a smiley and a frowney in the message "):)".

Unfortunately, Bob has trouble understanding the message. He can only find out Alice's mood based on the number of emoticons in the message:

  • If there are more smilies than frownies, Alice is happy.
  • If the number of smilies is equal to the number of frownies, Alice is just texting him because she's bored.
  • If there are more frownies than smilies, Alice is sad.

Help Bob determine how does Alice feel!

Input

The first line contains a single integer n, the length of the message (1 ≤ n ≤ 105). The next line contains the message, a string consisting of n characters. Each of the characters is either ":", "(" or ")".

Output

In a single line, output either "HAPPY", "BORED" or "SAD" corresponding to Alice's mood.

Examples
Input
10
:)))))))))
Output
HAPPY
Input
1
:
Output
BORED
Input
8
)::(:():
Output
SAD