Bajtocja y Bitocja, tras años de guerras sin sentido, finalmente han firmado un tratado de paz. Como símbolo de acuerdo definitivo, se ha construido una autopista entre las capitales de ambos países. Tú has sido designado como el administrador del tramo de la autopista que conduce de Bajtocja hacia Bitocja.*
Actualmente, hay $m$ estaciones de peaje en la autopista, numeradas consecutivamente del 1 al $m$. La primera se encuentra al inicio de la autopista y la última al final. Los costos de pasar por una estación determinada pueden variar según la hora del día. El día se divide en $n$ horas, numeradas del 1 al $n$. Actualmente, el costo de pasar por la estación $j$ a la hora $i$ es de $c_{i,j}$ bajtalares. Algunos de estos costos pueden ser iguales a 0 (el paso por la estación es gratuito) o incluso negativos (el conductor recibe $-c_{i,j}$ bajtalares por pasar por la estación).
Toda la autopista es lo suficientemente corta como para recorrerla en una hora. Sin embargo, no es necesario apresurarse; durante el trayecto se pueden realizar tantas paradas como se desee. No obstante, no se puede pernoctar en la autopista; se debe pasar por todas las estaciones el mismo día.
Naturalmente, los conductores desean cruzar la autopista con el menor costo posible. Denotamos por $f(i, j)$, para $1 \le i \le j \le n$, el costo mínimo posible para cruzar toda la autopista si el conductor pasa por la primera estación a la hora $i$ y por la última estación a la hora $j$. Todos los valores de $f(i, j)$ han sido establecidos en el tratado de paz por los gobiernos de ambos países, por lo que, como administrador de la autopista, no puedes cambiarlos. Sin embargo, puedes modificar libremente las tarifas de paso por las estaciones individuales o incluso cerrar completamente algunas estaciones, siempre que la primera y la última estación permanezcan abiertas, los valores de $f(i, j)$ no cambien y todos los costos que establezcas sean múltiplos enteros de un bajtalar.
Para minimizar los costos de mantenimiento de la autopista, deseas cerrar tantas estaciones como sea posible. Determina el número mínimo de estaciones que deben permanecer abiertas para seguir cumpliendo con las condiciones del tratado.
El proyecto de reorganización del esquema de peajes constará de dos fases. En la primera fase —el proyecto preliminar— basta con encontrar el número óptimo de estaciones. Sin embargo, en la segunda fase —la fase de implementación del proyecto— debes proporcionar además una lista de precios completa y ejemplar para las estaciones restantes.
Entrada
La primera línea de la entrada contiene tres números enteros $n$, $m$ y $q$ ($2 \le n, m \le 30\,000$; $n \cdot m \le 300\,000$; $q \in \{0, 1\}$), que representan, respectivamente, el número de horas en un día, el número actual de estaciones de peaje en la autopista y un bit que describe la fase del proyecto. El valor $q = 0$ significa la primera etapa del proyecto (proyecto preliminar), mientras que el valor $q = 1$ significa que el proyecto ya está en la fase de implementación.
Las siguientes $n$ líneas contienen la descripción de las tarifas actuales; la $i$-ésima línea contiene $m$ números enteros $c_{i,1}, c_{i,2}, \dots, c_{i,m}$ ($-10^6 \le c_{i,j} \le 10^6$). El valor $c_{i,j}$ representa el costo de pasar por la estación $j$ a la hora $i$ expresado en bajtalares. Si el valor $c_{i,j}$ es negativo, el conductor recibe $-c_{i,j}$ bajtalares por pasar por la $j$-ésima estación a la hora $i$.
Salida
En la primera línea de la salida debe aparecer un número entero $k$ ($2 \le k \le m$), que representa el número mínimo de estaciones que deben dejarse en la autopista para que ningún valor de $f(i, j)$ cambie. Si $q = 0$, la salida debe consistir únicamente en una línea que contenga este número.
Si $q = 1$, en las siguientes $n$ líneas debe aparecer una lista de precios óptima de ejemplo que cumpla con las condiciones del problema. En la $i$-ésima de estas líneas debe haber $k$ números enteros $d_{i,1}, d_{i,2}, \dots, d_{i,k}$ ($-10^{12} \le d_{i,j} \le 10^{12}$). El valor $d_{i,j}$ representa el nuevo costo de pasar por la $j$-ésima de las estaciones restantes a la hora $i$.
Se puede demostrar que, para las restricciones del problema, siempre es posible determinar costos que sean números enteros cuyos valores absolutos no excedan $10^{12}$.
Ejemplos
Entrada 1
3 6 1 -1 0 4 0 -3 0 -4 1 5 2 -5 2 -5 2 3 0 -2 2
Salida 1
3 0 0 0 0 1 0 0 0 0
Entrada 2
5 7 0 0 0 0 8 0 0 0 0 7 6 5 9 7 0 0 0 0 5 9 6 0 9 4 0 4 4 7 0 0 0 0 9 8 6 0
Salida 2
3
Nota
En el primer caso de prueba, los costos mínimos individuales para cruzar la autopista son los siguientes: $f(1, 1) = (-1) + 0 + 4 + 0 + (-3) + 0 = 0$, $f(1, 2) = (-1) + 0 + 4 + 0 + (-5) + 2 = 0$, $f(1, 3) = (-1) + 0 + 4 + 0 + (-5) + 2 = 0$, $f(2, 2) = (-4) + 1 + 5 + 2 + (-5) + 2 = 1$, $f(2, 3) = (-4) + 1 + 3 + 0 + (-2) + 2 = 0$, $f(3, 3) = (-5) + 2 + 3 + 0 + (-2) + 2 = 0$.
No es posible obtener los mismos costos de viaje utilizando solo dos estaciones. Ten en cuenta que la primera y la última estación no pueden cerrarse, a pesar de que con los costos $d_{i,j}$ propuestos no se cobran tarifas en ellas.
En el segundo caso de prueba, la salida no contiene una propuesta de nueva lista de precios, ya que el proyecto de reorganización del esquema de peajes se encuentra apenas en la fase preliminar.
Subtareas
- En las pruebas que valen la mitad de los puntos, se cumple la condición $q = 0$.
- En las pruebas restantes, siempre se cumple la condición $q = 1$.
*El sentido de Bitocja a Bajtocja no te interesa; es gestionado por un enviado de un país amigo hostil.