Minimum Subarray Length with Sufficient Bitwise OR

You are given a sequence of integers. The sequence supports two types of operations:

1. Update Query: Change the value at a specific position in the sequence.
2. Range Query: Given a range \([L, R]\) and an integer \(X\), find the shortest contiguous subarray within \([L, R]\) such that the bitwise OR of its elements is \(\ge X\). If no such subarray exists, output \(-1\).

Note: In the output, if a valid subarray does not exist, print the value \( -1 \) (i.e., \(\-1\)).

Input Format: The first line contains two integers \(n\) and \(q\) denoting the size of the sequence and the number of queries respectively. The second line contains \(n\) integers representing the initial sequence. Each of the following \(q\) lines describes a query. A query is in one of the following two formats:

• "1 pos val" : Update the element at position pos to val (1-indexed).
• "2 L R X" : Query for the shortest subarray within the interval \([L, R]\) (1-indexed) whose bitwise OR is \(\ge X\).

inputFormat

The first line contains two space-separated integers \(n\) and \(q\) \( (1 \leq n, q \leq 10^5)\), representing the number of elements in the sequence and the number of queries respectively.

The second line contains \(n\) space-separated integers, the initial sequence.

Each of the next \(q\) lines represents a query in one of the following formats:

• 1 pos val : Update the element at position \(pos\) to \(val\).
• 2 L R X : Query for the shortest contiguous subarray within the interval \([L, R]\) with bitwise OR \(\ge X\).

outputFormat

For each query of the second type, output a single line containing the minimum possible length of the subarray whose bitwise OR is \(\ge X\). If no such subarray exists, output -1.

sample

5 5
1 2 4 7 8
2 1 5 7
1 3 3
2 2 5 2
2 1 3 6
2 4 5 11

1
1
-1
2