class Result {
    static class CityCoordinate implements Comparable<CityCoordinate>{
        int coordinate;
        String cityname;

        public CityCoordinate(int c, String city) {
            this.coordinate = c;
            this.cityname = city;
        }

        @Override
        public int compareTo(CityCoordinate c) {
            return Integer.compare(this.coordinate, c.coordinate);
        }
    }

    public static List<String> closestStraightCity(List<String> c, List<Integer> x, List<Integer> y, List<String> queries) {
        Map<String, int[]> cities = new HashMap<>();
        Map<Integer, List<CityCoordinate>> xMap = new HashMap<>();
        Map<Integer, List<CityCoordinate>> yMap = new HashMap<>();

        int N = c.size();
        for(int i=0; i<N; i++) {
            List<CityCoordinate> xList = xMap.getOrDefault(x.get(i), new ArrayList<>());
            xList.add(new CityCoordinate(y.get(i), c.get(i)));
            xMap.put(x.get(i), xList);

            List<CityCoordinate> yList = yMap.getOrDefault(y.get(i), new ArrayList<>());
            yList.add(new CityCoordinate(x.get(i), c.get(i)));
            yMap.put(y.get(i), yList);

            cities.put(c.get(i), new int[] {x.get(i), y.get(i)});
        }

        // For each x coordinate, sort the corresponding list of cities on y coordinate
        for(int xCoodinate : xMap.keySet()) {
            Collections.sort(xMap.get(xCoodinate));
        }

        // For each y coordinate, sort the corresponding list of cities on x coordinate
        for(int yCoodinate : yMap.keySet()) {
            Collections.sort(yMap.get(yCoodinate));
        }


        List<String> result = new ArrayList<>();
        for(String q : queries) {
            int[] location = cities.get(q);

            List<CityCoordinate> xList = xMap.get(location[0]);
            List<CityCoordinate> yList = yMap.get(location[1]);

            CityCoordinate closestX = getClosestCityOnAnAxis(xList, location[1], q);
            CityCoordinate closestY = getClosestCityOnAnAxis(yList, location[0], q);

            result.add(getClosestCity(closestX, closestY, location));
        }

        return result;
    }

    private static String getClosestCity(CityCoordinate xCity, CityCoordinate yCity, int[] location) {
        int manhattanDistance1 = Math.abs(location[0] - xCity.coordinate);
        int manhattanDistance2 = Math.abs(location[1] - yCity.coordinate);

        if(manhattanDistance1 < manhattanDistance2) {
            return xCity.cityname;
        } else if(manhattanDistance1 == manhattanDistance2) {
            return xCity.cityname.compareTo(yCity.cityname) < 0 ? xCity.cityname : yCity.cityname;
        } else {
            return yCity.cityname;
        }
    }

    private static CityCoordinate getClosestCityOnAnAxis(List<CityCoordinate> list, int location, String city) {
        int index = Collections.binarySearch(list, new CityCoordinate(location, city));
        CityCoordinate leftCity = null, rightCity = null;
        int leftDist = Integer.MAX_VALUE, rightDist = Integer.MAX_VALUE;

        if(index > 0) {
            leftCity = list.get(index - 1);
            leftDist = Math.abs(leftCity.coordinate - location);
        }

        if(index < list.size() - 1) {
            rightCity = list.get(index + 1);
            rightDist = Math.abs(rightCity.coordinate - location);
        }

        if(leftDist < rightDist) {
            return leftCity;
        } else if(leftDist == rightDist) {
            return leftCity.cityname.compareTo(rightCity.cityname) < 0 ? leftCity : rightCity;
        } else {
            return rightCity;
        }
    }
}