Chess

Problem

The kings, queens, knights and rooks are pieces used in chess, a game played on a board with squares arranged in rows and columns. The squares marked K, Q, N and R respectively represent the position of the king, queen, knight, rook, and the squares marked X indicate the squares that are under attack.

             X   X   X 
              X  X  X          X   X             X      
   XXX         X X X         X       X           X     
   XKX          XXX              N               X     
   XXX       XXXXQXXXXX      X       X       XXXXRXXXX 
                XXX            X   X             X     
               X X X                             X     
              X  X  X                            X     
             X   X   X  

In this problem, you are required to find out the largest number of pieces that can be placed in the given board so that no two pieces can attack each other. Consider each type separately. For each type of on pieces, find the maximum number of pieces of this type that can be put on the board so that they can't attack each other in one step. The board will have dimension of M rows by N column and both of them will not larger than 60000.

Input

The input consists of a number of test cases, each on a single line. The line will contain two integers M and N. 1 ≤ M, N ≤ 60000. The last line contains a pair of zeroes, which should not be processed.

Output

For each test case, display the number of kings, queens, knights and rooks that can be appropriately placed in the format below. Print 'kings', 'queens', etc even if only 1 piece of it can be placed.

Sample Input

2 3
5 5
4 7
0 0

Sample Output

2 kings, 2 queens, 4 knights and 2 rooks may be placed on the board.
9 kings, 5 queens, 13 knights and 5 rooks may be placed on the board.
8 kings, 4 queens, 14 knights and 4 rooks may be placed on the board.

Author