EVENFRQ - Even Frequency


 

Kutus loves even number. Girl friend of kutus, name putus makes an interesting
problem for kutus to testing his even number knowledge. Putus gives an integer
array A, consisting of N number.
Putus asked Kutus to process the following three types of queries on this array
accurately and efficiently.
• 0 X V: add V to the Xth element of array. i.e AX = AX + V.
• 1 L R V: replace all the element in range L to R with V.
• 2 L R: Find out whether all elements frequency in the range L to R is/are even or
not

Kutus loves even number. Girl friend of kutus, name putus makes an interesting problem for kutus to testing his even number knowledge. Putus gives an integer array A, consisting of N number.

Putus asked Kutus to process the following three types of queries on this array accurately and efficiently.

• 0 X V: add V to the Xth element of array. i.e AX = AX + V.

• 1 L R V: replace all the element in range L to R with V.

• 2 L R: Find out whether all elements frequency in the range L to R is/are even or not

 

Input

Input start with an integer T, which denotes the number of test case. Each case contains 2 space separated integer N and Q denoting the size of array A and the number of queries to be performed.

Next line contains N space separated integers denoting the elements of array A. Each of the next Q lines of input contains a query having one of the mentioned three types. There will be no more than fifty update operation (type 0 & type 1).

Output

For each case print the case number and print the answer. If all elements frequency in the range L to R is/are even, then answer will be ‘Yes’ otherwise answer will be ‘No’.

 

Constraints:

T <= 10

1 <= N <= 100000

1 <= Q <= 100000

0 <= Ai , V <= 100000

1 <= L <= R <= N

 

Example

Input:
1
5 6
1 2 2 3 2
2 2 3
0 5 1
2 2 5
2 1 5
1 1 3 2
2 1 5

Output:
Case 1:
Yes
Yes
No
No

hide comments
smtcoder: 2016-08-16 09:29:54

getting TLE even after using both methods of mapping and hashing.. :(

[Rampage] Blue.Mary: 2016-07-22 17:41:34

I've used some evil technique to successfully "attack" this problem :-)


Added by:Anick
Date:2016-07-22
Time limit:1s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Problem setter: Tanvir Hasan Anick. Alternate: Niloy D rocker