ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

2124. Algebra on Segment

Time limit: 4.0 second
Memory limit: 256 MB
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:
  • l r x”: multiply all elements of the segment [l; r] by x;
  • l r”: find the order of the subgroup generated by the set of elements from the segment [l; r].

Input

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 < 109, p is prime, 1 ≤ n ≤ 105, 1 ≤ q ≤ 105).
The second line of input contains the initial array a of size n (1 ≤ ai < p).
The next q lines describe the queries.
A query of the first type is described as “l r x”: multiply all elements of the segment [l; r] by x (1 ≤ lrn, 1 ≤ x < p).
A query of the second type is described as “l r”: find the order of the subgroup generated by the set of elements from the segment [l; r] (1 ≤ lrn).

Output

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

Sample

inputoutput
17 3 7
10 16 2
2 2 3
2 1 2
2 2 2
1 1 2 3
2 1 1
2 3 3
2 1 3
8
16
2
4
8
16

Notes

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 SG, ⟨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.
Problem Author: Alexey Danilyuk
Problem Source: Petrozavodsk Summer 2018. t.me/umnik_team Contest