У Саши есть две бинарные строки \(s\) и \(t\) одинаковой длины \(n\), состоящие из символов 0 и 1.
Также есть вычислительная машина, которая умеет выполнять два вида операций с бинарными строками \(a\) и \(b\) одинаковой длины \(k\):
- Если \(a_{i} = a_{i + 2} =\) 0, то можно присвоить \(b_{i + 1} :=\) 1 (\(1 \le i \le k - 2\)).
- Если \(b_{i} = b_{i + 2} =\) 1, то можно присвоить \(a_{i + 1} :=\) 1 (\(1 \le i \le k - 2\)).
Саше стало интересно следующее: если рассмотреть строку \(a=s_ls_{l+1}\ldots s_r\) и строку \(b=t_lt_{l+1}\ldots t_r\), то какое максимальное количество символов 1 в строке \(a\) можно получить с помощью вычислительной машины. Так как Саша очень любознательный, но ленивый, то вам предстоит ответить на этот вопрос для нескольких интересующих его пар \((l_i, r_i)\).
Выходные данные
Для каждого набора входных данных выведите \(q\) целых чисел — ответы на все запросы.
Примечание
В первом наборе входных данных:
- В первом запросе \(a =\) 11, поэтому максимальное количество символов 1 равно \(2\).
- Во втором запросе \(a =\) 111, поэтому максимальное количество символов 1 равно \(3\).
Во втором наборе входных данных:
- В первом запросе \(a =\) 101 и \(b =\) 110. Никаких операций сделать нельзя, поэтому максимальное количество символов 1 равно \(2\).
- Во втором запросе \(a =\) 1010 и \(b =\) 1101. Так как \(a_2 = a_4 =\) 0, то можно присвоить \(b_3 :=\) 1. Теперь \(b_1 = b_3 =\) 1, поэтому можно присвоить \(a_2 :=\) 1. Строка \(a\) стала равна 1110, поэтому максимальное количество символов 1 равно \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
1111
0000
2
1 2
2 4
4
1010
1101
2
1 3
1 4
6
010101
011010
5
2 3
1 6
2 5
4 4
3 6
|
2
3
2
3
1
4
3
1
2
|