SOLVE

LATER

Square or Cube

/

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\)".

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

Initializing Code Editor...