Matriu d'empleats P61055

Una oficina està distribuïda com una matriu $n \times m$ de petits compartiments, a cadascun dels quals treballa exactament un empleat, del qual es coneix el nom i l’edat. El director general de l’empresa, que té poca feina, vol saber, a partir d’un compartiment donat, quants compartiments es pot moure cap a la dreta de manera que cada compartiment tingui un empleat amb nom més gran (alfabèticament) que el de l’empleat anterior i amb edat més petita que la de l’empleat anterior. També vol calcular el mateix, però anant cap avall enlloc de cap a la dreta. El podeu ajudar?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $n$ i $m$, seguides del nom i l’edat de les persones de cada compartiment, seguint el format que es pot veure a l’exemple d’entrada. Per exemple, l’empleat del compartiment $(0, 3)$ es diu Joan i té 63 anys. Segueix el nombre de preguntes del cas $p$, seguit de $p$ triplets $i$ $j$ $c$, on $0 \le i < n$, $0 \le j < m$, i $c$ és un caràcter que és ‘D’ o ‘A’.

Sortida

Per a cada cas, i per a cada pregunta, escriviu el nombre de compartiments que es poden visitar començant en $(i, j)$ i movent-se segons les regles mencionades anteriorment, cap a la dreta si $c$ és ‘D’ o cap avall si $c$ és ‘A’. Escriviu una línia amb 10 guions al final de cada cas.

Observació

No es valorarà cap solució que no usi les definicions

    struct Empleat {
      string nom;
      int edat;
    };

    typedef vector<Empleat> Fila;
    typedef vector<Fila> Matriu;