The great escape

Luckily, based on the previous exercises you were able to narrow down the list of buildings where your teammate is kept hostage. So your "only remaining task" is to simply go in and free him/her! However the terrorists created traps and obstacles to make your task infinitely more harder. So your job is to try to navigate through this obstacle course to save your teammate!

Input and rules

The input is a single line containing a string and terminated by an end of line character. The contents of the line is the following:

• The characters of the string are the _, |, ~, l, c and P characters.
• There is exactly one P which denotes our teammate.
• Every other character can have an arbitrary number of occurences.

• We start from the "left end" of the map.
• We can only move from left to right.
• At the start out "leg power" and "cardio power" are both 1.
• The _ character denotes the road, which can be travelled without any restrictions.
• The | character denotes a wall. The consecutive | characters give the height of the wall, so e.g. ||| means a 3 meter tall wall. If we encounter a wall, then our "leg power" decides if we can climb it or not. If our "leg power" is at least as big as the height of the wall, then we can climb over it and we arrive to the first field after the walls. Otherwise it is game over.
• The ~ character denotes the water. The consecutive ~ characters give the length of the water, so e.g. ~~~ means a 3 meter long water. If we encounter a wall, then our "cardio power" decides if we can swim through it or not. The principle is the same as for the walls.
• After the consecutive wall or body characters we always stop for a moment to regain our full "leg power" and "cardio power". So e.g. |||~~~~||~~ can be conquered with a "leg power" of 3 and a "cardio power" of 4, since after the 3 meter tall wall our "leg power" is restored, and similarly after the 4 meter long water our "cardio power" is also restored.
• The "l" and "c" characters are short for "IT'S LEG DAY" and "CARDIO TIME" respectively. If we encounter a symbol like this then our "leg power" / "cardio power" are increased permanently by 1.
• Otherwise the l and c characters count as roads, so they completely fill both our "leg power" and "cardio power".

Output

The output is the number 1 if we can reach our teammate or the number 0 otherwise.

Example

Explanation

In the first case the only big problem is the 2 meter long water before the P character. Every other wall or water is only 1 meter tall/long. However since we performed a "bit of a cardio" before the 2 meter long water we are able to swim through it.
In the second case we have multiple 2 meter tall walls and 2 meter long waters. However since we "do a bit of a leg day" around the start, we can easily climb through the walls. However the first 2 meter long water is before the "cardio day", so we are not able to swim through it.