Given an array of integers of length n in ascending order, and q queries.

For each query, returns the start and end positions of an element k, counted from 0.

"- 1 - 1" is returned if the element does not exist in the array.

Input format

The first row contains the integers n and q, indicating the array length and the number of queries.

The second row contains n integers (all in the range of 1-10000), representing the complete array.

Next, line q, each containing an integer k, represents a query element.

Output format

There are q lines in total. Each line contains two integers, indicating the starting and ending positions of the element.

"- 1 - 1" is returned if the element does not exist in the array.

Data range

1≤n≤1000001≤n≤100000
1≤q≤100001≤q≤10000
1≤k≤100001≤k≤10000

Input example:

6 3
1 2 2 3 3 4
3
4
5

Output example:

3 4
5 5
-1 -1

You can search directly in order, but the time O (n); and the binary search time O (logn)

import java.util.Scanner;

public class Main {
         public static void main(String[] args) {
               Scanner scan=new Scanner(System.in);
               int n=scan.nextInt();
               int q=scan.nextInt();
               int a[]=new int[n];
               for(int i=0;i<n;i++) a[i]=scan.nextInt();
               while(q-->0){
                    int num=scan.nextInt();
                    //Find the left border first
                    int l=0,r=n-1;
                    while(l<r){
                         int mid=l+r>>1;
                         if(a[mid]>=num) r=mid;
                         else l=mid+1;
                    }
                    if(a[l]!=num){
                          System.out.println("-1 -1");
                    }
                    //If you have this number, look for the right boundary
                    else{
                          System.out.print(l+" ");
                          l=0;r=n-1;
                          while(l<r){
                                 int mid=l+r+1>>1;
                                 if(a[mid]<=num) l=mid;
                                 else r=mid-1;
                          }
                          System.out.println(l);
                    }
               }
        }
}