You are given a binary string s and a two dimensional integer array queries where each queries[i] = [first_i, second_i].

For each query $i$, find a substring of s starting at index left_i and ending at index right_i inclusive, such that the decimal value represented by this binary substring, denoted as val, satisfies:

val $\oplus$ first_i $=$ second_i

where $\oplus$ represents the bitwise XOR operation.

If multiple valid substrings exist for a query, select the one with the shortest length. If there is still a tie, select the substring with the smallest starting index left_i. If no such substring exists, the answer for that query is $[-1, -1]$.

Return an array ans where ans[i] = [left_i, right_i] represents the answer to the $i^{ ext{th}}$ query, or $[-1, -1]$ if no valid substring is found.

Constraints:

• $1 \leq$ s.length $\leq 10^4$

• s[i] is either '0' or '1'

• $1 \leq$ queries.length $\leq 10^5$

• $0 \leq$ first_i, second_i $\leq 10^9$

Input: s = "0"-str, queries = [[0, 0], [6, 7]]-List[List[int]]
Output: [[0, 0], [-1, -1]]-List[List[int]]
Explanation: For [0, 0], the substring "0" at index 0 has value 0, satisfying 0 XOR 0 = 0. No valid substring exists for [6, 7].

Input: s = "0011100"-str, queries = [[4, 4], [3, 2], [8, 15]]-List[List[int]]
Output: [[0, 0], [2, 2], [2, 4]]-List[List[int]]
Explanation: The shortest valid substrings for the three queries are selected at indices [0, 0], [2, 2], and [2, 4], respectively.

Input: s = "1010110"-str, queries = [[0, 5], [7, 2], [10, 3], [1000000000, 1000000000]]-List[List[int]]
Output: [[0, 2], [0, 2], [-1, -1], [1, 1]]-List[List[int]]
Explanation: The shortest valid substring for the first two queries is at indices [0, 2]. No valid substring exists for [10, 3], while the query [1000000000, 1000000000] is satisfied by the substring at index [1, 1].

Input: s = "11101111"-str, queries = [[0, 3], [0, 7], [5, 5], [20, 4]]-List[List[int]]
Output: [[0, 1], [0, 2], [3, 3], [-1, -1]]-List[List[int]]
Explanation: The shortest valid substrings for the first three queries are located at [0, 1], [0, 2], and [3, 3]. No valid substring exists for [20, 4].

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.