The Gnomes, living in dark and cold caves, invented their own game on ice. They called it a gnomish hockey.
However, it is really different from the hockey we know. The game is played with multiple pucks on the ice H \times W with the outer walls around it. And there is only one team trying to hit one goal.
Some of the cells are empty, some contain pucks. The puck perfectly fits the cell. The gnome may pull any puck in any of four directions parallel to the coordinate axis.
When the puck hits something (either the outer wall or another puck) it stops immediately. When the puck is hit by another puck, it starts movement in the same direction. This is including the cases when puck hits several pucks staying one after another in the direction of the movement: for example, let puck hit two pucks and staying in a row: then stops, starts movement and immediately stops at the same cell, but it "passes" movement to which starts the movement. Note that a puck will not replace another puck; instead, it will stop right before it.
Exactly one cell is labeled as goal. If the team managed to stop any of the pucks at the goal cell, it wins the round. Otherwise, the round is lost. Note that if the puck is sliding over the goal, it cannot be counted as the victory.
You are given the size of the playfield, initial placement of pucks and the goal cell. Check if gnomes can win the game starting with this placement if they are playing optimally.
First line of the input contains two integers and (1 \le H, W \le 16). Each of following lines contains exactly characters. Character 'p' denotes the puck, character 'g' — the goal, character '.' — other cells on the ice. You may assume that there is exactly one goal and at least one puck in the input.
Print "yes" if gnomes can stop a puck at the goal, or "no" otherwise.
Example 1
Example 2
Example 3