Единственное отличие между простой и сложной версиями — максимальное значение \(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\).
Выходные данные
Выведите \(q\) строк. В \(i\)-ю строку должна быть выведена цифра \(x_i\) \((0 \le x_i \le 9)\) — ответ на запрос номер \(i\), то есть \(x_i\) должно быть равно элементу последовательности, который находится в позиции \(k_i\).