We have two N-bit numbers (0< N< 100000). We have to perform q queries (0< q<500000) over these numbers. The query can be of following three types:

* set\_a idx x: Set A[idx] to x, where 0 <= idx < N, where A[idx] is idx'th least significant bit of A.
* set\_b idx x: Set B[idx] to x, where 0 <= idx < N.
* get\_c idx: Print C[idx], where C=A+B, and 0<=idx

Now, I have optimized the code to the best extent I can.

* First, I tried with an int array for a, b and c. For every update, I calculate c and return the ith bit when queried. It was damn slow. Cleared 4/11 test cases only.
* I moved over to using boolean array. It was around 2 times faster than int array approach. Cleared 7/11 testcases.
* Next, I figured out that I need not calculate c for calculating idx th bit of A+B. I will just scan A and B towards right from idx until I find either a[i]=b[i]=0 or a[i]=b[i]=1. If a[i]=b[i]=0, then I just add up towards left to idx th bit starting with initial carry=0. And if a[i]=b[i]=1, then I just add up towards left to idx th bit starting with initial carry=1.
This was faster but cleared only 8/11 testcases.
* Then, I figured out once, I get to the position i, a[i]=b[i]=0 or a[i]=b[i]=1, then I need not add up towards idx th position. If a[i]=b[i]=0, then answer is (a[idx]+b[idx])%2 and if a[i]=b[i]=1, then the answer is (a[idx]+b[idx]+1)%2. It was around 40% faster but still cleared only 8/11 testcases.

Now my question is how do get down those 3 'hard' testcases? I dont know what they are but the program is taking >3 sec to solve the problem.

Here is the code: <http://ideone.com/LopZf>