Giá trị xor lớn nhất

Cho dãy số nguyên \(a = a_{1}, a_{2},... , a_{n}\) và \(q\) truy vấn. Mỗi truy vấn có dạng \((L, R, x)\), cần tìm \(i\) sao cho \(L ≤ i ≤ R\) và \(a_{i} ∧ x\) đạt giá trị lớn nhất. Các số \(a_{i}\) và \(x\) đều được cho dưới dạng dãy nhị phân.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\);

• Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa số \(a_{i}\) ở dạng nhị phân;

• \(q\) dòng tiếp theo, mỗi dòng chứa \((L, R, x)\) trong đó \(x\) ở dạng nhị phân

Output

Với mỗi truy vấn, in ra kết quả trên một dòng. Nếu có nhiều \(i\) thỏa mãn \(a_{i} ∧ x\) đạt giá trị lớn nhất thì in ra \(i\) nhỏ nhất có thể.

Example

5 4
100
101
1
1011
11
2 3 10
1 5 1100
3 5 1010
1 5 11100

2
5
3
5

Scoring

• Trong tất cả các test: \(n\), \(q ≤ 10^5\); tổng độ dài tất cả các xâu \(a_{i}\) không quá \(10^6\); tổng độ dài tất cả các xâu \(x\) không quá \(10^6\);

• Có \(8\%\) số test với \(n, q ≤ 5000\); độ dài các xâu nhị phân đều không quá \(30\);

• Có \(12\%\) số test với \(n, q ≤ 5000\);

• Có \(28\%\) số test với độ dài các xâu nhị phân đều không quá \(30\);

• Có \(52\%\) số test với ràng buộc gốc.