A45403.追求更多的玫瑰花

小明同学有一个长度为 $n$ 的数组 $A$，该数组中的元素$A_i$ 要么等于 $1$，要么等于 $-1$。小美同学有 $m$ 个询问，每个询问有两个整数 $l$ 和 $r$，如果小明的数组 $a$ 可以通过重新排列使得 $A_l + A_{l + 1} + ……+ A_{r - 1} + A_{r} = 0$，那么小美就能得到一束玫瑰花。对于每一个询问，如果小美能得到玫瑰花那么输出 "happy"，否则输出 "sad"。

$\large{数据范围}$

• $1 \leq n, m \leq 2 \times 10^5$
• $A_i \in \{-1, 1\}$

第一行输入两个整数 $n, m$，分别代表 $A$ 数组长度和 询问个数。

第二行输入 $n$ 个整数，代表 $A$ 数组。

接下来 $m$ 行，每一行输入两个整数分别代表每次询问的 $l$ 和 $r$。

对于每一个询问，输出一个字符串占一行表示答案，如果能通过排列整个数组，满足区间和为 $0$，输出"happy"， 否则输出 "sad"。

样例解释：

对于第一个询问，我们可以把数组排列成 $[-1, 1, -1, 1]$，这样就能满足区间 $[1, 2]$ 的和为 0，所以输出 "happy"。

对于第二个询问，我们无论如何排列数组，都不能保证区间 $[2, 4]$ 的和为 0，所以输出 "sad"。