F. Дзюдзю и бинарная строка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Красота бинарной строки — это количество в ней $$$\texttt{1}$$$, делённое на длину строки. Например, красота строки $$$\texttt{01101}$$$ равна $$$\frac{3}{5}$$$.

У Дзюдзю есть бинарная строка $$$s$$$ длины $$$n$$$. Она хочет выбрать некоторые непересекающиеся подотрезки $$$s$$$ так, чтобы их конкатенация имела длину $$$m$$$ и такую же красоту, как и строка $$$s$$$.

Более формально, она хочет найти два массива $$$l$$$ и $$$r$$$ равной длины $$$k$$$ таких, что $$$1 \leq l_1 \leq r_1 < l_2 \leq r_2 < \ldots < l_k \leq r_k \leq n$$$, а также:

  • $$$\sum\limits_{i=1}^k (r_i - l_i + 1) = m$$$;
  • Красота $$$s[l_1,r_1]+s[l_2,r_2]+\ldots+s[l_k,r_k]$$$ в точности равна красоте $$$s$$$, где $$$s[x, y]$$$ обозначает подотрезок $$$s_x s_{x+1} \ldots s_y$$$, а $$$+$$$ обозначает конкатенацию строк.
Дзюдзю не любит разделять строки на много частей, поэтому она также хочет минимизировать значение $$$k$$$. Найдите минимальное значение $$$k$$$ такое, что существуют массивы $$$l$$$ и $$$r$$$, удовлетворяющие ограничениям выше, или определите, что подходящих массивов $$$l$$$ и $$$r$$$ не существует ни при каком $$$k$$$.
Входные данные

Первая строка содержит единственное целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq m \leq n \leq 2 \cdot 10^5$$$).

Вторая строка каждого набора содержит бинарную строку $$$s$$$ длины $$$n$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных, если не существует подходящих $$$l$$$ и $$$r$$$, выведите $$$-1$$$.

Иначе выведите $$$k + 1$$$ строку.

В первой строке выведите число $$$k$$$ ($$$1 \leq k \leq m$$$) — минимальное количество требуемых подотрезков.

Затем выведите $$$k$$$ строк, $$$i$$$-я строка должна содержать $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$) — границы $$$i$$$-го подотрезка. Обратите внимание, что вы должны выводить подотрезки так, чтобы выполнялось неравенство $$$l_1 \leq r_1 < l_2 \leq r_2 < \ldots < l_k \leq r_k$$$.

Пример
Входные данные
4
4 2
0011
8 6
11000011
4 3
0101
5 5
11111
Выходные данные
1
2 3
2
2 3
5 8
-1
1
1 5
Примечание

В первом примере красота $$$\texttt{0011}$$$ равна красоте $$$\texttt{01}$$$.

Во втором примере красота $$$\texttt{11000011}$$$ равна $$$\frac{1}{2}$$$ и не существует подотрезка длины $$$6$$$ с такой же красотой. Поэтому мы должны использовать $$$2$$$ непересекающихся подотрезка $$$\texttt{10}$$$ и $$$\texttt{0011}$$$.

В третьем примере есть $$$8$$$ способов разбить строку таким образом, что $$$\sum\limits_{i=1}^k (r_i - l_i + 1) = 3$$$, но ни в одном из них конкатенация не будет иметь такую же красоту, как $$$\texttt{0101}$$$.

В последнем примере мы не должны разбивать строку.