【问题描述】
𝑛辆车在一条数轴上，车的编号为1到𝑛。编号为𝑖的车坐标为𝑎[𝑖]，初始方向为𝑑𝑖𝑟[𝑖]（左或右），初始位置两两不同。每辆车每个时刻行走距离为1。两辆车相碰时，会调转方向，继续行走，掉头不消耗时间。现在车子开始朝其方向行驶，同一个坐标允许有多辆车。现在有𝑞个询问，给出𝑡,𝑖，询问过了𝑡时刻后，编号为𝑖的车的坐标的绝对值。
【输入格式】
输入文件名为collision.in。
首先输入𝑛,𝑞。
接下来𝑛行，每行两个整数𝑎[𝑖],𝑑𝑖𝑟[𝑖]，若𝑑𝑖𝑟[𝑖]=0，表示车子向左行走，若𝑑𝑖𝑟[𝑖]=1，表示车子向右行走。
接下来𝑞行，每行两个整数𝑡,𝑖，询问时刻𝑡时编号为𝑖的车的坐标。
【输出格式】
输出文件名为collision.out。
对于每个询问，输出一个整数，代表编号为𝑖的车的坐标。
【输入输出样例1】
collision.in
5 5
1 1
4 1
2 0
7 1
11 0
5 1
10 2
7 3
8 4
20 5
collision.out
3
1
8
12
27
【输入输出样例2】
collision.in
20 15
31116973 1
721410312 0
152891538 1
55434456 0
903968 1
34492580 0
97565125 0
78559065 1
191708700 0
335941230 0
526621966 1
168159348 1
457798506 1
160026937 1
76511872 1
247171016 1
48722268 0
159552820 0
701333640 0
434868520 1
143857480 13
821356724 11
132436670 1
20249229 11
504666 16
138701034 19
339607872 1
184664000 13
80827802 15
625365533 5
668115287 6
93821572 7
175176488 5
438184710 1
71279702 12

collision.out

25622049
38331852
977130985
662422758
171848754
220003868
5474029
533404717
11069472
1056101384
524968026
326917138
237940668
420617936
689224277
【数据规模与约定】
对于 30%的数据 ，max(𝑡)×𝑛≤107
另外有 30%的数据， 𝑛,𝑞≤1000
对于 100%的数据， 𝑛,𝑞≤100000,0≤𝑎[𝑖]≤109,𝑡≤109,𝑑𝑖𝑟[𝑖]∈{0,1}