Вам дана последовательность бит $$$a_1, a_2, \dotsc , a_n$$$, где $$$a_i \in \{0, 1\}$$$, а также бит $$$r$$$. Вам нужно поставить максимум одну пару скобок в выражении $$$a_1 \Rightarrow a_2 \Rightarrow \dotsc \Rightarrow a_n$$$ так, чтобы выражение равнялось $$$r$$$. Здесь $$$\Rightarrow$$$ означает битовую импликацию (следствие). Эта операция задаётся следующей таблицей истинности:
| $$$x$$$ | $$$y$$$ | $$$x \Rightarrow y$$$ |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Выражение из нескольких импликаций вычисляется слева направо. Разрешается ставить скобки даже если выражение изначально равнялось $$$r$$$.
В первой строке даётся одно натуральное число $$$n$$$ $$$(2 \le n \le 5 \cdot 10^5)$$$ — количество бит в выражении.
Во второй строке даётся $$$n$$$ бит — переменные $$$a_1, a_2, \dotsc , a_n$$$ $$$(a_i \in \{0, 1\})$$$
В третьей строке даётся один бит $$$r$$$ — требуемый результат выражения.
Если поставить пару скобок в выражении так, чтобы оно стало равняться искомому, невозможно, то выведите одно число «-1» (без кавычек).
Если ставить скобки в выражение не требуется, выведите одно число «0».
Иначе выведите 2 числа $$$l$$$ и $$$r$$$, где $$$l \lt r$$$ — перед какой по счёту переменной нужно поставить открывающую скобку и после какой переменной нужно поставить закрывающую. Обратите внимание, что такая расстановка скобок некорректна: $$$0 \Rightarrow (1) \Rightarrow 1$$$.
Задача состоит из 20 тестов, не считая тестов из условия. Каждый тест оценивается независимо в 5 баллов.
Решения, верно работающие для $$$n \le 100$$$ получат не менее 30 баллов.
Решения, верно работающие для $$$n \le 5000$$$ получат не менее 60 баллов.
3 0 1 0 1
2 3
5 1 0 1 0 0 1
0
4 1 1 1 1 0
-1
В первом примере после установки открывающей скобки до второго элемента и закрывающей после третьего получается выражение $$$0 \Rightarrow (1 \Rightarrow 0) = 0 \Rightarrow 0 = 1$$$. Это единственный ответ для данного теста.
Во втором примере изначальное выражение уже имеет значение 0. Также корректным ответом будет, например, «2 4».
В третьем примере при любой расстановке скобок значение выражения будет 1.
