Minimum Subway Lines

In city S, an underground network is planned as a grid with n horizontal tunnels and m vertical tunnels, forming \(n \times m\) intersections, each of which will be a subway station. All subway lines (routes) must cover every station in the network, and the overall network must be connected. That is, starting from any station, one can reach every other station by taking one or more subway lines (transferring at stations common to two or more lines).

In addition, every individual subway line must not be detoured. Formally, when traveling from the starting station to the ending station along a subway line, if there exist two segments on parallel corridors where the train is running in opposite directions, then the route is said to be detoured. (See the figure where the red, green, and blue lines are non-detoured while the yellow, orange, and purple ones are detoured.)

S City wants to minimize the number of subway lines being built. Given the dimensions of the underground grid \(n \times m\), output the minimum number of subway lines required and provide one valid plan. If your answer uses more lines than the minimum, you will receive partial credit.

Construction Idea:
For the cases when both \(n\) and \(m\) are greater than 1, one valid strategy is as follows:

• If \(n \le m\): choose one vertical line at column \(c=\lceil{m/2}\rceil\) (i.e. \(c = \frac{m+1}{2}\) in integer division) and then add a horizontal line for each row. This covers all stations and ensures connectivity since every horizontal line intersects that vertical line.
• If \(m < n\): choose one horizontal line at row \(r=\lceil{n/2}\rceil\) and then add a vertical line for each column.

For the edge case when \(n=1\) or \(m=1\), a single line covering the only row or column is sufficient.

inputFormat

The input consists of a single line containing two integers \(n\) and \(m\) (\(1 \le n, m \le 10^5\)), which denote the number of horizontal and vertical tunnels respectively.

outputFormat

First, output an integer \(k\) denoting the number of subway lines in your plan. Then output \(k\) lines, each describing one subway line. A subway line is represented by a string in one of the following formats:

• H i — a horizontal subway line covering row i (1-indexed).
• V j — a vertical subway line covering column j (1-indexed).

The plan must cover every station in the grid and the overall network (the union of the lines) must be connected. Moreover, every individual line must not be detoured as defined above.

sample

1 5

1
H 1

</p>