Красота бинарной строки — это количество в ней \(\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\).
Выходные данные
Для каждого набора входных данных, если не существует подходящих \(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\).
Примечание
В первом примере красота \(\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}\).
В последнем примере мы не должны разбивать строку.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|