For a binary string S, define its beauty to be the maximum number of [substrings] S can be partitioned into, such that each substring has strictly more ones than zeroes. For example, the beauty of 11011 is 3, as it can be partitioned as [110][1][1]. If such a partition doesn't exist, the beauty is defined to be 0. 

Also, define the happiness of a binary string to be the maximum beauty over all its substrings. For example, the happiness of the string S = 010011011 is 3, which is the beauty of its substring 11011.

You are given N binary strings S_{1}, S_{2}, \ldots, S_{N}. You have to process Q queries:
- Each query consists of two integers L, R, where 1 ≤ L ≤ R ≤ N.
- The result of the query is the maximum possible happiness of S_{p_{1}} + S_{p_{2}} + \ldots S_{p_{(R - L + 1)}}, where p is some permutation of \{L, L + 1, \ldots, R - 1, R\} and + denotes the concatenation operation.

------ Input Format ------ 

The first line of input contains two space-separated integers N and Q, the number of strings and the number of queries. Then, 2N + Q lines follow:
- For each 1 ≤ i ≤ N, S_{i} is represented by two lines. The first line contains the length of S_{i} and the second line contains S_{i} itself.
- Each of the next Q lines contains two integers, L and R, denoting the query parameters

------ Output Format ------ 

For each query, print the maximum possible happiness of the concatenation of some permutation of the given interval on a new line.

------ Constraints ------ 

$1 ≤ N, Q ≤ 10^{5}$
$|S_{i}| ≥ 1$ for each valid $i$.
- Every string consists of characters which are either '0' or '1'.
- The sum of the lengths of all the input strings doesn't exceed $10^{6}$.

------ subtasks ------ 

Subtask 1 (30 points): The sum of $R L + 1$ over all queries doesn't exceed $10^{6}$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------ 
4 1
1
0
2
11
3
010
4
0110
2 4
----- Sample Output 1 ------ 
3
----- explanation 1 ------ 
It is optimal to concatenate as $S_{3} + S_{4} + S_{2}$ to get $010011011$ with a happiness value of $3$.

Source: codechef | Difficulty: VERY_HARD
Tags: Range queries

Greedy algorithms

Segment trees revisited

Dynamic programming

Data structures


Solutions:
from sys import stdin
input = stdin.readline
inp = lambda : list(map(int, input().split()))

def b_s(take, left, right):
	(l, h) = (0, len(take) - 1)
	while l <= h:
		mid = (l + h) // 2
		if take[mid] < left:
			l = mid + 1
			continue
		if take[mid] > right:
			h = mid - 1
			continue
		return take[mid]

def sparse_query(b, left, right):
	dist = right - left + 1
	if dist == 0:
		return 0
	for i in range(19, -1, -1):
		if dist >> i & 1:
			msb = i
			break
	return max(b[left][msb], b[right - (1 << msb) + 1][msb])

def sparse_table(b):
	for j in range(1, 20):
		for i in range(n - (1 << j - 1)):
			b[i][j] = max(b[i][j - 1], b[i + (1 << j - 1)][j - 1])

def answer():
	best_ans = [[0 for i in range(20)] for j in range(n)]
	best_suf = [[0 for i in range(20)] for j in range(n)]
	best_pref = [[0 for i in range(20)] for j in range(n)]
	takes = dict()
	takep = dict()
	total = [0]
	for i in range(n):
		(ans, sval) = (0, 0)
		for j in s[i]:
			if j == '1':
				sval += 1
			else:
				sval -= 1
			ans = max(ans, sval)
			if sval <= 0:
				sval = 0
		best_ans[i][0] = ans
		(ans, sval) = (0, 0)
		for j in s[i]:
			if j == '1':
				sval += 1
			else:
				sval -= 1
			ans = max(ans, sval)
		best_pref[i][0] = ans - max(0, sval)
		total.append(total[-1] + max(0, sval))
		key = ans - max(0, sval)
		if key not in takep:
			takep[key] = []
		takep[key].append(i)
		(ans, sval) = (0, 0)
		for j in s[i][::-1]:
			if j == '1':
				sval += 1
			else:
				sval -= 1
			ans = max(ans, sval)
		best_suf[i][0] = ans - max(0, sval)
		key = ans - max(0, sval)
		if key not in takes:
			takes[key] = []
		takes[key].append(i)
	sparse_table(best_pref)
	sparse_table(best_suf)
	sparse_table(best_ans)
	for i in range(q):
		(l, r) = inp()
		(l, r) = (l - 1, r - 1)
		ans = sparse_query(best_ans, l, r)
		t = total[r + 1] - total[l]
		bs = sparse_query(best_suf, l, r)
		mid = b_s(takes[bs], l, r)
		bp = max(sparse_query(best_pref, l, mid - 1), sparse_query(best_pref, mid + 1, r))
		ans = max(ans, t + bs + bp)
		bp = sparse_query(best_pref, l, r)
		mid = b_s(takep[bp], l, r)
		bs = max(sparse_query(best_suf, l, mid - 1), sparse_query(best_suf, mid + 1, r))
		ans = max(ans, t + bp + bs)
		print(ans)
for T in range(1):
	(n, q) = inp()
	(size, s) = ([], [])
	for i in range(n):
		size.append(int(input()))
		s.append(input().strip())
	answer()