실행 시간 제한 | 메모리 제한 |
---|---|
1 초 | 128 MB |
매년 봄마다 열리는 화려한 라인 댄스 파티에서 남자들과 여자들은 댄스 중에 서로 인사를 합니다.
정상적으로 인사를 하는 한 쌍의 남녀들은 마치 이렇게 보입니다: '><'.
때로는 인사하는 두 남녀 사이로 또 다른 한 쌍의 남녀가 끼어들기도 합니다: '> >< <'.
실제로, 더 많은 수의 사람이 혼합되어 이렇게 보일 때가 있습니다: '> >< < ><' (오른쪽에 두 번째로 인사를 하는 사람의 집합이 포함되어 있습니다). 복잡해 보이는 정렬도 알고보면 완벽하게 정상적인 라인 댄스 형태일 수 있습니다:
> > > >< < >< < >< >< >< <
| | | -- | -- | -- -- -- |
| | ------ | |
| ------------- |
--------------------------
행사 주최자인 상철은 종종 파트너를 잃은 여자가 그룹에 끼어들어 균형을 깨뜨리는 것을 발견했습니다.: '> >< < <><'.
이는 엄격히 금지된 행위이며, 상철은 이를 막고 싶어합니다.
상철은 최대 500명의 사람들이 참여하는 라인 댄스의 cctv 기록을 복사한 후, 라인 댄스의 균형이 맞는지 (즉, 모든 사람들이 적어도 한 가지 방법으로 한 쌍씩 짝을 이루어 댄스를 추는지) 알고 싶어합니다.
각자 어떤 사람에게 인사를 했는지 확인하기 위해 공백을 제외하고 방향만을 복사하여 균형이 깨진 라인 댄스의 예시를 다음과 같이 표현했습니다. 예: '>><<<><'.
여러분에게 라인 댄스의 규칙이 잘 지켜졌는지 프로그램을 작성하라는 상철의 요청이 있습니다.
상철에게는 N (1 <= N <= 1,000)개의 패턴의 cctv 기록 P_i가 있으며, 이는 길이가 다른 K_i (1 <= K_i <= 200)개의 문자 '>'와 '<'로 구성되어 있습니다. 그 패턴들이 제대로 인사하고 있는 사람의 쌍을 포함하고 있으면 'legal'를, 그렇지 않으면 'illegal'을 출력합니다.
2 6 >><<>< 4 ><<>
legal illegal