Having learned (not without some help from the Codeforces participants) to play the card game from the previous round optimally, Shrek and Donkey (as you may remember, they too live now in the Kingdom of Far Far Away) have decided to quit the boring card games and play with toy soldiers. The rules of the game are as follows: there is a battlefield, its size equals n × m squares, some squares contain the toy soldiers (the green ones belong to Shrek and the red ones belong to Donkey). Besides, each of the n lines of the area contains not more than two soldiers. During a move a players should select not less than 1 and not more than k soldiers belonging to him and make them either attack or retreat . An attack is moving all of the selected soldiers along the lines on which they stand in the direction of an enemy soldier, if he is in this line. If this line doesn't have an enemy soldier, then the selected soldier on this line can move in any direction during the player's move. Each selected soldier has to move at least by one cell. Different soldiers can move by a different number of cells. During the attack the soldiers are not allowed to cross the cells where other soldiers stand (or stood immediately before the attack). It is also not allowed to go beyond the battlefield or finish the attack in the cells, where other soldiers stand (or stood immediately before attack). A retreat is moving all of the selected soldiers along the lines on which they stand in the direction from an enemy soldier, if he is in this line. The other rules repeat the rules of the attack. For example, let's suppose that the original battlefield had the form (here symbols " G " mark Shrek's green soldiers and symbols " R " mark Donkey's red ones): Let's suppose that k = 2 and Shrek moves first. If he decides to attack , then after his move the battlefield can look like that: If in the previous example Shrek decides to retreat , then after his move the battlefield can look like that: On