Read problems statements [Hindi] , [Vietnamese] , [Mandarin Chinese] , [Russian] and [Bengali] as well.

In ShareChat, there is a sequence of binary integers $A_{1}, A_{2}, \ldots, A_{N}$. You should answer $Q$ queries on this sequence. In each query, you are given two indices $L$ and $R$ and a binary integer $X$.

The answer to a query is the smallest index $i$ ($L ≤ i ≤ R$) such that the value $A_{i} \oplus X$ is maximum possible, i.e. equal to $\mathrm{max}(A_{L} \oplus X, A_{L+1} \oplus X, \ldots, A_{R} \oplus X)$. Here, $\oplus$ denotes the bitwise XOR operation.

------  Input ------
The first line of the input contains two space-separated integers $N$ and $Q$.
$N$ lines follow. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of these lines contains a single binary string denoting the number $A_{i}$ (in binary representation).
The following $Q$ lines describe queries. Each of these lines contains two space-separated integers $L$ and $R$, followed by a space and a binary string denoting the number $X$ (in binary representation).

------  Output ------
For each query, print a single line containing one integer — the answer to that query.

------  Constraints ------
$1 ≤ N ≤ 10^{5}$
$1 ≤ Q ≤ 10^{5}$
$1 ≤ A_{i}$ for each valid $i$
$1 ≤ L ≤ R ≤ N$
$1 ≤ X$
the sum of lengths of strings denoting $A_{1}, A_{2}, \ldots, A_{N}$ does not exceed $10^{6}$
the sum of lengths of strings denoting $X$ over all queries does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (33 points): all binary strings on the input have equal lengths

Subtask #2 (67 points): original constraints

----- Sample Input 1 ------ 
5 4

100

101

1

1011

11

2 3 10

1 5 1100

3 5 1010

1 5 11100
----- Sample Output 1 ------ 
2

5

3

5

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

String algorithms

Sorting

Segment trees revisited

Complete search

Mathematics

Data structures


Solutions:
(N, M) = map(int, input().split())
A = []
for i in range(N):
	A.append(input())
Q = []
for i in range(M):
	(l, r, v) = input().split()
	Q.append((int(l), int(r), v))
import random

def genInput(N, M, large=False):
	if large:
		A = ['1' + ''.join(['1' if random.randint(0, 10) > 4 else '0' for _ in range(random.randint(1000 if i < 10 else 1, 2000 if i < 10 else 20))]) for i in range(N)]
		Q = []
		for i in range(M):
			l = random.randint(1, N // 2)
			r = random.randint(l, N)
			v = '1' + ''.join(['1' if random.randint(0, 10) > 4 else '0' for _ in range(random.randint(1000 if i < 10 else 1, 20000 if i < 10 else 20))])
			Q.append((l, r, v))
		return (N, M, A, Q)
	else:
		A = ['1' + ''.join(['1' if random.randint(0, 10) > 4 else '0' for _ in range(1, random.randint(1, 20))]) for _ in range(N)]
		Q = []
		for i in range(M):
			l = random.randint(1, N // 2)
			r = random.randint(l, N)
			v = '1' + ''.join(['1' if random.randint(0, 10) > 4 else '0' for _ in range(random.randint(1, 20))])
			Q.append((l, r, v))
		return (N, M, A, Q)
tree = {'c': [], 'v': [], 'vl': 0}

def compressStr(num, maxLen):
	ans = []
	ln = len(num)
	if ln < maxLen:
		ans.append((maxLen - ln, '0'))
	elif ln > maxLen:
		num = num[ln - maxLen:]
	(i, j) = (0, 0)
	while j < len(num):
		if num[j] != num[i]:
			ans.append((j - i, num[i]))
			i = j
		j += 1
	ans.append((j - i, num[i]))
	if len(ans) > 1 and ans[0][1] == ans[1][1]:
		ans[:2] = [(ans[0][0] + ans[1][0], ans[0][1])]
	return ans

def diffCompressedStr(u, v):
	(ui, vi) = (0, 0)
	same = []
	while ui < len(u) and vi < len(v):
		if u[ui][1] == v[vi][1]:
			if u[ui][0] == v[vi][0]:
				same.append((u[ui][0], u[ui][1]))
				ui += 1
				vi += 1
			elif u[ui][0] < v[vi][0]:
				same.append((u[ui][0], u[ui][1]))
				v[vi] = (v[vi][0] - u[ui][0], v[vi][1])
				ui += 1
			else:
				same.append((v[vi][0], v[vi][1]))
				u[ui] = (u[ui][0] - v[vi][0], u[ui][1])
				vi += 1
		else:
			break
	return (same, u[ui:], v[vi:])

def popLeft(num, count=1):
	c = 0
	for i in range(len(num)):
		if c + num[i][0] > count:
			return [(num[i][0] - count + c, num[i][1])] + num[i + 1:]
		else:
			c += num[i][0]
	return []

def rev(val):
	return '1' if val == '0' else '0'

def buildTree(num, idx, numLen):
	t = tree
	num = compressStr(num, numLen)
	while num:
		tv = t['v']
		(same, vleft, num) = diffCompressedStr(tv, num)
		if not vleft:
			if num:
				u = num[0][1]
				ru = rev(u)
				if u in t:
					t['c'].append(idx)
					t = t[u]
					num = popLeft(num, 1)
				elif ru in t:
					t[u] = {'c': [idx], 'v': popLeft(num, 1)}
				else:
					t['c'].append(idx)
					t['v'] = num
					return
			else:
				t['c'].append(idx)
				return
		else:
			c0 = t['0'] if '0' in t else None
			c1 = t['1'] if '1' in t else None
			v0 = vleft[0][1]
			n0 = num[0][1]
			t[n0] = {'c': [idx], 'v': popLeft(num, 1)}
			t[v0] = {'c': [x for x in t['c']], 'v': popLeft(vleft, 1)}
			if c0:
				t[v0]['0'] = c0
			if c1:
				t[v0]['1'] = c1
			t['v'] = same
			t['c'].append(idx)
			return
	t['c'].append(idx)

def computeTreeValLen(t):
	if not t:
		return
	if 'v' in t:
		t['vl'] = sum([x[0] for x in t['v']] or [0])
	else:
		t['vl'] = 0
	if '0' in t:
		computeTreeValLen(t['0'])
	if '1' in t:
		computeTreeValLen(t['1'])
MXD = max([len(x) for x in A])
for (i, v) in enumerate(A):
	buildTree(v, i + 1, MXD)
computeTreeValLen(tree)
import json

def check(l, r, idx):
	if not idx:
		return False
	if idx[0] > r or idx[-1] < l:
		return False
	if l <= idx[0] <= idx[-1] <= r:
		return True
	(a, b) = (0, len(idx))
	while a < b:
		c = (a + b) // 2
		v = idx[c]
		if l <= v <= r:
			return True
		if v < l:
			a = c + 1
		elif v > r:
			b = c
	return False

def find(l, r, idx):
	(a, b) = (0, len(idx))
	while a < b:
		c = (a + b) // 2
		v = idx[c]
		if v < l:
			a = c + 1
		elif v > r:
			b = c
		else:
			b = c
	return idx[a]

def query(l, r, num):
	num = compressStr(num, MXD)
	t = tree
	while num:
		if len(tree['c']) <= 1:
			break
		if t['v']:
			num = popLeft(num, t['vl'])
			if not num:
				break
		a = num[0][1]
		ra = rev(a)
		if ra in t and check(l, r, t[ra]['c']):
			t = t[ra]
			num = popLeft(num, 1)
		elif a in t and check(l, r, t[a]['c']):
			t = t[a]
			num = popLeft(num, 1)
		else:
			break
	return find(l, r, t['c'])
ans = []
for (l, r, v) in Q:
	ans.append(query(l, r, v))
print('\n'.join(map(str, ans)))


from collections import defaultdict
from bisect import bisect_left, bisect_right
from math import log2, ceil
maxpow = 0

class TrieNode:

	def __init__(self, key):
		self.key = key
		self.children = [None] * 2
		self.data = []

class Trie:

	def __init__(self):
		self.root = self.newNode(-1)

	def newNode(self, key):
		return TrieNode(key)

	def insert(self, key, idx):
		pCrawl = self.root
		for i in range(maxpow, -1, -1):
			f = check(key, i)
			if not pCrawl.children[f] or pCrawl.children[f] == None:
				pCrawl.children[f] = self.newNode(key)
			pCrawl = pCrawl.children[f]
			pCrawl.data.append(idx)

	def insert_list(self, arr):
		for i in range(len(arr) - 1):
			key = arr[i]
			pCrawl = self.root
			for j in range(maxpow, -1, -1):
				f = check(key, j)
				if not pCrawl.children[f]:
					pCrawl.children[f] = self.newNode(key)
				pCrawl = pCrawl.children[f]
				pCrawl.data.append(i)

	def find_max_xor(self, x):
		pCrawl = self.root
		res = 0
		for i in range(maxpow - 1, -1, -1):
			f = check(x, i)
			if pCrawl.children[f ^ 1]:
				res += 2 ** i
				pCrawl = pCrawl.children[f ^ 1]
			else:
				pCrawl = pCrawl.children[f]
		return res

	def query(self, big_nums, l, r, x):
		res = 0
		pCrawl = self.root
		pCrawl2 = None
		for i in range(maxpow, -1, -1):
			f = check(x, i)
			done = False
			if pCrawl.children[f ^ 1]:
				pCrawl2 = pCrawl.children[f ^ 1]
				p = bisect_left(pCrawl2.data, l)
				if p == len(pCrawl2.data):
					p -= 1
				if pCrawl2.data[p] >= l and pCrawl2.data[p] <= r:
					res = 2 * res + 1
					pCrawl = pCrawl2
					done = True
			if not done and pCrawl.children[f]:
				pCrawl = pCrawl.children[f]
				res *= 2
		idx = -1
		for i in big_nums.keys():
			if l <= i <= r:
				xo = big_nums[i] ^ x
				if xo > res:
					idx = i
					res = xo
		return (res ^ x, idx)

def check(b, pos):
	return 1 if b & 2 ** pos else 0

def brute(arr, N, Q):
	results = []
	for i in range(N):
		x = int(input(), 2)
		arr.append(x)
	for i in range(Q):
		(l, r, x) = input().split()
		(l, r, x) = (int(l), int(r), int(x, 2))
		mx = -1
		idx = 0
		for j in range(l, r + 1):
			if arr[j - 1] ^ x > mx:
				mx = arr[j - 1] ^ x
				idx = j
		results.append(idx)
	print('\n'.join((str(k) for k in results)))

def solve():
	global maxpow
	(N, Q) = map(int, input().split())
	indexes = defaultdict(list)
	results = []
	arr = []
	big_nums = defaultdict(int)
	max_ = int('1' * (60 - 2 * N // 10000), 2)
	if Q * N < 300000000:
		brute(arr, N, Q)
		return
	for i in range(N):
		x = int(input(), 2)
		if x > max_:
			big_nums[i] = x
			x = 0
		arr.append(x)
		indexes[x].append(i + 1)
	maxpow = ceil(log2(max(arr)))
	arr.append(0)
	TRIE = Trie()
	TRIE.insert_list(arr)
	for _ in range(Q):
		(L, R, X) = input().split()
		(L, R, X) = (int(L) - 1, int(R) - 1, int(X, 2))
		if X > max_:
			idx = L + 1
			res = arr[L] ^ X
			for j in range(L + 1, R + 1):
				xo = arr[j] ^ X
				if xo > res:
					res = xo
					idx = j + 1
			for i in big_nums.keys():
				if L <= i <= R:
					xo = big_nums[i] ^ X
					if xo > res:
						idx = i + 1
						res = xo
			results.append(idx)
		else:
			(q, idx) = TRIE.query(big_nums, L, R, X)
			if idx != -1:
				results.append(idx + 1)
				continue
			i = bisect_right(indexes[q], L - 1)
			if indexes[q][i] < L + 1:
				i += 1
			results.append(indexes[q][i])
	print('\n'.join((str(k) for k in results)))
solve()