Roommate Trouble

All submissions for this problem are available.
Pratzz and Abhi are roommates. Pratzz will throw Abhi out of the room if he fails to answer this question. Please help him stay in the room by answering the queries. Formally stating, there is an array A given initially of size N. All the array elements are initially 0.Array is 1indexed.Based on that, you have to process 'Q' queries.Each query can be of 2 types:
1 i a  For this, you have to update the array element at ith index
of array to 'a'.
2 k  To answer this query, we generate a new array S of the same size as given array A.
The description of array S is mentioned below :
S[1]=A[1] when i=1
S[i]=A[i]  S[i1] when i>1 and i<=n . denotes bitwise OR operator.
We need to find a whether a subset of array S exists whose XOR is equal to 'k'.
For example, suppose the elements of a subset of array S is {S[1],S[3],S[4]}, then XOR of the subset = S[1]^S[3]^S[4].
The answer to this query should be either "YES" if we can find a subset of S whose XOR is equal to 'k'
or "NO" otherwise.
Note: Assume XOR of empty subset to be 0.
Input
The first line of input contains N, denoting the number of elements in A and Q, the number of queries. Next Q lines will contain the Q queries described above.
Output
For each query of type 2, answer "YES" or "NO" in a new line..
Constraints
 1 ≤ N,Q ≤ 10^5
 0 ≤ a,k ≤ 10^9
Subtasks
Subtask #1 (20 points), Time limit : 1 sec1 ≤ N,Q ≤ 10, 0 ≤ a,k ≤ 10^9
Subtask #2 (80 points), Time limit : 1 sec
Original Constraints
Example
Input: 4 5 2 0 2 2 1 1 3 2 3 2 2 Output: YES NO YES NO
Explanation
In the sample input 1:
for query 1, Array A={0,0,0,0},Array S={0,0,0,0}. Answer for 0 is YES because it can be formed from Xor of subset {0} .
for query 2, no subset gives Xor as 2 so Answer is NO.
for query 3, we update Array A={3,0,0,0}, Array S={3,3,3,3}.
for query 4, Array A={3,0,0,0}, Array S={3,3,3,3}. Answer for 3 is YES
because it can be formed from Xor of subset {3}.
for query 5, no subset gives Xor as 2 so Answer is NO.
Author:  shivamtanay 
Tags  shivamtanay 
Date Added:  26062017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions