Consider a prime number p.

All operations below will be performed in the multiplicative group modulo p.

Given an array of size n, process q queries of two types:

In the first line of input, there are three integers p, n, q: the prime number, the size of the array and the number of queries (2 ≤ p < 10⁹, p is prime, 1 ≤ n ≤ 10⁵, 1 ≤ q ≤ 10⁵).

The second line of input contains the initial array a of size n (1 ≤ a_i < p).

The next q lines describe the queries.

A query of the first type is described as “1 l r x”: multiply all elements of the segment [l; r] by x (1 ≤ l ≤ r ≤ n, 1 ≤ x < p).

A query of the second type is described as “2 l r”: find the order of the subgroup generated by the set of elements from the segment [l; r] (1 ≤ l ≤ r ≤ n).

For each query of the second type, print the answer to it on a separate line.

Originally this problem has TL = 10 sec. You may need some hard optimizations to get AC. Have fun :)

In this section, we will give definitions for all terms from group theory which appear in the statement. All the definitions are conventional, so feel free to skip the section if you are familiar with the basics of group theory.

A group is a set with associative binary operation. The group is closed under its operation: for any two elements a and b of the group, a ○ b is also an element of this group, where ○ is the binary operation. There exists the identity element (equivalent of 1 for multiplication), and for every element there exists an inverse.

A multiplicative group modulo prime number p is defined as follows. The elements of the group are non-zero remainders modulo p: that is, 1, 2, …, p−1. The operation is multiplication modulo p. It is easy to see that it is a group.

A subgroup is a subset H of group G which itself is a group for the same operation as in G: in particular, it is closed under the binary operation.

A subgroup generated by a set: for any subset S ⊆ G, ⟨S⟩ is the smallest subgroup G which contains S. This subgroup is unique.

The order of the group is the number of elements in it.