Четверо Всадников готовят новый трюк. На сцене перед зрителями стоит магическая доска, на которой изначально записано одно число $$$S$$$ — сумма денег, которая якобы лежит в банковской ячейке.

За один ход маги могут выполнить следующий «номер»:

• выбрать какое-то число $$$y$$$, записанное на доске;
• стереть $$$y$$$;
• вместо него записать два натуральных числа $$$a$$$ и $$$b$$$ такие, что $$$y = a + b$$$.

Однако за каждый такой размен продюсеру приходится платить за спецэффекты $$$a \cdot b$$$ монет.

В какой-то момент Всадники хотят, чтобы на доске оказались заранее заданные числа — это суммы, которые зрители якобы увидят на своих счетах после трюка. При этом на доске могут остаться и какие-то лишние числа; главное, чтобы все нужные суммы уже присутствовали.

Дан массив из $$$n$$$ чисел $$$x_1, x_2, \dots, x_n$$$ — потенциальные финальные суммы для разных вариантов трюка.

Продюсер задаёт $$$q$$$ вопросов. Каждый вопрос описывает одну постановку:

• выбирается подотрезок массива $$$x$$$ — от $$$l$$$ до $$$r$$$;
• задаётся исходная сумма на доске $$$S$$$.

Для каждого такого запроса нужно определить, можно ли, начиная с единственного числа $$$S$$$ на доске, с помощью описанных действий получить набор чисел $$$x_l, x_{l+1}, \dots, x_r$$$ (порядок не важен, на доске могут быть дополнительно другие числа). Если можно — сообщить, какова минимальная суммарная стоимость всех разменов в монетах, необходимая для реализации такого трюка; иначе — сообщить, что трюк невозможен.