Hamming Distance Checker in Subarrays

You are given an array of n integers and a threshold value t. For a series of queries, each specifying a subarray by its starting index L and ending index R, determine if the Hamming distance between every two consecutive elements in the subarray is at most t. The Hamming distance between two integers a and b is computed as the number of 1's in the binary representation of a \oplus b (i.e., the number of differing bits). Formally, for every consecutive pair of elements arr[i] and arr[i+1] in the subarray from L to R (inclusive), the condition must hold: \[ \text{HammingDistance}(arr[i], arr[i+1]) \leq t \] If the subarray contains only one element, it trivially satisfies the condition. Your task is to process all queries and output whether each subarray meets the criteria.

Note: The input will be provided via standard input and the output should be printed to standard output.

inputFormat

The first line contains an integer n, the size of the array.

The second line contains n space-separated integers representing the elements of the array.

The third line contains an integer t, the threshold for the Hamming distance.

The fourth line contains an integer q, representing the number of queries.

Each of the following q lines contains two space-separated integers L and R indicating the start and end indices (0-indexed) of the subarray.

outputFormat

For each query, print a single line containing either True if the Hamming distance condition is satisfied for the subarray or False otherwise.

## sample

5
1 4 3 6 7
2
2
0 2
2 4

False
True

</p>