题目背景

孤帆远影碧空尽，唯见长江天际流。

问题描述

在江面上（可看作一维数轴，右边为正方向），有 \(n\) 条传信船，每一条船有自己的编号（从 \(1\) 到 \(n\) 且不重复），每一条传信船在单位时间内的速度为一，有向左和向右两种运动方向，当它遇到另一艘传信船时，它便会立刻掉转方向。

初始时给出每个船的编号，位置和方向。初始时间为 \(0\)。

现在有 \(m\) 次询问，每次询问形式为 \(x,t\)。表示询问编号为 \(x\) 的船在 \(t\) 时刻的位置。

输入格式

第一行，两个正整数 \(n，m\)。

以下 \(n\) 行，每行格式为 \(x_i,y_i,z_i\)。表示编号为 \(x_i\) 的船在初始时所处位置为 \(y_i\)，初始方向为 \(z_i\) （为 \(0\) 表示向左，为 \(1\) 表示向右）。
以下 \(m\) 行，每行表示一个询问包含两个正整数 \(x,t\)，意义参考题目描述。

输出格式

对于每个询问输出一行一个整数表示位置。

样例

样例输入 1

4 4
3 -1 0
4 -3 0
2 2 1
1 5 1
1 0
2 1
3 2
4 3

样例输出 1

5 
3
-3
-6

数据范围

\(100\%\) 的数据 保证读入和正确输出的所有数据的绝对值都小于 \(10^9\) 且为整数。
每一次询问的时间 \(t\) 为非负整数。任意 \(z_i\) 等于 \(0\) 或 \(1\)。

测试点编号	\(n,m,t\)
\(1-4 \)	\(n\le 100,m\le 100,\) 任意 \(t\le 100 \)
\(5-6 \)	\(n\le 1000,m\le 1000,\) 任意 \(t\le 1000 \)
\(7-10 \)	\(n\le 1000,m\le 1000 \)
\(11-20\)	\(n\le 100000,m\le 100000 \)

时空限制

\(2\mathrm s,512\mathrm{MiB}\)