题目背景

赛时答疑

跑酷这东西，还是得看人品的（比如 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。

2
1 4 P
4 5 P

1

3
1 6 P
2 4 N
3 4 P

0

2
5 8 P
7 11 P

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$。

保证数据有一定梯度。