Bitwise OR

3.3

9 votes
String Algorithms, Algorithms, String Searching
Problem

You are given an array A of length N and an integer X. You are required to find all the subarrays of minimum length with BITWISE OR greater than or equal to X.

Input format

  • The first line of input contains an integer T denoting the number of test cases. 
  • The first line of each test case contains N and X.
  • The second line of each test case contains N space-separated integers each representing elements of array A.

Output format
For each test case: 

In the first line, print count of such subarrays (let it be C). In the next C lines, print all the subarrays (in sorted order).
Note: A subarray can be defined by 2 indexes L and R where L and R are starting and ending indexes of that subarray)

Constraints

1 ≤  T ≤ 3

1 ≤  N ≤ 10^5

0 ≤  A[i] ≤ 10^9

0 ≤  X ≤ 1073741823

Sample Input
3
5 7
1 2 3 4 5
4 15
1 2 4 8
4 16
1 2 4 8
Sample Output
1
3 4
1
1 4
0
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation
  • For 1st test case, 7 can be achieved by 3 or 4.
  • For 2nd test case, value greater than or equal to 15 is only possible if we take Or or complete array.
  • For 3rd test case, Or of complete array is less than X, so no possible solution.
Editor Image

?