#3141. [Hnoi2013]旅行

内存限制:128 MiB 时间限制:10 Sec

题目描述

输入格式

第一行为两个空格隔开的正整数n, m,表示旅行的城市数与旅行所花的月数。接下来n行,其中第 i行包含两个空格隔开的整数Ai和Bi,Ai表示他第i个去的城市编号。Bi为0或1;如果Bi=0则表示城市Ai没有小L想去的景点,如果Bi=1则表示城市Ai有小L想去的景点,
Ai两两不同且有1<=Ai<=N,即{Ai}为1,2....N的一个排列。
例如{2,1,3,4...N}
N<=500000,M<=200000

输出格式

t仅包括一行,包含m个空格隔开的正整数X1,X2...Xm,t仅包括一行,包含m个空格隔开的正整数X1,X2...Xm,为给小L安排的旅行计划对应的路线。为给小L安排的旅行计划对应的路线。

样例

样例输入


			
8 3
2 0
3 1
4 1
1 0
5 0
6 1
7 1
8 0

样例输出


			
1 6 8

数据范围与提示

1个月得到2点快乐值与2点疲劳值,第2个月得到1点快乐值与1点疲劳值,第3 个月得到1点快乐值与1点疲劳值。3个月中疲劳值与快乐值差的最大值为0,达到所有方 案最小值。


可行方案有:


1  6 8


3  6 8


3  1 8


其中1 6 8字典序最小。