Online Query with Divisible Division

You are given a sequence of non-negative integers of length \(n\). The sequence supports the following two operations:

• 1 l r x: For every element in the subarray \([l, r]\) that is a multiple of \(x\), divide that element by \(x\).
• 2 l r: Query the sum of the subarray \([l, r]\).

This is an online problem. For each query, the parameters \(l\), \(r\), and \(x\) (if applicable) are XOR-ed with the previous answer. If there is no previous answer, the value is considered to be \(0\).

inputFormat

The first line contains two integers \(n\) and \(q\), representing the number of elements in the sequence and the number of queries, respectively.

The second line contains \(n\) non-negative integers \(a_1, a_2, \dots, a_n\) which form the sequence.

Each of the following \(q\) lines describes a query in one of the following formats:

• 1 l r x — In the subarray \([l, r]\), for every element that is divisible by \(x\), divide it by \(x\).
• 2 l r — Output the sum of the subarray \([l, r]\).

Note: In every query, the parameters are XOR-ed with the previous answer (initially \(0\)).

outputFormat

For each query of type 2, output a single integer on a new line indicating the sum of the elements in the queried subarray.

sample

5 5
12 15 18 20 24
2 1 5
1 2 4 2
2 1 5
1 1 3 3
2 1 5

89
59