在为“封闭式编程奥林匹克竞赛”做准备期间，组织者决定装饰礼堂。为此，他们在墙上的一条直线上钉了 $2n$ 个钉子。所有钉子的位置各不相同。在这些钉子之间拉了 $n$ 根弦，其中第 $i$ 根弦连接距离墙起点分别为 $l_i$ 和 $r_i$ 的钉子（$l_i < r_i$）。已知每个钉子上恰好连接有一根弦。

弦可以进行一种称为“重连”（restringing）的操作。在一次重连操作中，你可以选择两根弦 $(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, \dots, 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, \dots, k_q$ ($1 \le k_i \le n$)，表示组织者查询中期望的美观度大小。保证所有 $k_i$ 互不相同。

输出格式

对于每个查询，输出一个非负整数，表示为了获得查询中指定的美观度配置所需执行的最少重连操作次数。输出结果需对 $12569$ 取模。

保证对于每个查询，都可以通过若干次重连操作达到所需的美观度。

样例

输入格式 1

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

输出格式 1

0 0 1 1 2 3

说明

在第一个样例中，弦的初始配置如下：

由于弦 3 和弦 4 已经相交，因此不需要任何操作即可达到至少 1 和至少 2 的美观度。

为了达到美观度 3 和 4，你可以对弦 2 和弦 5 执行一次重连操作，得到弦 $(4, 29)$ 和 $(5, 15)$。

为了达到美观度 5，你可以额外对弦 3 和弦 6 执行一次操作，得到 $(7, 16)$ 和 $(12, 23)$。

为了使所有 6 根弦都相交，你可以对弦 1 和弦 5、弦 2 和弦 3、弦 4 和弦 6 执行操作，得到如下配置：

Scoring

| :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 组别 | 分数 | :---: | Additional constraints | :---: | 所需组别 | 说明 | | | | $n$ | $q$ | $k_i$ | | | | 0 | 0 | | | | | 样例测试 | | 1 | 14 | $n \le 100$ | | | 0 | | | 2 | 16 | $n \le 3000$ | | | 0, 1 | | | 3 | 13 | | | | | 弦不两两相交 | | 4 | 25 | | $q = 1$ | $k_i = n$ | | | | 5 | 17 | | $q = 1$ | $k_i \le 10$ | | | | 6 | 15 | | | | 0 - 5 | |