1340. XOR Queries of a Subarray

Given an array arr and a list of queries where each query is a pair [l, r], return an array whose i-th entry is the XOR of arr[l], arr[l+1], ..., arr[r] for the i-th query. Both endpoints are inclusive.

Input: A JSON object {"arr": [<integers>], "queries": [[l, r], ...]} with 0 <= l <= r < len(arr).

Output: Return an array of query answers in the original order.

Examples

Input: {"arr":[1,3,4,8],"queries":[[0,1],[1,2],[0,3],[3,3]]}
Output: [2,7,14,8]
Explanation: Prefix XORs answer each range: 2, 7, 14, 8.

Input: {"arr":[4,8,2,10],"queries":[[2,3],[1,3],[0,0],[0,3]]}
Output: [8,0,4,4]
Explanation: Each range XOR computed from prefixes.

Constraints

• 1 <= len(arr) <= 3 * 10^4
• 1 <= len(queries) <= 3 * 10^4
• 0 <= arr[i] <= 10^9

Asked by