Square or Cube
Tag(s):

## Algorithms, Hash function, Hashing algorithm, Medium-Hard, Number Theory, String

Problem
Editorial
Analytics

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$".

SAMPLE INPUT
7 5
2 4 16 -4 5 5 7
1 2
2 3
3 4
5 6
6 7
SAMPLE OUTPUT
Cube
Both
Cube
Square
None

Explanation

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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

Airtel Crack the Code

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Algorithms > Graphs
• Algorithms > Graphs
• Algorithms > Greedy Algorithms
• Algorithms > Graphs