Problem D: [Usaco2012 Feb]Cow Cotillion

Problem D: [Usaco2012 Feb]Cow Cotillion

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 301  Solved: 159
[Submit][Status][Web Board]

Description

每年春天,奶牛们会举行一个盛大的舞会。 
舞会上公牛(表示为">")和母牛(表示为"<")相互鞠躬以后开始舞蹈。 
原则上,一对相互鞠躬的牛表示为:"><"。 
有时候,另一对牛会处在一对相互鞠躬的牛中间:"> >< <"。 
事实上,有些时候舞厅会有非常多的牛会混杂在一起:"> >< < ><"。 
会比上面的例子更复杂一点(右侧又多加了一对相互鞠躬的牛)。 
如下是一个更复杂但合法的安排: 

  > > > >< < >< < >< >< >< <
 
              | | | -- | -- | -- -- -- |
              | | ------    |          |
              | -------------          |
              --------------------------

Farmer John注意到有时会有游荡的牛闯入一组跳舞者中,因此这个跳舞组变得不平衡:"> >< < <><"。 
这是严格禁止的。Farmer John想要惩罚这些闯入者。 
Farmer John整理出一些跳舞队列的记录。每个跳舞队列最多有500只牛。 
他想要知道这些跳舞队列是否平衡。 
平衡也就是说至少有一种方案可以使每头牛都加入一个鞠躬对。 
Farmer John一共整理出N组记录(1 <= N <= 1,000)。 
第i组记录由字符('>' and '<')和一个表示长度的K_i (1 <= K_i <=200)构成。 
如果记录可以平衡,输出"legal",否则,输出"illegal"。

Input

* Line 1: A single integer: N
* Lines 2..N+1: Line i contains an integer followed by a space and a
        string of K characters '>' and '<': K_i and P_i

Output

* Lines 1..N: Line i contains either the word "legal" or "illegal"
        (without the quotes, of course) depending on whether the input
        has a legal bowing configuration.

Sample Input

2
6 >><<><
4 ><<>

Sample Output

legal
illegal

HINT

[Submit][Status]