E. Произведение замыканий
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем замыканием целого числа $$$x \gt 0$$$ следующую бесконечную бинарную строку $$$C(x)$$$:

  1. Выпишем $$$x$$$ в бинарном представлении без лидирующих нулей;
  2. Склеим полученную строку с самой собой бесконечное количество раз и назовем результат $$$C(x)$$$.

Например, $$$C(1)$$$ $$$=$$$ 11111..., $$$C(4)$$$ $$$=$$$ 10010010010010..., $$$C(9)$$$ $$$=$$$ 100110011001....

Назовем произведением двух замыканий $$$C(x) \mathop{\&} C(y)$$$ бесконечную бинарную строку, полученную путем поэлементного бинарного AND строк $$$C(x)$$$ и $$$C(y)$$$. Например, для $$$C(4) \mathop{\&} C(9)$$$ мы получим

$$$$$$ \begin{array}{r} \begin{array}{r} C(4)\\ C(9)\\ \end{array} \mathop{\&} \begin{array}{r} 100100100100100100...\\ 100110011001100110...\\ \end{array} \\ \hline \begin{array}{r} 100100000000100100... \end{array} \end{array} $$$$$$

Вам заданы три числа $$$l$$$, $$$r$$$ и $$$n$$$. Среди всех чисел на отрезке $$$[l, r]$$$ найдите два числа $$$x$$$ и $$$y$$$ ($$$l \le x \lt y \le r$$$) таких, что $$$C(x) \mathop{\&} C(y)$$$ — лексикографически минимально, и выведите первые $$$n$$$ бинарных символов этого произведения.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

В единственной строке каждого набора заданы три целых числа $$$l$$$, $$$r$$$ и $$$n$$$ ($$$1 \le l \lt r \lt 2^{30}$$$; $$$1 \le n \le 1000$$$) — отрезок возможных значений и длина ответа.

Выходные данные

Для каждого набора входных данных выведите одну бинарную строку длины $$$n$$$ — первые $$$n$$$ символов лексикографически наименьшего произведения замыканий.

Пример
Входные данные
3
1 4 10
1073741822 1073741823 35
10 20 15
Выходные данные
1000001000
11111111111111111111111111111011111
100000000010000
Примечание

В первом наборе входных данных лексикографически наименьшую строку дает произведение $$$C(2) \mathop{\&} C(4)$$$.