Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Miguel and His Dream House

By iamSadee · Limits 1s, 512 MB

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

InputOutput
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”.


    Discussion

    Statistics


    70% Solution Ratio

    dipubalaEarliest, 3w ago

    AungkurFastest, 0.1s

    shojib_muLightest, 8.7 MB

    RamprosadGShortest, 2466B

    Submit

    Login to submit