01204212/resistors

This is part of 01204212

You want to buy a resistor. The shop has a lot of resistors available. If you want a resister with the resistance of r ohm, you are usually fine with having a resister with the resistance higher than r ohm.

There are 2 versions of the task.

Resistor 1: Unlimited supply

There are n types of resistors in the shop. Type i resistors have the resistance of r_i ohm.

You get m' requests, each request specifies the expected resistance x. You want to answer with the smallest resistance r_i available at the shop which is at least as large as x. If every resistor at the shop has resistance less than x, you should output -1.

Input/output

Input

• First line: two integers n and m (1<=n<=100,000; 1<=m<=100,000)
• Next n lines: line 1+i contains resistance r_i. It is guaranteed that the values are increasing r_i < r_i+1, for 1<=i<n.
• Next m lines: line 1+n+j specifies the j-th request as an integer x.

Output

The output contains m lines. Each line specifies the smallest resistance r_i available at the shop which is at least as large as x. If every resistor at the shop has resistance less than x, you should output -1.

Example

Input

5 5
10
20
30
50
100
9
15
30
101
21

Output

10
20
30
-1
30

Code

Hint: look at TreeSet

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    int n,m;
    int[] rs;
    int[] xs;
    
    public static void main(String[] args) throws Exception {
        Main m = new Main();
        
        m.readInput();
        m.process();
    }

    private void process() {    
        // your code here
    }
    
    private void readInput() throws Exception {
        BufferedReader reader = new BufferedReader(
                   new InputStreamReader(System.in) );

        String[] items = reader.readLine().split(" "); 
                
        n = Integer.parseInt(items[0]);
        m = Integer.parseInt(items[1]);
        
        rs = new int[n];
        xs = new int[m];

        for(int i=0; i<n; i++) {
            rs[i] = Integer.parseInt(reader.readLine());
        }

        for(int i=0; i<m; i++) {
            xs[i] = Integer.parseInt(reader.readLine());
        }
    }
}