#P17638. [ICPC 2019 Yinchuan R] Pot!!
[ICPC 2019 Yinchuan R] Pot!!
Problem Description
Little Q is very sleepy, and he really needs some coffee to make him awake. At this time, Little L brings a pot to Little Q, and he states the pot as follows.
For a prime number , if and , we say .
The pot is very special that it can make everyone awake immediately.
Now Little L provides integers to Little Q, each of which is initially. After that, Little L shows types of queries:
- MULTIPLY l r x: For every (), multiply by ().
- MAX l r: Calculate the value of$$\max_{l\le i\le r} \left\{ \max_{p|a_i} \left\{ \text{pot}_p (a_i) \right\} \right\}~(1 \le l \le r \le n),$$where is prime.
Now you need to perform queries of these two types of queries described above.
If you perform a “MULTIPLY” query, you don't need to output anything.
If you perform a “MAX” query, you need to output a line like ANSWER y, where the value you've calculated.
Input Format
The first line contains two integers and , the number of integers and the number of queries.
Each of the next lines contains one type of query described above.
Output Format
For each “MAX” query, output one line in the format of ANSWER y, where the value you have calculated.
5 6
MULTIPLY 3 5 2
MULTIPLY 2 5 3
MAX 1 5
MULTIPLY 1 4 2
MULTIPLY 2 5 5
MAX 3 5
ANSWER 1
ANSWER 2
Hint
If and are non-zero integers, or more generally, non-zero elements of an integral domain, it is said that divides if there exists an integer , or an element of the integral domain, such that , and this is written as .