The Inter-space Navigation Center (CIN in portuguese) launched a probe in a distant planet. To know its precise location, the Center will need to maintain a satellite following its steps. That way, the satellite needs first to find the probe in the terrain of the unknown planet, which can be considered a matrix of N lines and M columns.
While operating, the probe emits a log with the taken actions at each instant of time. Let (Xi, Yi) be the position of the probe at instant i, these actions can be:
At instant T all the logs emited by the probe since instant 0 will be available. Your task is compute all positions that must be checked at instant T so that the probe is guaranteedly found.
The satellite is capable of analyzing as many positions as they're necessary, but you must not check any position for which there are enough data to determine that the probe can't be there.
The first line contains 2 space separated integers, N and M (1 ≤ N, M ≤ 106, 1 ≤ N × M ≤ 106), the number of lines and the number of coulmns in the matrix.
The second line contains 1 integer T (1 ≤ T ≤ 106), the current instant. T lines follow. The (i + 2)-th line contains 1 character, li (), the probe's log at instant i.
In the first line, print 1 integer, Q (1 ≤ Q ≤ N * M), the number of positions to be verified.
Then, print Q lines. In the (j + 1)-th line, print 2 space separated integers, Xj (1 ≤ Xj ≤ N) and Yj (1 ≤ Yj ≤ N), the j-th coordinates of the matrix to be verified.
## Input
The first line contains 2 space separated integers, N and M (1 ≤ N, M ≤ 106, 1 ≤ N × M ≤ 106), the number of lines and the number of coulmns in the matrix.The second line contains 1 integer T (1 ≤ T ≤ 106), the current instant. T lines follow. The (i + 2)-th line contains 1 character, li (), the probe's log at instant i.
## Output
In the first line, print 1 integer, Q (1 ≤ Q ≤ N * M), the number of positions to be verified.Then, print Q lines. In the (j + 1)-th line, print 2 space separated integers, Xj (1 ≤ Xj ≤ N) and Yj (1 ≤ Yj ≤ N), the j-th coordinates of the matrix to be verified.
[samples]
**Definitions**
Let $ N, M \in \mathbb{Z}^+ $ be the dimensions of the grid, with $ 1 \leq N, M \leq 10^6 $ and $ N \times M \leq 10^6 $.
Let $ T \in \mathbb{Z}^+ $ be the number of time steps, $ 1 \leq T \leq 10^6 $.
Let $ L = (l_0, l_1, \dots, l_{T-1}) $ be the sequence of log commands, where each $ l_i \in \{ \text{'U'}, \text{'D'}, \text{'L'}, \text{'R'} \} $ represents the probe’s movement at time $ i $:
- 'U': $ (x, y) \to (x-1, y) $
- 'D': $ (x, y) \to (x+1, y) $
- 'L': $ (x, y) \to (x, y-1) $
- 'R': $ (x, y) \to (x, y+1) $
Let $ P = \{ (x, y) \in \{1, \dots, N\} \times \{1, \dots, M\} \} $ be the set of all possible initial positions.
For each initial position $ (x_0, y_0) \in P $, define the trajectory $ (x_i, y_i) $ for $ i = 0, \dots, T $ by:
- $ (x_0, y_0) $: initial position
- $ (x_{i+1}, y_{i+1}) = \text{move}((x_i, y_i), l_i) $, respecting grid boundaries (i.e., position remains unchanged if move would go outside $ [1, N] \times [1, M] $).
Let $ S \subseteq P $ be the set of initial positions such that the entire trajectory $ (x_0, y_0), \dots, (x_T, y_T) $ stays within bounds.
**Objective**
Compute the set $ R \subseteq \{1, \dots, N\} \times \{1, \dots, M\} $ of all possible final positions $ (x_T, y_T) $ reachable from *any* initial position $ (x_0, y_0) \in S $ under the given log sequence $ L $.
Output:
- $ Q = |R| $
- All $ (x, y) \in R $, one per line, in any order.