Find First and Last Occurrence in Sorted Array

Given a sorted array of integers and a target integer, your task is to find the indices of the first and last occurrences of the target in the array. The algorithm should run in \(O(\log n)\) time by using binary search. If the target is not found in the array, return \([-1, -1]\). Indices are zero-based.

Input is provided via standard input and your output should be printed to standard output.

inputFormat

The input begins with an integer \(T\) representing the number of test cases. Each test case is described as follows:

1. An integer \(n\) representing the number of elements in the array.
2. A line containing \(n\) space-separated integers, representing a sorted array.
3. An integer representing the target value.

Note: For an empty array, \(n\) will be 0 and the corresponding line may be empty.

outputFormat

For each test case, output two integers separated by a space on a new line: the first integer is the index of the first occurrence of the target, and the second is the index of the last occurrence. If the target is not found, output "-1 -1".

## sample

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

1

1 3
-1 -1
2 2
0 5
-1 -1

</p>