ORBOT

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 512M

Authors:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

As much as ButaneBot's newly recoded OR function is cool, he is still getting bored of storing only numbers in the form inside of him. Instead, he has been asked to code a much more interesting problem. There are initially numbers in an array, and queries of the form . After each query, the -th number in the array becomes . Your job is to find the maximum bitwise of ANY consecutive subarray, after every single query. Note that ButaneBot is assuming all numbers are represented as a 32-bit signed two's complement number, and that updates are cumulative. He also assumes that your subarray will be of length at least .

Input Specification

The first line of input will contain the integers and .

The next line will contain integers, the initial array.

The next lines will each have two numbers and which represent the index to be changed and the value of the new number, respectively.

Constraints

At any time, all values in the array will fall in the range

All integers in the input will be either strictly non negative, or strictly non positive.

Output Specification

Output one integer for each query, the maximum bitwise of any consecutive subarray given the current state of the array.

Sample Input

3 2
2 3 -1
3 -2
1 -4

Sample Output

3
3

Explanation for Sample Output

The initial array is . After the first update, the array becomes . The maximum bitwise of a subarray is . After the second update, our array becomes . In this case, the best bitwise we can get is choosing just the number .