404767: GYM101628 D Don't Lose The Droid

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 (X_i, Y_i) be the position of the probe at instant i, these actions can be:

• C: The probe moves upwards (X_i + 1 = X_i + 1)
• D: The probe moves rightwards (Y_i + 1 = Y_i + 1)
• B: The probe moves downwards (X_i + 1 = X_i - 1)
• E: The probe moves leftwards (Y_i + 1 = Y_i - 1)

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 ≤ 10⁶, 1 ≤ N × M ≤ 10⁶), the number of lines and the number of coulmns in the matrix.

The second line contains 1 integer T (1 ≤ T ≤ 10⁶), the current instant. T lines follow. The (i + 2)-th line contains 1 character, l_i (), 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, X_j (1 ≤ X_j ≤ N) and Y_j (1 ≤ Y_j ≤ N), the j-th coordinates of the matrix to be verified.

3 3
3
D
D
B

2
1 3
2 3

1 3
1
E

2
1 1
1 2