Description

油城西是一個毒瘤

身為一個毒瘤，他自然有很多難題可以砸人

現在他有 $n$ 個題庫，其中第 $i$ 個題庫包含了 $[l_{i}, r_{i}]$ 間所有整數難度的題目各一題

而現在也有 $q$ 個人依序想被題目砸

其中第 $i$ 個人的實力值為 $s_{i}$

若一道題目的難度為 $x$ ，則我們定義該題目和第 $i$ 個人的適合度為 $| x - s_{i} |$

而每個人都會被分配到目前和他最適合的題目（也就是適合度數值最低的題目）

若有兩題的合適度相同，則油城西會拿比較難的題目砸他

同時為了避免題目慘遭外流

一道題目只要分配給一個人後就不能再分給別人了

請依序輸出每個人被分到的題目難度為多少

Input Format

$n$

$l_{1}$ $r_{1}$

$. . .$

$l_{n}$ $r_{n}$

$q$

$s_{1}$

$. . .$

$s_{q}$

Input Limits:

$n, q \leq 10^{6}$

$1 \leq l_{1} \leq r_{1} < l_{2} \leq r_{2} < . . . < l_{n} \leq r_{n} \leq 10^{18}$

$\forall i, s_{i} \leq 10^{18}$

$q \leq \sum_{i = 1}^{n} r_{i} - l_{i} + 1$

所有輸入均為正整數

Output Format

輸出 $q$ 行正整數

Sample Input 1

Sample Output 1

Hints

Subtasks

No.	Testdata Range	Score

TopCoder

justinlin

只會寫 $l o w$ 題

User's AC Ratio

60.0% (3/5)

Problem Source

Google Kickstart 2021 Round D

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Memory Limit (RSS, KiB)	Output Limit (KiB)
0	5000	250000	250000	65536
1	5000	250000	250000	65536
2	5000	250000	250000	65536
3	5000	250000	250000	65536
4	5000	250000	250000	65536
5	5000	250000	250000	65536
6	5000	250000	250000	65536
7	5000	250000	250000	65536
8	5000	250000	250000	65536
9	5000	250000	250000	65536
10	5000	250000	250000	65536
11	5000	250000	250000	65536
12	5000	250000	250000	65536

4454 . 油城西和他的難題庫

Description

Input Format

Output Format

Sample Input 1

Sample Output 1

Hints

Subtasks

TopCoder

User's AC Ratio

Tags

Problem Source

Testdata and Limits

4454 . 油城西和他的難題庫

Description

Input Format

Output Format

Sample Input 1

Sample Output 1

Hints

Subtasks

TopCoder

User's AC Ratio

Tags Show solution-related tags

Problem Source

Testdata and Limits

Tags