#P18504. Festival Decorating
Festival Decorating
Festival Decorating
为了庆祝即将到来的冬季节日,Byteland 的主街(可看作 轴)上布置了 盏彩灯,编号依次为 。第 盏灯的坐标为 ,颜色为 。任意两盏灯的坐标不同。
你需要回答 个询问。第 个询问给出整数 :找出编号最小的灯 ,使得坐标 处存在另一盏灯,且那盏灯的颜色与 不同。如果不存在这样的 ,则答案为 。
答案允许有不超过 的绝对或相对误差。具体判定方式见输出格式。
输入格式
第一行包含两个整数 (),表示灯的数量和询问数量。
随后 行,第 行包含两个整数 (,),表示第 盏灯的坐标与颜色。保证所有 两两不同。灯的编号由输入顺序确定,坐标不保证有序。
随后 行,第 行包含一个整数 ()。
输出格式
每个询问输出一行,包含一个数:你找到的最小编号 ;若无法找到,则输出 。
你可以输出非整数。设输出为 ,精确标准答案为 ,当且仅当下式成立时,该询问被接受:
每个询问都必须满足这个条件。例如,精确答案为正整数 时,整个区间 都合法;精确答案为 时, 都合法。交付判题器严格使用原公式,不额外要求输出为整数。
原样例
4 5
3 1
1 2
5 1
6 2
1
2
3
4
5
3
2
1
2
0