Processing math: 100%

Problem F. Food stalls

Author:M. Sporyshev   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

City government plans to install several food stalls and several security posts on the street where young programming Alice lives. A scheme of their locations was developed.

Scheme is represented by a string S consisting of characters: '.' — unoccupied place, 'F' — food stall and 'S' — security post.

To be eligible for federal financing, plan must satisfy requirements of Federal program of Postponing and Stalling. In particular, a report is required, where for i-th security post there will be two numbers li and ri — the number of stalls between this post and nearest post to the left (or the beginning of the street) and number of stalls between this post and nearest post to the right (or the end of the street).

Your program must generate the required report.

Input file format

The only line of input file contains a scheme with the plan.

Output file format

Output file must contain integer N — number of security posts, followed by N pairs of integers li and ri — the number of food stalls to the left and to the right of i-th post. Posts must be listed in order of their occurrence in the scheme from left to right.

Constraints

Schema string is no longer than 105.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
.....FFF.F.F.FS......S..F.
2
6 0
0 1
2
S
1
0 0

0.062s 0.015s 13