【题目描述】

学校可以用一个无限大的平面来描述。学校里有 $n$ 个人，第 $i$ 个人位于 $(x_i,y_i)$，期望送达时间为 $t_i$。所有人的位置互不相同，且都不在原点 $(0,0)$。

时刻 $0$，一个机器人在原点领取了 $n$ 份餐品，第 $i$ 份餐品需要送给第 $i$ 个人。

接下来，机器人按照顺序执行 $m$ 条移动指令。第 $j$ 条指令让它向指定方向移动 $d_j$ 个单位。机器人每移动一个单位需要花费一个单位时间，执行相邻两条指令之间不会停留。

四个方向分别用以下字符表示：

• N：向北移动，即纵坐标增大；
• S：向南移动，即纵坐标减小；
• W：向西移动，即横坐标减小；
• E：向东移动，即横坐标增大。

坐标 $(x,y)$ 中，第一个数 $x$ 是横坐标，第二个数 $y$ 是纵坐标。例如，机器人从 $(2,3)$ 出发，向四个方向移动 $4$ 个单位后的位置分别为：

• 向北移动到 $(2,7)$，第二个数增加 $4$；
• 向南移动到 $(2,-1)$，第二个数减少 $4$；
• 向西移动到 $(-2,3)$，第一个数减少 $4$；
• 向东移动到 $(6,3)$，第一个数增加 $4$。

以上四种情况均以 $(2,3)$ 为出发位置，分别独立计算。

机器人严格按照编号从小到大的顺序送餐。当机器人到达某个人的位置时，只有这个人是当前尚未收到餐品的人中编号最小的，机器人才能将餐品交给他；否则，机器人直接经过，不会送餐。送餐不消耗时间，也不会改变机器人接下来的移动路线。

对于第 $i$ 个人，设他收到餐品的时刻为 $s_i$，在此之前机器人到达过他所在位置的次数为 $c_i$。他的不满意度按以下规则计算：

• 如果收到了餐品，且 $s_i\le t_i$，不满意度为 $c_i$；
• 如果收到了餐品，且 $s_i>t_i$，不满意度为 $(c_i+1)\times(s_i-t_i)$；
• 如果执行完全部 $m$ 条指令后仍未收到餐品，不满意度为 $-1$。

一次移动途中到达某个人的位置，或恰好在一条指令结束时到达该位置，都需要进行送餐判定。相邻两条指令的衔接处只算一次到达，不会因为开始执行下一条指令而重复计数。送餐当次的到达不计入 $c_i$，送餐后的到达也不会改变这个人的不满意度。

请你计算每个人最终的不满意度。

【输入描述】

第一行输入两个整数 $n,m$，分别表示人数和移动指令数。

接下来 $n$ 行，第 $i$ 行输入三个整数 $x_i,y_i,t_i$，分别表示第 $i$ 个人的位置和期望送达时间。

接下来 $m$ 行，第 $j$ 行输入一个字符 $o_j$ 和一个整数 $d_j$，表示机器人向 $o_j$ 指定的方向移动 $d_j$ 个单位。

保证：

• $1\le n\le 300$，$1\le m\le 10000$；
• $1\le d_j\le 100000$；
• $1\le t_i\le 10^9$；
• $|x_i|,|y_i|\le 10^6$；
• 所有人的位置互不相同，且 $(x_i,y_i)\ne(0,0)$；
• $o_j$ 为 N、S、W、E 中的一个。

【输出描述】

输出 $n$ 行，第 $i$ 行输出一个整数，表示第 $i$ 个人最终的不满意度。

【样例 1】

【样例 1 输入】

5 5
3 0 3
1 0 5
1 2 8
2 0 10
0 -1 20
E 3
W 4
N 2
E 3
S 2

【样例 1 输出】

0
1
3
12
-1

【样例 1 解释】

• 时刻 $1$ 和 $2$，机器人依次经过第 $2$ 个人和第 $4$ 个人的位置。此时第 $1$ 个人还未收到餐品，因此这两次都不送餐。
• 时刻 $3$，机器人到达 $(3,0)$，给第 $1$ 个人送餐，恰好在期望时间送达。他此前没有被经过，不满意度为 $0$。
• 机器人向西移动，时刻 $4$ 再次经过第 $4$ 个人的位置，仍不送餐；时刻 $5$ 到达 $(1,0)$，给第 $2$ 个人送餐。他此前被经过 $1$ 次，且没有超时，不满意度为 $1$。
• 时刻 $7$，机器人到达 $(-1,0)$；随后向北移动，在时刻 $9$ 到达 $(-1,2)$；再向东移动，在时刻 $11$ 到达 $(1,2)$，给第 $3$ 个人送餐。他此前没有被经过，超时 $11-8=3$ 个单位时间，不满意度为 $(0+1)\times 3=3$。
• 时刻 $12$，机器人到达 $(2,2)$，随后向南移动，在时刻 $14$ 到达 $(2,0)$，给第 $4$ 个人送餐。他此前被经过 $2$ 次，超时 $14-10=4$ 个单位时间，不满意度为 $(2+1)\times 4=12$。
• 全部指令执行完后，第 $5$ 个人仍未收到餐品，不满意度为 $-1$。

【样例 2】

【样例 2 输入】

9 12
4 3 6
-2 -1 17
0 1 30
0 -2 40
2 0 35
4 0 40
-1 0 46
1 0 42
3 2 100
E 4
N 3
W 6
S 5
E 5
N 4
W 3
S 4
N 2
E 4
W 6
E 3

【样例 2 输出】

1
0
1
1
6
1
0
28
-1

【数据规模与约定】

对于所有测试数据，均满足【输入描述】中的保证。