RoAlgo Contest #11 - Back to School 2024 | prod3

Task

You are given $n$, $q$, an array of $n$ elements $a_1, a_2, \dots, a_n$, and $q$ queries of the following types:

• 1 poz x: The element $a_{poz}$ is changed to $x$.
• 2 l r: Display 3 indices $i, j, k$ such that $a_i = a_j \cdot a_k$, where $l \leq i, j, k \leq r$ and $i, j, k$ are pairwise distinct. If there are no such 3 indices, display 0 0 0.

Input data

The first line contains two integers, $n$ and $q$. The next line contains the array $a$ of $n$ natural numbers. The following $q$ lines contain the $q$ queries.

Output data

For each query of type 2, output the answer on a new line.

Constraints and clarifications

• $1 \leq n, q \leq 2 \cdot 10^5$
• $1 \leq a_i, x \leq 50$

Example

stdin

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

stdout

2 1 3
0 0 0
2 4 3

Explanation

In the interval $[1, 3]$, if $i = 2$, $j = 1$, and $k = 3$, we get $2 = 2 \cdot 1$, which is true, so we can output 2 1 3. Note that this is not the only solution.

The element at position $1$ is changed to $2$.

In the interval $[1, 3]$, there are no 3 indices $i, j, k$ such that $a_i = a_j \cdot a_k$, so we output 0 0 0.