题目背景

Facer和教官关系很好（py交易）

被教官任命为副教官

题目描述

Facer训练一个N个人的队伍

每个人有一个智力值ai和体力值bi

Facer希望两个人组队，组队的两个人要尽量相似

具体来说，两个人的相似度cmp(i,j) =| ai - aj + bj - bi | + | ai - aj | cmp(i,j)越小表示越相似

现在本来有N个人，但是Facer想要再加入一个人

有M个候选人

Facer需要对每一个候选人找到组队的对象（即找到和他cmp最低的的本来就在队伍中的人），你需要输出每个人和队伍中的人最低的cmp，并输出它

输入格式

第一行N，M

接下来N行，每行两个数，表示本来就在队伍中的人的智力值ai,体力值bi

接下来M行

如果是 1 a b 表示队伍中新加入了一个人 ,智力a , 体力b

如果是2 a b表示有一个候选人，请找出和候选人最相似的队伍中的人

输出格式

对于每个候选人，输出他和本来就在队伍中的人的最低的cmp

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

3
1

提示

40% 1 <= N,M <= 1000

100% 1 <= N,M <= 100000

模板题