P16369 [OOI 2026] Decoration

During the preparation for the Closed Olympiad of School Students in Programming, the organizers decided to decorate the auditorium. For this purpose, $2n$ pegs were hammered into a straight line on the wall. All pegs are in different positions. Between them, $n$ strings were stretched, the $i$-th of which was stretched between the pegs at distances $l_i$ and $r_i$ from the start of the wall ($l_i < r_i$). It is known that each peg has exactly one string stretched to it. The strings can undergo operations called $\textit{restringing}$. In one $\textit{restringing}$ operation, you can choose two strings $(l_i, r_i)$ and $(l_j, r_j)$, remove them from the pegs, and then hang two new strings, using each of the four freed pegs exactly once. That is, from the four freed pegs, two new pairs are formed, between which new strings are stretched. The strings stretched between the pegs $(l_i, r_i)$ and $(l_j, r_j)$ intersect if the segments $[l_i, r_i]$ and $[l_j, r_j]$ have at least one common point. A configuration of strings is considered to have beauty at least $k$ if there exists a set of $k$ strings, each pair of which intersects. Note that if a configuration has beauty $k$, it also has beauty at least $k - 1,\ k - 2,\ \ldots,\ 0$. The organizers of the Olympiad have $q$ queries for obtaining a configuration of a certain beauty as a result of several $\textit{restringing}$ operations. In the $i$-th query, they would like to achieve beauty at least $k_i$. For each query, the organizers want to know the minimum number of $\textit{restringing}$ operations required to achieve this. The queries are independent of each other, meaning that the $\textit{restringing}$ operations between queries are not preserved.

The first line contains two integers $n$ and $q$ ($1 \le q \le n \le 200\,000$) --- the number of strings and the number of queries. The next $n$ lines describe the strings. In the $i$-th line, there are two integers $l_i$ and $r_i$ ($1 \le l_i < r_i \le 10^9$) --- the numbers of the pegs connected by the $i$-th string. It is guaranteed that each peg appears exactly once. The next line contains $q$ integers $k_1$, $k_2$, $\ldots$, $k_q$ ($1 \le k_i \le n$) --- the desired beauty sizes in the queries from the organizers. It is guaranteed that all $k_i$ are distinct.

For each query, output a single non-negative integer --- the minimum number of $\textit{restringing}$ operations that need to be performed to obtain a configuration of strings with the required beauty as specified in the query. It is guaranteed that for each query, it is possible to perform several restringings to achieve a configuration of the required beauty.

### Note In the first example, the strings initially have the following configuration: :::align{center}  ::: Since strings 3 and 4 already intersect, no operations are needed to achieve beauty at least $1$ and beauty at least $2$. To achieve beauties $3$ and $4$, you can perform a $\textit{restringing}$ operation on strings 2 and 5 to obtain strings $(4, 29)$ and $(5, 15)$. :::align{center}  ::: To achieve beauty $5$, you can additionally perform an operation on strings 3 and 6 to obtain $(7, 16)$ and $(12, 23)$. :::align{center}  ::: To make all 6 strings intersect, you can perform operations on strings 1 and 5, 2 and 3, 4 and 6 to obtain the following configuration: :::align{center}  ::: ### Scoring The tests for this problem consist of six groups. Points for each group are awarded only if all tests of the group and all tests of some previous groups are passed. Note that passing the tests from the statement is not required for some groups. | Group | Points | Additional constraints | < | < | Required groups | Comment | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | $n$ | $q$ | $k_i$ | | | | $0$ | $0$ | -- | -- | -- | -- | Tests from the statement. | | $1$ | $14$ | $n \le 100$ | -- | -- | $0$ | -- | | $2$ | $16$ | $n \le 3000$ | -- | -- | $0, 1$ | -- | | $3$ | $13$ | -- | -- | -- | -- | Strings do not intersect pairwise. | | $4$ | $25$ | -- | $q=1$ | $k_i = n$ | -- | -- | | $5$ | $17$ | -- | $q=1$ | $k_i \le 10$ | -- | -- | | $6$ | $15$ | -- | -- | -- | $0$ -- $5$ | -- |