题目描述

出完题目，blg 觉得贪吃蛇挺好玩，于是赶在关门前又回到嘉年华。这次，他看到一台大人版贪吃蛇便又开始玩了起来，每一个时刻，贪吃蛇会按照指令进行移动。

• w-表示向上走
• a-表示向左走
• s-表示向下走
• d-表示向右走

贪吃蛇的移动范围的横纵坐标都是 $-1000$ 至 $+1000$，开始位置在 $(0,0)$。也就是如果贪吃蛇某一时刻的横坐标或纵坐标的绝对值大于 $100$ ，游戏就结束了。

与幼儿版相比，大人版贪吃蛇可以真的吃豆了。但是很显然，豆子不是一开始就在游戏里的，会在某个时刻 $t$ 出现在某个位置 $p$，如果蛇头到达 $p$ 位置的时刻豆子已经出现或者刚好出现（天选之蛇），则贪吃蛇会吃下这颗豆子。

相应的，每吃一个豆之后会变长一个单位，具体实现方案为头部移动到新位置后，脖子的原位置变为身体，身体其他位置不动，从而使得总长度增加一个单位。见示意图。

很显然，现在可能撞上自己造成死亡。现在给你 blg 的操作序列，每一个时间单位贪吃蛇按照操作序列移动一格，请问他控制的贪吃蛇的最终长度。初始长度为 1，初始时刻为 0。

注意：

• 每颗豆子被吃掉之后就消失了。豆子如果出现在蛇身子上则不会吃掉。比如 $0$ 时刻时蛇头在 $(0,0)$ 位置，$1$ 时刻到达 $(1,0)$ 位置，则 $1$ 时刻出现在 $(1,0)$ 的豆子会被吃到（天选），而 $2$ 时刻才出现在 $(1,0)$ 的豆子不会被吃到。
• 如果蛇头的下一步位置正好是当前的蛇尾（蛇的最后一格），则此时如果蛇尾会让出位置（即蛇头不会吃到豆子从而造成蛇尾不动），则蛇继续存活。
• 如果某个位置 $p$ 已经有一颗豆子，且还未被贪吃蛇吃下，而此时系统又要在 $p$ 位置产生一颗豆子，则此时产生豆子的指令将被跳过。即任意时刻每个位置只会有一个豆子，且蛇每一时刻也只可能吃下一个豆子。
• 贪吃蛇的头跑到绝对值超过 $1000$ 的位置也会结束游戏。
• 题目保证不会出现直接转身180度的情况，即不会有 ws、sw、ad、da 这样的子操作序列。

输入格式

第一行是一个字符串 $s$，表示 blg 的操作序列。

第二行是一个整数 $n$，表示有 $n$ 个豆子要出现。

接下来 $n$ 行每行三个整数$x_i,y_i,t_i$，表示第 $i$ 个豆子将在第 $t_i$ 时刻出现在 $x_i,y_i$ 位置。这里 $x_i$ 为正时表示在原点右侧，$y_i$ 为正时表示原点上部。注意 $x,y$ 的方向与贪吃蛇Ⅰ有所不同。

豆子按照出现顺序给出，即后出现的豆子一定会在后面给出。

输出格式

对每个测试数据，输出一个数字，表示操作完成时，贪吃蛇的长度。

测试样例

wwwww
4
0 1 1
0 2 2
0 3 3
0 4 4

5

连吃4个，长度为5。

wdsawww
4
0 1 1
1 1 1
1 0 1
0 2 3

5

吃了一圈，注意第四步尾巴刚好让出位置。

wwwwwww
6
0 1 1
0 2 1
0 3 1
0 3 2
0 5 4
0 5 5

5

注意(0,3)处只有1个豆子。

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

6

注意贪吃蛇吃最后一个豆子前已经死了。

数据规模说明

对 $100\%$ 数据，$s$ 的长度不超过 $10^6$，$1≤n≤2×10^5$，$-1000≤x_i,y_i≤1000$，$1≤t_i≤10^6$。