Назовем две строки \(a\) и \(b\) (обе длиной \(k\)) немного похожими, если они имеют один и тот же символ в некоторой позиции, то есть существует по крайней мере одно \(i \in [1, k]\) такое, что \(a_i = b_i\).
Задана двоичная строка \(s\) длины \(n\) (строка из \(n\) символов 0 и/или 1) и целое число \(k\). Обозначим строку \(s[i..j]\) как подстроку \(s\), начинающуюся с \(i\)-го символа и заканчивающуюся \(j\)-м символом (то есть \(s[i..j] = s_i s_{i + 1} s_{i + 2} \dots s_{j - 1} s_j\)).
Назовем двоичную строку \(t\) длины \(k\) красивой, если она немного похожа на все подстроки \(s\), имеющие длину ровно \(k\); то есть она немного похожа на \(s[1..k], s[2..k+1], \dots, s[n-k+1..n]\).
Ваша задача — найти лексикографически наименьшую строку \(t\), которая является красивой, или сообщить, что такой строки не существует. Строка \(x\) лексикографически меньше строки \(y\), если \(x\) является префиксом \(y\) (и \(x \ne y\)), либо существует такое \(i\) (\(1 \le i \le \min(|x|, |y|)\)), что \(x_i < y_i\), и для любого \(j\) (\(1 \le j < i\)) \(x_j = y_j\).