COCI 2009/2010, Contest #6

Task KAJAK

Mirko and Slavko are sports commentators on a local kayaking competition. They have a live satellite feed of the entire track. Since there are too much teams for our dynamic duo to follow, they asked you to help them. They would like you to write a program that will display current standings teamby-team.

The satellite feed is encoded as a table of R rows C characters each. The first character in each row is the starting line, encoded by the character 'S'. The last character in each row is the finishing line, encoded by 'F'. There are exactly nine kayaks on the image. Each kayak is marked by his number, and each spans exactly three consecutive columns. Water is marked by '.'.

Teams are ranked by their distance to the finish line. Smaller is better. If two teams are at the same distance, they share their place.

Input

The first line of input contains two integers R and C (10 ≤ RC ≤ 50), the number of rows and columns of the encoded satellite image.

Each of the following R lines contains exactly S characters '.', 'S', 'F' and digits '1' to '9'. Each row will contain at most one kayak.

Each image contains all 9 kayaks.

Output

Output nine lines, one for each kayak. The ith line should contain the current rank of the ith team.

Sample Tests

Input

10 10
S.....111F
S....222.F
S...333..F
S..444...F
S.555....F
S666.....F
S.777....F
S..888...F
S...999..F
S........F

Output

1
2
3
4
5
6
5
4
3

Input

10 15
S..........222F
S.....111.....F
S...333.......F
S...555.......F
S.......444...F
S.............F
S......777....F
S..888........F
S........999..F
S...666.......F

Output

5
1
6
3
6
6
4
7
2

All Submissions
Best Solutions


Point Value: 5
Time Limit: 1.00s
Memory Limit: 32M
Added: Jul 17, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...