Read problems statements in Mandarin Chinese  and Russian. 

Chef has an array containing N integers. You have to make M queries. Each query has one of the two types:

1 l r p - Select all the numbers having indices between l and r (inclusive) that are divisible by p and divide them by p,
where p is in set {2, 3, 5}.
2 l d - Modify the l-th number in the array to d.

Please help Chef in finding out the array after all the M queries.

------ Input ------ 

The first line of the input contains a single integer N denoting the number of integers in given array. 
The second line contains N space-separated integers A_{1}, A_{2}, ..., A_{N} denoting the given array.
Next line contains a single integer M denoting the number of queries.
Each of the following M lines describes a single query in the format given in the statement.

------ Output ------ 

Output a single line containing N integers denoting the array after all the M queries.

------ Constraints ------ 

$1 ≤ M ≤ 10^{5}$
$1 ≤ l ≤ r ≤ N$
$1 ≤ A_{i} ≤ 10^{9}$
$In each query of first type, p is in set {2, 3, 5} $
$Subtask 1 (20 points): 1 ≤ N ≤ 100$
$Subtask 2 (35 points): 1 ≤ N ≤ 10^{5}, there is no query of second type$
$Subtask 3 (45 points): 1 ≤ N ≤ 10^{5}$

------ Example ------ 

Input:
3
1 2 3
5
1 2 2 2
1 2 2 2
2 2 3
1 2 3 3
2 1 5

Output:
5 1 1

Source: codechef | Difficulty: HARD
Tags: Data structures

Range queries

Segment trees revisited


Solutions:
import sys
n = int(sys.stdin.readline())
bits = [[] for _ in range(6)]
for i in [2, 3, 5]:
	bits[i] = [0] * (n + 1)

def add(bit, index, val):
	index += 1
	while index <= n:
		bit[index] += val
		index += index & -index

def add_range(bit, l, r, val):
	add(bit, l, val)
	add(bit, r + 1, -val)

def get(bit, index):
	r = 0
	index += 1
	while index:
		r += bit[index]
		index -= index & -index
	return r

def reset(bit, index):
	add_range(bit, index, index, -get(bit, index))
s = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
for _ in range(m):
	op = list(map(int, sys.stdin.readline().split()))
	if len(op) == 4:
		(_, l, r, p) = op
		add_range(bits[p], l - 1, r - 1, 1)
	else:
		(_, index, val) = op
		index -= 1
		s[index] = val
		for i in [2, 3, 5]:
			reset(bits[i], index)
for (i, num) in enumerate(s):
	for p in [2, 3, 5]:
		v = get(bits[p], i)
		while v > 0 and num % p == 0:
			num = num // p
			v -= 1
	print(num, end=' ')
print()