SOLVE
LATER
You have an array A consisting of n integers. You will be given q queries.
In each query, you will be given two integers l and r which denotes two positions of the array. P is the product of all the integers between \(l^{th}\) and \(r^{th}\) positions. We can write \( P = \prod_{i=l}^{r} A_i \)
For each query you have to determine whether P is a square or cube or both of them or none of them.
Input:
First line will contain two integers \(n (1 \leq n \leq 300000)\) and \(q (1 \leq q \leq 300000)\).
Next line will contain n integers where \(i^{th}(1 \leq i \leq n)\) of them represents \(A_i (-{10}^{5} \leq A_i \leq 10^{5})\).
Each of the next q lines will contain two positive integers l and r.
Output:
For each query print
"\(Square\)" if P is only a square number
"\(Cube\)" if P is only a cubic number
"\(Both\)" if P is both square and cube
otherwise "\(None\)".
Query 1: Product = \(2 \times 4 = 8 \) is a cube.
Query 2: Product = \(4 \times 16 = 64 \) is both square and cube.
Query 3: Product = \(16 \times (-4) = -64 \) is a cube.
Query 4: Product = \(5 \times 5 = 25 \) is a square.
Query 5: Product = \(5 \times 7 = 35 \) is neither a square nor a cube.