Background
He said, what if after breaking out of the cocoon, you find that you are not a butterfly, but an ugly moth?
— Epigraph
Description
Given a binary sequence $a$ of length $2^n$, consisting of $0$s and $1$s. Initially, all elements of the sequence are $0$. Your task is to perform $q$ operations on the sequence:
- Flip operation: For a given index $i$, flip $a_i$ (i.e., change $a_i$ to $1 - a_i$). This operation is denoted as
! i. - Query operation: For a given index $i$, determine whether the number of $1$s among all $a_j$ such that $j \subseteq i$ is odd or even. Here, $j \subseteq i$ means that in the binary representations of $i$ and $j$, every bit that is $1$ in $j$ must also be $1$ in $i$. This operation is denoted as
? i.
Input
The first line contains two integers $n$ and $q$, representing that the length of the sequence is $2^n$, followed by $q$ operations.
The next $q$ lines each represent an operation, which can be one of the following two forms:
! irepresents a flip operation.? irepresents a query operation.
Output
For each query operation ? i, output an integer:
- If the number of $1$s among the $a_j$ satisfying the condition is odd, output $1$.
- If the number of $1$s is even, output $0$.
Examples
Input 1
4 10
! 4
? 15
! 2
? 12
! 8
! 5
? 10
? 7
? 13
? 15Output 1
1
1
0
1
1
0Input 2
32 10
! 772
! 34373648
? 4286562043
? 3890741199
! 18874880
! 269484552
! 1122312
? 4277131259
! 104867841
? 3087007739Output 2
1
1
1
1Constraints
| Subtask ID | Score | Number of Test Cases | $ n= $ | $ q= $ | Special Property |
|---|---|---|---|---|---|
| $1$ | $10$ | $8$ | $24$ | $10^6$ | None |
| $2$ | $10$ | $8$ | $26$ | $10^6$ | None |
| $3$ | $10$ | $8$ | $28$ | $10^6$ | None |
| $4$ | $10$ | $8$ | $30$ | $10^6$ | None |
| $5$ | $10$ | $8$ | $32$ | $10^6-10$ | Randomly generated data |
| $6$ | $50$ | $20$ | $32$ | $10^6$ | None |
For subtask $5$, the data is generated randomly according to the following rules, where all random events are independent:
- Each operation has a $50\%$ probability of being a flip operation or a query operation.
- For a flip operation, each bit of the index has a $70\%$ probability of being $0$ and a $30\%$ probability of being $1$.
- For a query operation, each bit of the index has a $70\%$ probability of being $1$ and a $30\%$ probability of being $0$.
Scoring
Suppose a test case belongs to a subtask worth $S$ points:
Your output will be compared line by line with the correct output. If your output is completely correct, you will receive $S$ points. Otherwise, if the first error in your output occurs at the $x$-th operation, your score will be calculated using the formula $\left\lfloor \dfrac{x-1}{q/S} \right\rfloor$. In other words, you receive $1$ point for every $q/S$ operations processed correctly.
The final score for each subtask is the minimum score among all its test cases. Subtasks are independent and have no dependencies.