Processing math: 100%
编程题
                ### 问题描述

小齐和小艾各自烤了 N 个派。每个派都有一个美味值,由小齐和小艾相互评价。

小齐考虑要把一个派送给小艾。如果小艾收到小齐的派,她会觉得有义务回赠一个派给小齐。为了既不显得吝啬又不过于奢侈,小艾会尝试挑选一个派,使其美味值至少与她所收到的派相同,但不超过 D

如果找不到这样的派,小艾会匿名化身并自我放逐到日本。

但是如果小艾确实回赠了一个派给小齐,小齐也会尝试给小艾一个派,使其美味值至少与小艾刚刚给她的派相同,但不超过 D(在小齐看来)。如果这是不可能的,小齐也会自我放逐。否则,她将把所选的派送给小艾。这个循环将继续,直到两头牛中的一头被放逐,这是不幸的结局,或者其中一头牛收到的派被评为 0,这时礼物交换将结束,两头牛都会很开心。

请对于小齐可能选择的每个派的初始礼物,确定在牛们开心的礼物交换中可能赠送的最小派数。

输入格式

第一行包含两个整数 ND

接下来的 2N 行,每行包含两个整数,分别表示小齐和小艾对某个派的美味值。

N 行表示小齐的派,后 N 行表示小艾的派。

输出格式

输出应有 N 行。第 i 行应包含一个整数:在以小齐的第 i 个派作为初始礼物的情况下,在礼物交换中可能赠送的最小派数。如果以第 i 个派为初始礼物的礼物交换不会让牛们开心,则第 i 行应包含整数 1

样例输入

2 1
1 1
5 0
4 2
1 4

样例输出

3
1

评测数据规模

1N1050D109

查看答案
赣ICP备20007335号-2