All Tracks Algorithms String Algorithms Problem

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...
Your Rating:

Contributor

This Problem was Asked in

Airtel

Challenge Name

Airtel Crack the Code

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?