Bajtocja et Bitocja ont enfin signé un traité de paix après des années de guerres absurdes. En signe de réconciliation définitive, une autoroute a été construite entre les capitales des deux pays. Vous avez été désigné comme gestionnaire du tronçon d'autoroute menant de Bajtocja vers Bitocja.
Il y a actuellement $m$ péages sur l'autoroute, numérotés de $1$ à $m$. Le premier se trouve au début de l'autoroute et le dernier à la fin. Les coûts de passage à un péage donné peuvent varier selon l'heure de la journée. La journée est divisée en $n$ heures, numérotées de $1$ à $n$. Actuellement, le coût de passage au péage $j$ à l'heure $i$ est de $c_{i,j}$ bajtalars. Certains de ces coûts peuvent être égaux à $0$ (le passage est alors gratuit) ou même négatifs (le conducteur reçoit alors $-c_{i,j}$ bajtalars pour avoir franchi le péage).
L'autoroute est suffisamment courte pour être parcourue en une heure. Cependant, il n'est évidemment pas nécessaire de se presser ; on peut faire autant d'arrêts que souhaité pendant le trajet. Il n'est toutefois pas possible de passer la nuit sur l'autoroute ; tous les péages doivent être franchis le même jour.
Les conducteurs souhaitent naturellement traverser l'autoroute au coût le plus bas possible. Pour $1 \le i \le j \le n$, on note $f(i, j)$ le coût minimal possible pour traverser toute l'autoroute si le conducteur franchit le premier péage à l'heure $i$ et le dernier péage à l'heure $j$. Toutes les valeurs $f(i, j)$ ont été fixées dans le traité de paix par les gouvernements des deux pays ; en tant que gestionnaire de l'autoroute, vous ne pouvez donc pas les modifier. Vous pouvez cependant modifier librement les tarifs de passage aux différents péages ou même fermer complètement certains péages, à condition que le premier et le dernier péage restent ouverts, que les valeurs $f(i, j)$ ne changent pas et que tous les coûts que vous fixez soient des multiples entiers d'un bajtalar.
Afin de minimiser les coûts de maintenance de l'autoroute, vous souhaitez fermer autant de péages que possible. Déterminez le nombre minimal de péages qui doivent rester ouverts pour continuer à respecter les conditions du traité.
Le projet de réorganisation du système de péage se déroulera en deux phases. Dans la première phase — le projet préliminaire — il suffit de trouver le nombre optimal de péages. Cependant, dans la seconde phase — la phase de mise en œuvre du projet — vous devez également fournir une grille tarifaire complète pour les péages conservés.
Entrée
La première ligne de l'entrée contient trois entiers $n, m$ et $q$ ($2 \le n, m \le 30\,000$ ; $n \cdot m \le 300\,000$ ; $q \in \{0, 1\}$), représentant respectivement le nombre d'heures dans une journée, le nombre actuel de péages sur l'autoroute et un bit décrivant la phase du projet. La valeur $q = 0$ signifie la première étape du projet (projet préliminaire), tandis que la valeur $q = 1$ signifie que le projet est déjà en phase de mise en œuvre.
Les $n$ lignes suivantes contiennent la description des tarifs actuels ; la $i$-ième ligne contient $m$ entiers $c_{i,1}, c_{i,2}, \dots, c_{i,m}$ ($-10^6 \le c_{i,j} \le 10^6$). La valeur $c_{i,j}$ représente le coût de passage au péage $j$ à l'heure $i$ exprimé en bajtalars. Si la valeur $c_{i,j}$ est négative, le conducteur reçoit $-c_{i,j}$ bajtalars pour le passage au $j$-ième péage à l'heure $i$.
Sortie
La première ligne de la sortie doit contenir un entier $k$ ($2 \le k \le m$), représentant le nombre minimal de péages à conserver sur l'autoroute pour qu'aucune valeur $f(i, j)$ ne soit modifiée. Si $q = 0$, la sortie doit se composer d'une seule ligne contenant uniquement ce nombre.
Si $q = 1$, les $n$ lignes suivantes doivent contenir une proposition de grille tarifaire optimale respectant les conditions du problème. La $i$-ième de ces lignes doit contenir $k$ entiers $d_{i,1}, d_{i,2}, \dots, d_{i,k}$ ($-10^{12} \le d_{i,j} \le 10^{12}$). La valeur $d_{i,j}$ représente le nouveau coût de passage au $j$-ième péage conservé à l'heure $i$.
Il est possible de démontrer que, pour les contraintes du problème, il est toujours possible de déterminer des coûts sous forme d'entiers dont les valeurs absolues ne dépassent pas $10^{12}$.
Exemples
Entrée 1
3 6 1 -1 0 4 0 -3 0 -4 1 5 2 -5 2 -5 2 3 0 -2 2
Sortie 1
3 0 0 0 0 1 0 0 0 0
Entrée 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
Sortie 2
3
Remarque
Dans le premier test, les coûts minimaux individuels pour traverser l'autoroute sont les suivants : $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$.
Il n'est pas possible d'obtenir les mêmes coûts de trajet en utilisant seulement deux péages. Notez que le premier et le dernier péage ne peuvent pas être fermés, même si, avec les coûts $d_{i,j}$ proposés, aucun frais n'est prélevé à ces péages.
Dans le second test, la sortie ne contient pas de proposition de nouvelle grille tarifaire, car le projet de réorganisation du système de péage n'en est qu'à sa phase préliminaire.
Sous-tâches
- Dans les tests valant la moitié des points, la condition $q = 0$ est vérifiée.
- Dans les tests restants, la condition $q = 1$ est toujours vérifiée.