Danya and Numbers

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Danya has a sequence $A$ of nonnegative integers. Initially, $A$ has length $N$. Let's define a function $f(x, A)$, where $x$ is a positive integer $\le A$, as the maximum of bitwise ANDs of all subsequences of $A$ with length equal to $x$. Kostya gives Danya $M$ requests. There are three types of requests:  $1\;v$: append an integer $v$ to $A$  $2\;v$: delete an element equal to $v$ from $A$; it is guaranteed that $A$ contains $v$ at least once, but if there are more elements equal to $v$, you should only delete one of them  $3\;x$: calculate $f(x, A)$ Also, Kostya knows that at any time, all elements of $A$ are smaller than $2^k$ for a fixed $k$. Help Danya process all of Kostya's requests. ### Input  The first line of the input contains three spaceseparated integers $N$, $M$ and $k$.  The second line contains $N$ spaceseparated integers $a_1, a_2, \dots, a_N$ denoting the initial sequence $A$.  Each of the following $M$ lines contains two spaceseparated integers describing a request in the format $1\;v$, $2\;v$ or $3\;x$. ### Output For each request of type 3, print a single line containing one integer — the value of $f(x, A)$. ### Constraints  $1 \le N, M \le 75,000$  $1 \le k \le 18$  $0 \le v \lt 2^k$  $1 \le x \le A$ ### Example Input ``` 4 7 3 6 7 5 2 3 2 3 3 1 7 3 3 2 7 2 6 3 2 ``` ### Example Output ``` 6 4 6 5 ``` ### Explanation Subsequences giving optimal answers for the requests of type 3 are, in order: $(6, 7)$; $(6, 7, 5)$; $(6, 7, 7)$; $(7, 5)$.Author:  barenuz 
Editorial  https://discuss.codechef.com/problems/DANYANUM 
Tags  barenuz, cook95, medhard, sqrtdecomp 
Date Added:  14062018 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions