E. 断层

很久很久以前，一个叫做 IOI 的先进文明蓬勃发展。时过境迁，现代考古学家 JOI 博士决定挖掘 IOI 文明遗址。

IOI 文明沿着笔直的河流发展。方便起见，IOI 文明遗址可以看作平面直角坐标系的 x 轴，而 y 轴表示海拔。IOI 文明地面平坦，也就是说，直线 代表地面，而 代表地面上空， 代表地下。另外，由于流水堆积，IOI 文明的地面一直在缓慢升高。IOI 文明灭亡前 年 () 时，直线 才是地平面。 IOI 文明灭亡后，它脚下的地层发生了 次运动。第 次运动 () 可用位置 ，方向 和变化量 描述。 为 或 。具体来说:

：断层视为一条过 ，斜率为 的直线,该直线只会穿过整点（即一格地层的两端），不会从一格地层的中间穿过从而把这格地层斩断。断层上方的地层斜向上移动，横坐标增加 ，纵坐标增加 。也就是说，直线上方的所有点 移动到 。

：断层视为一条过 ，斜率为 的直线,该直线只会穿过整点。断层上方的地层斜向上移动，横坐标减少 ，纵坐标增加 。也就是说，直线上方的所有点 移动到 。 每次地壳运动后， 的地层都会因风化作用而消失。

试求：对于每一个 ， 和 之间的地层是在 IOI 文明灭亡前哪一年的地层。

推荐查看样例 1 解释中的图片

第一行有两个整数 ，，用空格分隔。

在接下来的 行中，第 行 有三个整数 , , 用空格分隔。

输入的所有数的含义见题目描述。

输出共 行，第 行 有一个整数，表示点 和 点 之间的地层是在 IOI 文明灭亡前哪一年的地层。

样例输入 1

10 2
12 1 3
2 2 2

样例输出 1

3
3
5
5
5
5
5
5
2
2

样例 1 的解释图片：

https://www.z4a.net/images/2018/02/09/0fe14625e2fb78233cfd864dde8e1eda.png

样例输入 2

10 6
14 1 1
17 1 1
-6 2 1
3 2 1
4 1 1
0 2 1

样例输出 2

5
5
4
5
5
5
5
5
4
4

样例输入 3

15 10
28 1 7
-24 2 1
1 1 1
8 1 1
6 2 1
20 1 3
12 2 2
-10 1 3
7 2 1
5 1 2

样例输出 3

15
14
14
14
14
12
12
12
12
12
12
12
15
15
12

对于所有数据，, , 或 , 。