SOLVE

LATER

Rahul's Lucky ID Number

/

Rahul will be assigned his college id number soon.

He considers the id number to be lucky for himself if it can be expressed in the form-

\(2^x+2^y\) ( \(x \neq y , x \geq 0 , y \geq 0\)).

He plays a game in which he decides to make N guesses for his id number and wants you to perform some queries on his guesses, which fall in either of the two categories-

__Category 1:__

Given p,q change his p-th guess to q

__Category 2:__

Given p,q find how many lucky id numbers exist from his p-th guess to q-th guess.(both inclusive).

If p > q then print 0.

**Input Format:**

The first line contains T, the number of testcases.

For each testcase,

A separate line contains N, the number of guesses Rahul makes.

The next line contains N space separated integers denoting the guesses for his id number.

The next line contains Q, the number of queries.

Each query contains three space separated integers m, p, q.

m denotes the category of the query (1 or 2) and p, q are the parameters to be used by each of the query.

**Output Format:**

Answer category 2 of the query by printing the required integer on a new line.

__For Instance__- Using 1-based indexing, category 2 asks you to count the number of lucky guesses among the guess at p-th index, guess at (p+1)-th index and so on till the guess at q-th index.

If m=2 and p > q then print 0.

**Constraints: **

0<=Rahul’s Guess(id number)<= (10^9+1)

0 < T <= 2

0 < N <= 10^5

0 < Q <= 10^5

m is either 1 or 2

1 <= p <= N

0 <= q <= (10^9+1) (if m is 1)

1 <= q<= N (if m is 2)

Explanation

(T=1)

The N = 2 guesses are as below:

1st guess 3

2nd guess 1

Q=4

__ 1st query__-(category 1)

p=2 q=6

Change p th guess i.e 2nd guess to 6

Therefore, 2nd guess becomes 6

__ 2nd query__-(category 2)

p=1 q=2

We find number of lucky id numbers from 1st guess to 2nd guess (both inclusive)

1st guess is 3=2^1+2^0 (lucky)

2nd guess is 6=2^1+2^2 (lucky)

So, we print 2 as the answer to this query.

__ 3rd query__-(category 1)

Similarly, this query makes 1st guess as 2

and

__ 4th query__-(category 2)

we find the number of lucky guesses from 1st guess to 1st guess-

1st guess is 2 (can't be expressed as 2^x+2^y where x!=y,x>=0,y>=0)

So this guess is unlucky and we print 0.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...