Light or Weight

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

  The "Gold Bar"bank received information from reliable sources that in their last group of N coins exactly one coin is false and differs in weight from other coins (while all other coins are equal in weight). After the economic crisis they have only a simple balance available. Using this balance, one is able to determine if the weight of objects in the left pan is less than, greater than, or equal to the weight of objects in the right pan. 
   In order to detect the false coin the bank employees numbered all coins by the integers from 1 to N, and there is a standard coin (The standard coin means its weight is standard) numbered 0. 
   You are to write a program that will help the bank employees to determine the identifier of the false coin and weight. And your program must determine the false coin in K times weighting. 
   To challenge your algorithmic ability, the number of coins fixed at N=(3K-1)/2, is the limit of coins which you can determine the false coin in K weightings. 

Input

  There are several test cases. For each test case, a single line contains only one integer K. K is the number of weightings (1≤K≤12). The input file will end when K=0 and not need to process.

   Then by calling function SetCoin, computer set one coin false: the identifier of the false coin, light or weight. 
   By calling Function Judge, the function will return a char:
   '<' means that the weight of coins in the left pan is less than the weight of coins in the right pan, 
   '>' means that the weight of coins in the left pan is greater than the weight of coins in the right pan, 
   '=' means that the weight of coins in the left pan is equal to the weight of coins in the right pan. 
   For each test case, your program can at most call the function Judge K times, if not, the function Judge will return 0; 

Output

  For each test case, output a single line in following format:
   # c
   Where # is the identifier of the false coin, c is ‘<’ if the false coin is light, ‘>’ if the false coin is weight.
   You may assume that the false coin must exist. 

Sample Input

2
3
0

Sample Output

1 >
13 <

Hint

 

Source

2010湖南大学校赛