Maximal Enemy Elimination via a Timed Railgun Shot

In this problem, there are $N$ enemy units represented as points on a 2D plane. For each enemy unit \(i\), its initial position at time \(0\) is \((X_i, Y_i)\). It moves with constant speed \(V_i\) in one of the four cardinal directions given by \(D_i\) (where \(D_i\) is one of 'U', 'D', 'L', or 'R'). Its movement can be described by the following formulas:

• If \(D_i = U\): \(X_i(t) = X_i,\quad Y_i(t) = Y_i + V_i \cdot t\)
• If \(D_i = D\): \(X_i(t) = X_i,\quad Y_i(t) = Y_i - V_i \cdot t\)
• If \(D_i = R\): \(X_i(t) = X_i + V_i \cdot t,\quad Y_i(t) = Y_i\)
• If \(D_i = L\): \(X_i(t) = X_i - V_i \cdot t,\quad Y_i(t) = Y_i\)

Small Ming has a railgun which can be used exactly once at a non-negative integer time \(t\). When fired, the railgun eliminates all enemy units that lie on a single straight line that is parallel to one of the coordinate axes (i.e. a horizontal line \(y = c\) or a vertical line \(x = c\)). Your task is to determine the maximum number of enemy units that can be eliminated by choosing an optimal time \(t\) and the optimal line.

Note: You are allowed to choose any non-negative integer value of \(t\) for firing, and the chosen line can be any horizontal or vertical line.

inputFormat

The first line contains a single integer \(N\) \((1 \leq N \leq 10^5)\), representing the number of enemy units.

Then \(N\) lines follow. The \(i\)-th line contains the information for one enemy unit in the format:

Xi Yi Di Vi

where \(X_i, Y_i\) are integers representing the initial coordinates, \(D_i\) is a character among {U, D, L, R} indicating the direction, and \(V_i\) is an integer representing the speed.

outputFormat

Output a single integer, the maximum number of enemy units that can be eliminated by firing the railgun at an optimal time and along an optimal line.

sample

3
0 0 R 1
1 0 L 1
2 2 U 1

2