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