跑酷

题目背景

[赛时答疑](https://www.luogu.org/discuss/show/80694) 跑酷这东西,还是得看人品的(比如 zm 和 mt)…

题目描述

在 Minecraft 中,跑酷可以算得上是一门技术了,Steve 现在想在一个跑道上(二维)进行跑酷。但是 Steve 不知道能不能跑到终点,于是他便查询了 MC Wiki,来获得更多的知识。内容具体如下: ### 生命值 1. 我们规定每个玩家的初始生命为 $20$ 点。 2. 掉落伤害的计算: - 如果玩家的高度为 $3$ 格或以下,免除此伤害。 - 如果玩家的高度为 $4$ 格或以上,便会造成 $x-3$ 点伤害,$x$ 为摔落的高度。 - 这里的高度均指相对高度,即当前方块与下一个方块之间的高度差。 3. 掉落伤害降低的情况:见特殊方块。 4. 当生命值为 $0$ 的时候,视为不能到达终点。 ### 跑酷 1. 对于站在一个方块上的玩家来说,玩家最多可以往前面跳 $3$ 格并且可以往上跳一个格子。 2. 对于站在一个方块上的玩家来说,玩家最多也可以往前跳 $4$ 格,但是不能向上跳一个格子。 3. 为了计算方便,我们规定下落时玩家不会移动,也就是说,如果下一个方块比现在方块的高度要低的话,我们只能正好下落到下一个方块的位置。 4. 默认终点为最后一个方块。 ### 特殊方块 1. **粘液块**:会使你跳跃至 $60\%$ 坠落距离的高度,如果有小数,我们向下取整。当你达到最高点的时候,只能往前再移动一格。当然,如果落在前方的方块上,同样要受到摔落伤害。你也可以按住 Shift 键来免除反弹。我们认为在粘液块上面进行跑酷不受减速的限制。 2. **蜘蛛网**:下落时会让你免除伤害。我们也认为玩家在蜘蛛网上跑酷不受减速的限制。 Steve 找到了你,让你帮他去解决这个问题。判断 Steve 能不能到达终点。 - 如果能到达终点,输出最少的跳跃次数; - 如果不能到达终点,请输出:`qwq`。

输入输出格式

输入格式


第一行为一个整数 $n$,表示有 $n$ 个方块。 从第二行开始,下面连续 $n$ 行,表示有 $n$ 个方块。每个方块都有它的属性:横坐标,高度和是否为特殊方块。(普通方块输入为 $\verb!P!$,粘液块为 $\verb!N!$,蜘蛛网为 $\verb!Z!$)

输出格式


如果能到达终点,输出一个整数,表示最少的跳跃次数; 如果不能到达终点,请输出 `qwq`。

输入输出样例

输入样例 #1

2
1 4 P
4 5 P

输出样例 #1

1

输入样例 #2

3
1 6 P
2 4 N
3 4 P

输出样例 #2

0

输入样例 #3

2
5 8 P
7 11 P

输出样例 #3

qwq

说明

### 数据范围及约定 数据保证输入的横坐标单调递增。每一个横坐标只有一格方块。 数据保证不会在相邻的横坐标中间出现两个特殊方块。 对于方块而言,默认是都没有浮空方块的存在;也就是说,所有方块下面都会有支撑柱。 为了方便,不能先跳跃再下落。也就是说,只能下落到前面一格的方块。 对于 $30\%$ 的数据 $n\le 10$; 对于另外 $20\%$ 的数据,保证不存在特殊方块; 对于这前面的 $50\%$ 的数据,保证 Steve 往前跳只能跳四格远或者三格远一格高; 对于 $100\%$ 的数据 $1\le n\le 1000$,$1\le x_{\rm max}\le 10000$,$1\le height\le 1000$。 保证数据有一定梯度。