配点: 3 点
問題文
ABC 竞技编程补习班有 N 个班级,编号为 i (1 \leq i \leq N) 的班级面向评级为 A_i 的学生。
今、Q 名学生想要加入这个补习班。 编号为 j (1 \leq j \leq Q) 的学生的评级是 B_j 。 每个学生如果上不适合自己水平的班级会感到不满。 对于每个学生,不満度定义如下。
- 目标评分 a 与自己的评分 b 的差的绝对值,也就是说 |a-b|
j=1,2,3,\ldots,Q 对于每个,求编号 j 学生的不满度可能的最小值。 但是,1 可以存在没有人的班级,也可以存在由多个人组成的班级。
制約
- 1\leq N \leq 300000
- 1\leq Q \leq 300000
- 0\leq A_i \leq 10^9
- 0\leq B_j \leq 10^9
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N A_1 A_2 A_3 \cdots A_N Q B_1 B_2 B_3 \vdots B_Q
出力
j=1,2,3,\ldots,Q 关于每一项,请将答案逐行输出到标准输出,总计 Q 行输出。
入力例 1
4 4000 4400 5000 3200 3 3312 2992 4229
出力例 1
112 208 171
入力例 2
1 4000 10 3582 3538 3320 3312 3296 3257 3111 3040 3013 2994
出力例 2
418 462 680 688 704 743 889 960 987 1006
入力例 3
10 869120000 998244353 777777777 123456789 100100100 464646464 987654321 252525252 869120001 1000000000 10 4229 20210406 1 268435456 3582 536870912 1000000000 869120 99999999 869120001
出力例 3
100095871 79889694 100100099 15910204 100096518 72224448 0 99230980 100101 0
入力例 4
100 298750376 229032640 602876667 944779015 909539868 533609371 231368330 445484152 408704870 850216874 349286798 30417810 807260002 554049450 40706045 380488344 749325840 801881841 459457853 66691229 5235900 8100458 46697277 997429858 827651689 790051948 981897272 271364774 536232393 997361572 449659237 602191750 294800444 346669663 792837293 277667068 997282249 468293808 444906878 702693341 894286137 845317003 27053625 926547765 739689211 447395911 902031510 326127348 582956343 842918193 235655766 844300842 438389323 406413067 862896425 464876303 68833418 76340212 911399808 745744264 551223563 854507876 196296968 52144186 431165823 275217640 424495332 847375861 337078801 83054466 648322745 694789156 301518763 319851750 432518459 772897937 630628124 581390864 313132255 350770227 642944345 677742851 448945480 688009163 160941957 290297295 5532462 823543277 19634445 15791361 193309093 66202596 72364149 743270896 297240520 264035189 898589962 59916738 307942952 403411309 30 930579110 22697034 44652533 280533771 753567118 684927419 923477579 557613803 779616458 389130756 323671659 3117850 408004003 224808850 18421958 359047808 364572866 334631363 854759331 647435074 826055423 668443532 620408208 32237184 67299071 251185742 217292659 16181227 850865411 218577687
出力例 4
4031345 3062589 2044744 2866703 4241278 3081744 3070186 3564353 6718521 8642412 2455689 2118050 700867 4223790 1212487 8277581 13802639 2447438 251455 887671 1596266 9299319 10219916 1819374 607842 12849447 11739981 389866 648537 10454953