题目描述

在准备面向中学生的闭门编程奥林匹克竞赛的过程中，组织者决定装饰礼堂。为此，他们在墙上沿着一条直线钉上了 $2n$ 个木桩。所有木桩均位于不同的位置。在它们之间，拉起了 $n$ 条绳子，其中第 $i$ 条绳子拉在距离墙的起点分别为 $l_i$ 和 $r_i$ 的两个木桩之间（$l_i < r_i$）。已知每个木桩上恰好系有一条绳子。

这些绳子可以进行一种称为 重系 的操作。在一次 重系 操作中，你可以选择两条绳子 $(l_i, r_i)$ 和 $(l_j, r_j)$，将它们从木桩上解下，然后用这四个释放出来的木桩恰好各一次地挂上两条新绳子。也就是说，从这四个释放的木桩中，形成两个新的配对，并在它们之间拉上新绳子。

如果线段 $[l_i, r_i]$ 与 $[l_j, r_j]$ 至少有一个公共点，则称拉在木桩 $(l_i, r_i)$ 和 $(l_j, r_j)$ 之间的绳子相交。如果存在一个包含 $k$ 条绳子的集合，其中的绳子两两相交，则称一个绳子配置的 美观度 至少为 $k$。注意，如果一个配置的美观度为 $k$，那么它的美观度也至少为 $k - 1,\ k - 2,\ \ldots,\ 0$。

奥林匹克竞赛的组织者有 $q$ 个查询，希望通过若干次 重系 操作来得到具有特定美观度的配置。在第 $i$ 个查询中，他们希望达到至少为 $k_i$ 的美观度。对于每个查询，组织者希望知道所需的最少 重系 操作次数。这些查询之间相互独立，这意味着查询之间的 重系 操作不会被保留。

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le q \le n \le 200\,000$）—— 绳子的数量以及查询的数量。

接下来的 $n$ 行描述绳子。第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i < r_i \le 10^9$）—— 第 $i$ 条绳子所连接的木桩的编号。保证每个木桩恰好出现一次。

再接下来一行包含 $q$ 个整数 $k_1$, $k_2$, $\ldots$, $k_q$（$1 \le k_i \le n$）—— 组织者查询中所期望的美观度大小。保证所有 $k_i$ 互不相同。

输出格式

对于每个查询，输出一个非负整数 —— 为得到查询中所要求美观度的绳子配置，所需执行的最少 重系 操作次数。

保证对于每个查询，都可以通过执行若干次 重系 来达到所要求美观度的配置。

6 6
25 30
15 29
7 12
8 14
4 5
16 23
1 2 3 4 5 6

0 0 1 1 2 3

提示

样例解释

在第一个例子中，绳子的初始配置如下：

:::align{center} :::

由于绳子 3 和 4 已经相交，要达到美观度至少为 $1$ 和至少为 $2$ 不需要任何操作。

要达到美观度 $3$ 和 $4$，你可以对绳子 2 和 5 执行一次 重系 操作，得到绳子 $(4, 29)$ 和 $(5, 15)$。

:::align{center} :::

要达到美观度 $5$，你可以再对绳子 3 和 6 进行一次操作，得到 $(7, 16)$ 和 $(12, 23)$。

:::align{center} :::

要使所有 6 条绳子都相交，你可以对绳子 1 和 5、2 和 3、4 和 6 进行操作，得到如下配置：

:::align{center} :::

计分

本题的测试数据分为 6 组。每组仅在通过该组内全部测试以及此前某些组的全部测试后，才能获得分数。注意，某些组不要求通过题面中的样例。

翻译由 DeepSeek V4 Pro 完成