Avem o matrice cu N linii, numerotate de la 1 la N şi M coloane, numerotate de la 1 la M. Numărul de coloane este impar. Valorile din matrice sunt numere naturale nenule. Orice valoare apare pe aceeaşi linie de cel mult două ori. Există mai multe întrebări în legătura cu elementele matricei. O întrebare este de următoarea formă: se dă q, un număr întreg. Se cere să parcurgem un drum prin matrice, de cost minim, care îndeplineşte condiţiile:
- Pleacăm de la coloana din mijloc, de deasupra liniei 1 (îi spunem linia 0).
- La un pas, dacă ne găsim pe linia i, ne deplasăm pe linia i+1; dacă pe linia i+1 există valori egale cu q, trebuie să ne deplasăm obligatoriu în poziţia uneia dintre ele; dacă nu exisă valori egale cu q, ne deplasăm obligatoriu în poziţia aflată la mijlocul liniei.
- În final trebuie să ajungem în poziţia de sub mijlocul ultimei linii (să spunem, la mijlocul liniei N+1).
- Costul unui pas se calculează astfel: dacă de pe linia i, coloana j păşim pe linia i+1, coloana k, costul acestui pas este modul(j-k).
- Costul unui drum este egal cu suma costurilor tuturor paşilor de pe drum.
Cerinţă
Dându-se mai multe întrebări, să se determine răspunsul la fiecare dintre ele.
Date de intrare
Fişierul mijloc.in conţine pe prima linie trei numere naturale, N M Q reprezentând respectiv, numărul de linii ale matricei, numărul de coloane ale matricei şi numărul de întrebări.
Pe următoarele N linii, se găsesc câte M numere naturale, care reprezintă elementele matricei. Acolo unde sunt mai multe numere pe o linie, ele sunt separate prin câte un spaţiu. Următoarele Q linii, conţin câte un număr natural care reprezintă o întrebare.
Date de ieşire
În fişierul mijloc.out se vor scrie Q numere, câte unul pe fiecare linie, reprezentând răspunsurile la întrebări, în ordinea în care acestea sunt în fişierul de intrare.
Restricţii
1 <= N <= 20
1 <= M <= 4999, M impar
1 <= Q <= 5000
Valorile din matrice şi întrebările sunt numere naturale nenule mai mici sau egale decât un miliard.