Учёные с планеты Нибиру уже несколько десятилетий трудятся над созданием двигателя, который позволит космическим кораблям попадать в гиперпространство и двигаться там со сверхсветовой скоростью. Чтобы проверить, верны ли их представления о свойствах гиперпространства, учёные разработали следующий эксперимент.

В гиперпространство помещают цепочку из n частиц, позиции в которой пронумерованы от 1 до n. Изначально i-я частица имеет заряд a_i.

Согласно современной теории, если на частицу с номером i попадает специальное излучение мощности d, по гиперпространству распространяются колебания, которые увеличивают на d заряд частиц под номерами i, 2i, 3i и т. д. (то есть под номерами, которые делятся на i).

С помощью специального прибора учёные могут направить излучение одинаковой мощности на отрезок соседних частиц. Например, пусть изначально было 6 частиц с нулевыми зарядами, и учёные направили излучение мощности 5 на частицы с номерами 2 и 3. Тогда заряд частиц с номерами 2, 3, 4 повысится до пяти, а заряд частицы с номером 6 — до десяти (колебания настигнут её дважды). Заряд остальных частиц не изменится.

Без воздействия прибора заряд частиц в эксперименте меняться не может.

В течение эксперимента учёные планируют выполнять действия следующих типов:

Вашей программе будет дан список выполненных действий. На каждое действие первого типа она должна выдать ожидаемый заряд частицы, рассчитанный согласно современной теории, описанной выше.

Если ожидаемый заряд частиц совпадёт с зарядом, измеренным во время эксперимента, представления учёных о природе гиперпространства окажутся верными, и они смогут приступить к постройке гипердвигателей. Тогда всего через несколько лет жители Нибиру наконец-то встретятся со своими братьями с Земли!

Первая строка содержит единственное число n — количество частиц (1 ≤ n ≤ 3 · 10⁵).

Вторая строка содержит n целых чисел a_i, записанных через пробел — начальные заряды частиц (0 ≤ a_i ≤ 10⁶).

Третья строка содержит единственное число q — количество действий в эксперименте (1 ≤ q ≤ 3 · 10⁵).

В следующих q строках вводится либо два, либо четыре целых числа через пробел — описание очередного действия в одном из следующих форматов:

Для каждого запроса первого типа выведите ожидаемый заряд i-й частицы.