시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB151515100.000%

문제

Dave and Hal are playing one interesting game with cards. Dave has N cards (N is divisible by three, N=3K) with numbers from 1 to N written on them.

Each card has the same number written on both sides, and no two cards share the same number. Cards are sorted.

First Hal thinks of one number from set {1, 2, ..., N}.

Then Dave lays cards in K rows and three columns on a table starting with card numbered by 1 filling the first row from left to right, then second row, and so on till he finishes with the last row.

Hal then says in which column Dave put the card with a number he thought of.

Dave then picks up the cards from the first column (firstly taking card from the first row, then from the second and so on to the last row), then from the second and finally from the third column in the same way. He then lays them, without shuffling, to the table again the same way as the first time.

Each time Dave puts all the cards on the table, Hal tells him in which column is the card with his number.

Dave’s task is to guess Hal’s number.

Write a program that will use Hal’s answers to help Dave to determine the smallest set of numbers that are candidates for Hal’s number, 

입력

The first line of input file contains a natural number N, 3 ≤ N ≤ 999, the number of all cards.

The second line contains a natural number D, 1 ≤ D ≤ 10, the numbers of dealings (i.e. the number of Hal’s answers).

The following D lines contain words 'first', 'second' or 'third', denoting Hal’s answers – one word in each line.

출력

To the first and only line of output file should be written all the numbers from the smallest set of numbers that are candidates for Hal’s number. The numbers can be written in any order, and must be separated by a space.

예제 입력 1

6
1
second

예제 출력 1

5 2

예제 입력 2

12
2
third
first

예제 출력 2

6

예제 입력 3

18
2
first
third

예제 출력 3

7 16