Challenge: Shipping Price Bands

Lab Java Intermediate 20 points

A courier's price depends on weight bands: each band says “from weight w upward, the price is c” (until the next band starts). For each parcel, print its price, or no band if it is lighter than every band. Use a TreeMap and floorEntry.

Input

Line 1: b. Then b lines w c. Then a line with q, then q parcel weights on one line.

Output

One price (or no band) per line.

Example

Input

3
1 50
5 90
20 200
5
3 5 19 20 100

Output

Sample input available Sample output available

Editor

Java

Hints

Store band start → price in a TreeMap.

floorEntry(weight) finds the band that starts at or below the weight (null if none).

Solution explanation

The TreeMap finds the right band in O(log b) per parcel, and the bands don't even need to be given in order.

Show solution

import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int b = sc.nextInt();
        TreeMap<Integer, Integer> bands = new TreeMap<Integer, Integer>();
        for (int i = 0; i < b; i++) bands.put(sc.nextInt(), sc.nextInt());
        int q = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            Map.Entry<Integer, Integer> e = bands.floorEntry(sc.nextInt());
            sb.append(e == null ? "no band" : String.valueOf(e.getValue())).append('\n');
        }
        System.out.print(sb);
    }
}

Output

Answer