#P18504. Festival Decorating

Festival Decorating

Festival Decorating

为了庆祝即将到来的冬季节日,Byteland 的主街(可看作 xx 轴)上布置了 nn 盏彩灯,编号依次为 1,2,…,n1,2,\ldots,n。第 ii 盏灯的坐标为 xix_i,颜色为 cic_i。任意两盏灯的坐标不同。

你需要回答 qq 个询问。第 ii 个询问给出整数 did_i:找出编号最小的灯 uu,使得坐标 xu+dix_u+d_i 处存在另一盏灯,且那盏灯的颜色与 cuc_u 不同。如果不存在这样的 uu,则答案为 00。

答案允许有不超过 0.50.5 的绝对或相对误差。具体判定方式见输出格式。

输入格式

第一行包含两个整数 n,qn,q(1≤n,q≤2500001\le n,q\le250000),表示灯的数量和询问数量。

随后 nn 行,第 ii 行包含两个整数 xi,cix_i,c_i(1≤xi≤2500001\le x_i\le250000,1≤ci≤n1\le c_i\le n),表示第 ii 盏灯的坐标与颜色。保证所有 xix_i 两两不同。灯的编号由输入顺序确定,坐标不保证有序。

随后 qq 行,第 ii 行包含一个整数 did_i(1≤di≤2500001\le d_i\le250000)。

输出格式

每个询问输出一行,包含一个数:你找到的最小编号 uu;若无法找到,则输出 00。

你可以输出非整数。设输出为 uu,精确标准答案为 u′u',当且仅当下式成立时,该询问被接受:

∣u−u′∣max⁡(1,∣u′∣)≤0.5.\frac{|u-u'|}{\max(1,|u'|)}\le0.5.

每个询问都必须满足这个条件。例如,精确答案为正整数 bb 时,整个区间 [b/2,3b/2][b/2,3b/2] 都合法;精确答案为 00 时,[−0.5,0.5][-0.5,0.5] 都合法。交付判题器严格使用原公式,不额外要求输出为整数。

原样例

4 5
3 1
1 2
5 1
6 2
1
2
3
4
5
3
2
1
2
0