Костя и Игнат обожают числа в качестве подарков, но почти всегда начинают спорить, когда получают одновременно два числа, которые являются взаимно простыми (то есть их наибольший общий делитель равен 1).

Вадим решил их обрадовать и сделать им подарок в один и тот же день. К этому случаю у него на верхней полке завалялся массив из N чисел, только вот доступ к нему у Вадима крайне ограничен. В некоторые дни он может доставать числа только из подотрезка [l, r], а в некоторые — доступа и вовсе нет, в такие дни число на позиции p меняется на какое-то другое.

Для каждого дня, когда у Вадима есть доступ, он хочет найти пару чисел, которые он может подарить Косте и Игнату, либо определить, что таких нет. Ваша задача состоит в том, чтобы помочь ему в этом непростом задании.

В первой строке даны два целых числа N и Q — количество чисел в массиве и количество интересующих дней (2 ≤ N ≤ 10⁵, 1 ≤ Q ≤ 10⁵).

Во второй строке даны N целых чисел a_i — все элементы массива до старта интересующих дней (2 ≤ a_i ≤ 10⁶).

В следующих Q строках описаны интересующие дни в одном из следующих форматов

Для каждого дня, в котором имеется доступ к подотрезку, нужно вывести -1, если пары не взаимно простых чисел не найдётся, либо две различные позиции, принадлежащие данному подотрезку, на которых стоят два не взаимно простых числа.

Если существует несколько ответов, выведите любой.