static void beike1() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        Map<String, Integer> countMap = new HashMap<>(), priceMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String s = scanner.next();
            int price = scanner.nextInt(), count = scanner.nextInt();
            countMap.put(s, count);
            priceMap.put(s, price);
        }
        int ans = 0;
        for (int i = 0; i < m; i++) {
            String s = scanner.next();
            int count = scanner.nextInt();
            ans += count * priceMap.get(s);
            count = countMap.get(s) - count;
            if (count < 0) {
                ans = -(i + 1);
                break;
            }
            countMap.put(s, count);
        }
        System.out.println(ans);
    }

static void beike2() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] f = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = scanner.nextInt();
        }
        Arrays.sort(f);
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int ans = 0;
        for (int i = n - 1; i > -1; i--) {
            Integer key = map.higherKey(f[i]);
            if (key == null) {
                ans++;
                map.put(f[i], map.getOrDefault(f[i], 0) + 1);
                continue;
            }
            int val = map.get(key) - 1;
            if (val == 0) {
                map.remove(key);
            } else {
                map.put(key, val);
            }
            map.put(f[i], map.getOrDefault(f[i], 0) + 1);
        }
        System.out.println(ans);
    }

   static void beike3() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), k = scanner.nextInt();
        int[] f = new int[n];
        for (int i = 0; i < n; i++) {
            f[i] = scanner.nextInt();
        }

        int ans = 0;
        int cur = 0, l = 0;
        for (int i = 0; i < n; i++) {
            cur = 0;
            for (int j = i; j < n; j++) {
                cur += f[j] > k ? 1 : -1;
                ans = Math.max(ans, cur > 0 ? j - i + 1 : 0);
            }
        }
        System.out.println(ans);
    }

    static void beike4() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), q = scanner.nextInt();
        long[] f = new long[n], pre = new long[n];
        Map<Integer, Map<Integer, Integer>> memo = new HashMap<>();
        for (int i = 0; i < n; i++) {
            f[i] = scanner.nextInt();
            memo.put(i, new HashMap<>());
        }

        Arrays.sort(f);
        for (int i = 0; i < n; i++) {
            pre[i] += f[i];
            pre[i] += i - 1 >= 0 ? pre[i - 1] : 0;

        }
//        SegmentTree segmentTree = new SegmentTree(f);
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{0, f.length - 1});
        Set<Long> set = new HashSet<>();
        set.add(0L);
        while (queue.size() > 0) {
            int[] a = queue.poll();
            int l = a[0], r = a[1];
            long sum = getSum(pre, l, r);
            set.add(sum);

            long avg = sum / (r - l + 1);
            if (f[l] == avg && f[r] == avg) {
                continue;
            }
            int idx = upperBound(f, avg, l, r);
            if (memo.get(l).get(idx) == null) {
                queue.add(new int[]{l, idx});
                memo.get(l).put(idx, 0);
            }
            if (memo.get(idx + 1).get(r) == null) {
//                queue.add(new int[]{l,
                queue.add(new int[]{idx + 1, r});
                memo.get(idx + 1).put(r, 0);

            }
        }

//        System.out.println(set.size());

        for (int i = 0; i < q; i++) {
            long num = scanner.nextInt();
            System.out.println(set.contains(num) ? "YES" : "NO");
        }
    }

    static long getSum(long[] f, int l, int r) {
        return l == 0 ? f[r] : f[r] - f[l-1];
    }


    static int upperBound(long[] f, long num, int l, int r) {
//        int l = 0, r = f.length - 1;
        while (l < r - 1) {
            int mid = (l + r) / 2;
            if (f[mid] <= num) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        if (f[l+1] <= num) {
            l++;
        }
        return l;
    }