Miguel is ready to build his dream house in honor of his great grandfather Hector. There is an Array of Length N containing the heights of N bricks. Each integer Ai denoting the height of i-th brick. Miguel will choose a range of bricks so that his great grandmother Mamá Imelda will be happy. She will be happy if the range contains every distinct height even number of times.

Miguel wants to make his great grandmother and great grandfather happy. He is little busy in some works. So he gives the problem to "MBSTU CSE Victory Day Contest 2020". He will ask Q query. In each query, you will be asked either update or delete any brick or check whether the range contains every distinct height even number of times from index L to index R (inclusive).

Input

First line contains two integers N, Q(1 <= N, Q <= 105)Next Line contains N space separated integer denoting height of ith type brick (1 <= Ai <= 2* 106)Next Q lines each contain a query of the following list: • 1 id X (update index id of brick array A with X ) (1 <= X <= 2* 106) • 2 id (delete index id of brick array A) • 3 L R (check whether the range contains every distinct height even number of times from index L to index R)

Here, the first index is considered as 1.

It is guaranteed that There is no such query that brick array length will become 0.

1 <= L, R <= Current_Brick_Array_Length

Output

For each query of 3rd type, print one line denoting that if the range is Happy , print "Happy" otherwise "Unhappy".

Sample

Input

Output

5 3
1 2 1 2 1
3 1 2
2 3
3 1 4

Unhappy
Happy

Given Brick List is : 1 2 1 2 1

For the first query , range 1-2 contains both 1 and 2 one time . the range is "Unhappy". For second query , delete index 3, the brick list became : 1 2 2 1 For third query , range 1-4 contain both 1 and 2 even number of times. The range is "Happy".