ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2016

About     Problems     Submit solution     Judge status     Standings
Contest is over

J. Trains

Time limit: 4.0 second
Memory limit: 256 MB
Yulia is not related to Ural ACM, and the reason she is mentioned here is that she has written this task. At the university Yulia preferred mathematics to programming, so her maximum is bubble sorting in Pascal, while at the same time Yulia is an important manager at a large IT company. As every manager, Yulia has meetings. Not all meetings are equally useful, so Yulia appreciates smartphone games that can be played in 1-2 minutes very much.
This is how "Trains" found their place in Yulia’s phone. The game is very simple: the screen shows a railway map, each way ends with a colored station/depot, crossings are equipped with turnouts. One by one, trains leave the only depot. Player has to direct each train to a station of corresponding color, switching the turnouts timely. Just a moment of distraction — and the trains are running all around like colored cockroaches, and you have no idea what to do. So, the game requires tapping the screen with promptness and concentration.
Den noticed the game once, peeking over Yulia’s shoulder. Unlike Yulia, Den is an experienced ACM player, that is why he does not want to just tap the screen, he wants an algorithm. So said so done, after half an hour and three shots of B-52 a bot effectively playing Trains written by Den emerged.
Be like Den! Implement an algorithm for the Trains game. Keep in mind, however, that while Yulia as a manager plans beforehand and switches turnouts in advance, the only thing that motivates Den is the upcoming deadline, so his bot switches the turnout exactly when the train reaches it.


In the first line two numbers N and M are given (2 ≤ N, M ≤ 500), then 2 × N−1 lines follow containing 2 × M−1 characters each — map description. Keys on the map are as follows:
  • ’S’ — depot;
  • ’X’ — station;
  • ’F’, ’L’, ’R’ — turnout;
  • ’|’ (vertical bar, decimal ASCII code 124), ’-’ (hyphen, decimal ASCII code 45) — straight segments of the railway;
  • ’.’ (full stop, decimal ASCII code 46) — point outside the railway.
It is guaranteed that the railway network is a tree, with turnouts being represented by internal nodes, depot or stations — by leaves, with only one depot. Tree edges stand for straight-line sections of the network (an edge is one symbol ’|’ or ’-’).
Position of a turnout determines the direction in which a train will follow through, a turnout cannot direct a train to a point outside the railway network. The letter representing a turnout on the map indicates its initial position. ’F’ means that a train having passed the turnout will keep moving forward, ’R’ — will turn right, ’L’ — will turn left.
The next line contains one number Q (1 ≤ Q ≤ 2 × 105) — the number of trains leaving the depot. Each of the following Q lines contains 3 numbers Ti, Xi, Yi (1 ≤ Ti ≤ 109, 1 ≤ XiN, 1 ≤ YiM) — depot departure time for i-th train and destination station coordinates. Trains are ordered by their depot departure time ascending.


In the first line output a single number R (0 ≤ R ≤ 2 × 105) — the lowest number of required turnout switches.
Each of the following R lines must contain a description of one switch — three numbers Ti, Xi, Yi and one character Ci (Ci ∈ {’F’, ’L’, ’R’}), separated from Yi by exactly one space. String Ti Xi Yi Ci means that at the moment of time Ti the turnout situated at (Xi, Yi) is to be switched according to the train direction: ’F’ — forward, ’R’ — right, ’L’ — left. Switching several turnouts at a single moment of time is allowed.
It is guaranteed that there exists at least one solution with the number of switches not exceeding 2 × 105. If several possible solutions exist, output any.


3 3
1 1 3
2 3 1
4 1 3
6 3 2
3 1 2 R
5 1 2 F
7 1 2 R
8 2 2 L
2 3
1 2 2
2 1 3
4 1 3
2 1 2 R
3 1 2 F


Let’s look at the second example in more detail. The map contains a depot, two stations, three railway segments, and a turnout. The turnout is initially set in order to direct the train forward. It has two positions: forward and to the right. At the moment 1 a train starts at the depot. It will pass a distance unit in a time unit and will be at the turnout at the moment 2. In order to reach its destination the train needs to turn right, so the turnout should be switched to the "right" position. Here comes the first switch: 2 1 2 R
At the same moment 2 the second train starts from the depot. It will show up at the turnout at the moment 3, and he will need to pass forward. So the turnout will have to be switched again. Here comes the second switch: 3 1 2 F
The third train will go in the same direction as the second one, so no switch will be required for it.
Problem Author: Denis Mukhametianov
To submit the solution for this problem go to the Problem set: 2087. Trains