Description

快乐数做完了吗？快乐数组来了

一个数组是「快乐数组」当且仅当：

• 该数组不是回文数组

• 修改恰好一个元素后，该数组变成回文数组。

所谓回文数组，即将一个数组左右翻转后，和原数组相同，例如[12,3,12]是回文数组。

现在小明拿到了一个数组，请你帮小红判断这个数组是不是快乐数组，

如果是，在第一行输出"Happyhappyhappy"（不含双引号）；

如果不是，在第一行输出"Sadsadsad"，并判断该数组的和是不是快乐数，

如果是快乐数，在第二行输出YES，否则输出NO。

Format

Input

第一行为一个整数 $n(0 < n < 1e6)$ 。

第二行输入$n$个整数$a[i](0<a[i]<1e5)$，表示小明拿到的数组

Output

如果$a$是快乐数组，在第一行输出Happyhappyhappy，

否则在第一行输出Sadsadsad，并判断$a$中所有元素的和是不是快乐数

如果和是快乐数，在第二行输出YES，否则输出NO

Samples

5
1 2 3 4 5

Sadsadsad
NO

1
10

Sadsadsad
YES

6
1 2 3 4 2 1

Happyhappyhappy

2
1 2

Happyhappyhappy

Hint

「快乐数」定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数最后只剩下一位。
• 如果最后剩下的数是1，那么这个数就是快乐数。（如果这个数一开始就是个位数，且不等于1，那它也不是快乐数，1是快乐数）