Background

【The First Fleet has sent a message】
【It is about the battle result of Floating Island No. 15】
【The defense operation of Floating Island No. 15...】
【Has failed...】

Problem Description

Chtholly gives you a sequence. It supports point updates, and queries asking for the minimum possible length of an interval whose bitwise OR sum is greater than or equal to a given number. If there is no solution, output $-1$.

Input Format

The first line contains two integers $n, m$.

The next line contains $n$ integers, representing the sequence $a$.

The next $m$ lines are in one of the following forms:

• $1\ i\ x$: set $a_i$ to $x$.
• $2\ k$: query the minimum length such that there exists an interval of that length whose bitwise OR sum is $\geq k$.

Output Format

For every operation of type $2$, output one line containing an integer, the answer. If there is no solution, output $-1$.

2 3
0 2 
2 3
1 1 1
2 3

-1
2

Hint

Idea: kczno1.

Solution: kczno1 ($O( m\sqrt n\log a )$ solution), liu_cheng_ao ($O( m\log^2 n\log^2 a )$ solution), 142857cs ($O( m\log n\log^2 a )$ solution).

Code: kczno1 ($O( m\sqrt n\log a )$ code), liu_cheng_ao ($O( m\log^2 n\log^2a$ ) code).

Data: kczno1.

Constraints: For $100\%$ of the testdata, $0\leq a_i, k\leq 2^{30}$, $1\leq n, m\leq 5\times 10^4$.

Translated by ChatGPT 5