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