33OJ
登录 注册

#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 pp, if pm∣np^m \mid n and pm+1∤np^{m+1} \nmid n, we say potp(n)=m\text{pot}_p(n)=m.

The pot is very special that it can make everyone awake immediately.

Now Little L provides n (1≤n≤105)n~(1 \le n \le 10^5) integers a1,a2,⋯ ,ana_1, a_2, \cdots, a_n to Little Q, each of which is 11 initially. After that, Little L shows 22 types of queries:

  • MULTIPLY l r x: For every i∈[l,r]i \in [l,r] (1≤l≤r≤n1\le l\le r\le n), multiply aia_i by xx (2≤x≤102 \le x \le 10).
  • 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 pp is prime.

Now you need to perform q (1≤q≤105)q~(1 \le q \le 10^5) 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 yy the value you've calculated.

Input Format

The first line contains two integers n (1≤n≤105)n~(1 \le n \le 10^5) and q (1≤q≤105)q~(1 \le q \le 10^5), the number of integers and the number of queries.

Each of the next qq lines contains one type of query described above.

Output Format

For each “MAX” query, output one line in the format of ANSWER y, where yy 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 mm and nn are non-zero integers, or more generally, non-zero elements of an integral domain, it is said that mm divides nn if there exists an integer kk, or an element kk of the integral domain, such that m×k=nm \times k=n, and this is written as m∣nm \mid n.