Problem Background

Parkour in Minecraft can be considered a skill. Steve wants to perform parkour on a two-dimensional track, but he is unsure if he can reach the end. Therefore, he consults the MC Wiki to gain more knowledge. The details are as follows:

Health Points

1. Each player starts with 20 health points.
2. Calculation of fall damage:
   - If the height is 3 blocks or less, no damage is taken.
   - If the height is 4 blocks or more, damage taken is \( x-3 \) points, where \( x \) is the fall height.
   - The height refers to the relative height, i.e., the height difference between the current block and the next block.

3. Conditions for reduced fall damage: See special blocks.

4. When health points reach 0, it is considered that the player cannot reach the end.

Parkour

1. For a player standing on a block, the player can jump up to 3 blocks forward and one block upward.
2. For a player standing on a block, the player can also jump up to 4 blocks forward but cannot jump upward.
3. For simplicity, we assume that the player does not move when falling, meaning if the next block is lower than the current block, the player can only fall exactly to the next block.
4. The default end is the last block.

Special Blocks

1. Slime Block: It will make you jump to 60% of the fall distance, rounded down. When you reach the highest point, you can only move one block forward. If you land on a block ahead, you will still take fall damage. You can press the Shift key to avoid bouncing. We assume that parkour on slime blocks is not subject to speed reduction.
2. Cobweb: It will exempt you from fall damage. We also assume that parkour on cobwebs is not subject to speed reduction.

Steve has asked you to help him solve this problem. Determine if Steve can reach the end.

• If he can reach the end, output the minimum number of jumps;
• If he cannot reach the end, output: qwq.

Input Format

The first line is an integer \( n \), indicating there are \( n \) blocks.

From the second line, there are \( n \) consecutive lines, each representing a block with its attributes: x-coordinate, height, and whether it is a special block (normal block input as P, slime block as N, cobweb as Z).

Output Format

If Steve can reach the end, output an integer representing the minimum number of jumps;
if he cannot reach the end, output qwq.

Sample Input and Output

Sample Input #1

2
1 4 P
4 5 P

Sample Output #1

1

Sample Input #2

3
1 6 P
2 4 N
3 4 P

Sample Output #2

0

Sample Input #3

2
5 8 P
7 11 P

Sample Output #3

qwq

Notes

Data Range and Constraints

The input guarantees that the x-coordinates are monotonically increasing. Each x-coordinate has only one block.

The input guarantees that no two special blocks will appear between adjacent x-coordinates.

For blocks, it is assumed that there are no floating blocks; that is, all blocks have support underneath.

For simplicity, one cannot jump and then fall. That is, one can only fall to the block one step ahead.

For 30% of the data, \( n \leq 10 \);
For another 20% of the data, special blocks are guaranteed not to exist;
For the first 50% of the data, it is guaranteed that Steve can only jump four blocks forward or three blocks forward and one block upward;
For 100% of the data, \( 1 \leq n \leq 1000 \), \( 1 \leq x_{\text{max}} \leq 10000 \), \( 1 \leq \text{height} \leq 1000 \).

The data is guaranteed to have a certain gradient.

见题面 Input 部分

见题面 Output 部分