Федя обожает задачи на структуры данных. Особенно он любит задачи про запросы различных функций на подотрезках массива. А именно, у Феди был прекрасный массив $$$a_1, a_2, \ldots a_n$$$, а также замечательная структура данных, которая позволяла по данным $$$l$$$ и $$$r$$$, $$$1 \le l \le r \le n$$$, находить такое максимальное положительное целое число $$$d$$$ такое, что $$$d$$$ является делителем каждого из чисел $$$a_l$$$, $$$a_{l+1}$$$, ..., $$$a_{r}$$$.

Федя очень любил свою структуру данных, поэтому он воспользовался ей для каждого отрезка массива $$$a$$$ и выписал полученные числа в массив, который Федя сразу же отсортировал по неубыванию. Полученный массив он, недолго думая, назвал $$$b$$$. Нетрудно заметить, что массив $$$b$$$ состоял из $$$n(n+1)/2$$$ элементов.

После этого Федя взял еще одну замечательную структуру данных, которая позволяла по данным $$$l$$$ и $$$r$$$, $$$1 \le l \le r \le n(n+1)/2$$$, находить сумму $$$b_l + b_{l+1} + \ldots + b_r$$$. Конечно же, Федя сразу же воспользовался второй структурой данных для каждого отрезка массива $$$b$$$, а полученный массив отсортировал по неубыванию. Тщательно выбирая имя, он назвал полученный массив $$$c$$$. Помогите Феде найти нижнюю медиану массива $$$c$$$.

Напомним, что для отсортированного массива длины $$$k$$$ нижней медианой называется элемент, который стоит на позиции $$$\lfloor \frac{k + 1}{2} \rfloor$$$, с учетом того, что элементы массива нумеруются с $$$1$$$. К примеру, нижней медианой массива $$$(1, 1, 2, 3, 6)$$$ является число $$$2$$$, а нижней медианой массива $$$(0, 17, 23, 96)$$$ — число $$$17$$$.