Единственное отличие между простой и сложной версиями — максимальное значение $$$k$$$.

Вам задана бесконечная последовательность вида «112123123412345$$$\dots$$$», в которой следуют блоки всех последовательных целых чисел, записанных друг за другом. Первый блок содержит все числа от $$$1$$$ до $$$1$$$, второй — от $$$1$$$ до $$$2$$$, третий — от $$$1$$$ до $$$3$$$, $$$\dots$$$, $$$i$$$-й блок содержит все числа от $$$1$$$ до $$$i$$$.

Таким образом, первые $$$56$$$ элементов последовательности равны «11212312341234512345612345671234567812345678912345678910». Элементы последовательности нумеруются с единицы. Например, $$$1$$$-й элемент последовательности равен $$$1$$$, $$$3$$$-й элемент последовательности равен $$$2$$$, $$$20$$$-й элемент последовательности равен $$$5$$$, $$$38$$$-й элемент равен $$$2$$$, $$$56$$$-й элемент последовательности равен $$$0$$$.

Перед вами стоит задача ответить на $$$q$$$ независимых запросов. Для $$$i$$$-го запроса задано целое число $$$k_i$$$. Определите элемент последовательности, который находится в позиции $$$k_i$$$.