Олимпиадный тренинг

Задача . E. Медвежонок и плохие степени числа 42

Задача

Лимак — маленький медвежонок, и он плохо отвечает на запросы. Поэтому он просит вас о помощи.

Назовём все неотрицательные целые степени числа 42 (то есть числа 1, 42, 1764, ...) плохими. Все остальные числа являются хорошими.

Вам дана последовательность хороших целых чисел t₁, t₂, ..., t_n. Требуется выполнить q запросов трёх видов:

1 i — выведите число t_i на отдельной строке.
2 a b x — для всех $\text{[math]}$ присвоить t_i = x. Гарантируется, что число x является хорошим.
3 a b x — для всех $\text{[math]}$ увеличить t_i на x. Затем повторять этот процесс до тех пор, пока хотя бы одно число t_i является плохим.

Несложно заметить, что после выполнения каждого запроса, все числа t_i являются хорошими.

Входные данные

В первой строке входных данных записаны два целых числа n и q (1 ≤ n, q ≤ 100 000) — длина последовательности Лимака и количество запросов соответственно.

Во второй строке входных данных записаны n целых чисел t₁, t₂, ..., t_n (2 ≤ t_i ≤ 10⁹) — изначальные элементы последовательности Лимака. Гарантируется, что все t_i являются хорошими числами.

Далее следуют q строк, описывающих запросы. В i-й из них содержится описание i-го запроса. Первое число каждой из этих строк определяет тип запроса type_i (1 ≤ type_i ≤ 3). Гарантируется, что во входных данных будет хотя бы один запрос первого типа, то есть корректные выходные данные будут непусты.

Гарантируется, что во всех запросах второго и третьего типов 1 ≤ a ≤ b ≤ n.

Гарантируется, что во всех запросах второго типа целое число x (2 ≤ x ≤ 10⁹) является хорошим. В запросах третьего типа число x (1 ≤ x ≤ 10⁹) может быть плохим.

Выходные данные

Для каждого запроса первого типа выведите ответ на отдельной строке.

Примечание

После запроса 3 2 4 42 последовательность равна 40, 1742, 49, 1714, 4, 1722.

После запроса 3 2 6 50 последовательность равна 40, 1842, 149, 1814, 104, 1822.

После запроса 2 3 4 41 последовательность равна 40, 1842, 41, 41, 104, 1822.

После запроса 3 1 5 1 последовательность равна 43, 1845, 44, 44, 107, 1822.