RoAlgo Contest #11 - Back to School 2024 | prod3

This was the problem page during the contest. Access the current page here.
Time limit: 4s Memory limit: 512MB Input: Output:

Task

You are given nn, qq, an array of nn elements a1,a2,,ana_1, a_2, \dots, a_n, and qq queries of the following types:

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

Input data

The first line contains two integers, nn and qq. The next line contains the array aa of nn natural numbers. The following qq lines contain the qq queries.

Output data

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

Constraints and clarifications

  • 1n,q21051 \leq n, q \leq 2 \cdot 10^5
  • 1ai,x501 \leq a_i, x \leq 50
# Points Constraints
1 13 1n,q501 \leq n, q \leq 50
2 18 1n,q5001 \leq n, q \leq 500
3 22 1n,q5 0001 \leq n, q \leq 5\ 000
4 47 No additional constraints

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][1, 3], if i=2i = 2, j=1j = 1, and k=3k = 3, we get 2=212 = 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 11 is changed to 22.

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

Log in or sign up to be able to send submissions!