ICHB Selection Contest '17 Problem 3 - Parallel Universe

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.2s
Memory limit: 64M

Problem type

You are locked in a parallel universe and for you to be able to escape you have to answer Q (Q \le 100\,000) queries on an array named v with N (N \le 100\,000) elements. The queries are as follows:

  • U x val - Change the value of v[x] to val (0 \le val \le 2^{32} - 1)
  • Q x y val - Print val \mathbin{\&} v[x] \mathbin{\&} v[x + 1] \mathbin{\&} \cdots \mathbin{\&} v[y]. Here, \& refers to bitwise AND. (1 \le x \le y \le N)

Input Specification

On the first line you will find N and Q.
On the second line you will find N numbers, where the i-th number is v[i].
On the next Q lines you will find the queries.

Output Specification

For each Q type query, print each result on a different line.

Sample Input

3 3
5 7 15
Q 1 3 7
U 1 0
Q 1 3 15

Sample Output



There are no comments at the moment.