Cerința

Se dă o matrice binara cu N linii și M coloane. Celulele cu numărul 0 sunt libere și se pot traversa. Celulele cu numărul 1 sunt ocupate și nu se pot traversa. Pentru K poziții date, se cere să se determine drumul de lungime minimă care pleacă de la poziția (i1, j1) și trece prin toate cele K poziții intermediare (nu contează în ce ordine), ajungând în final în poziția (i2, j2).

Date de intrare

Fișierul de intrare lee3.in conține pe prima linie numerele N și M.

Pe următoarele N linii vor fi câte M numere, reprezentand structura matricei.

Pe următoarea linie se vor afla patru numere: i1, j1, i2 si j2 cu semnificația din enunț. Pe următoarea linie se află numărul K, urmat de K perechi de numere (i, j) după cum reiese și din enunț.

Date de ieșire

Fișierul de ieșire lee3.out va conține pe prima linie numărul C, reprezentând numărul minim de poziții din matrice prin care se va trece începând cu (i1, j1), pentru a trece prin toate cele K poziții și terminând în poziția (i2, j2).

Pe următoarele linii se vor afișa K+2 perechi de numere (i, j), reprezentând ordinea în care sunt parcurse cele K poziții, inclusiv poziția inițială și cea finală. Indicii pozițiilor se separă prin virgula. Dacă există mai multe trasee de aceeași lungime minimă, atunci se va afișa oricare.

Restricții și precizări

• 1 ≤ N, M ≤ 750
• 1 ≤ K ≤ 19
• 1 ≤ i1, i2, i[k] ≤ N
• 1 ≤ j1, j2, j[k] ≤ M
• Se garantează că există soluție pentru toate testele
• Pentru 10% din teste: K ≤ 7
• Pentru restul testelor: nicio restricție suplimentară

Exemplu:

lee3.in

4 5
0 0 0 0 0
1 0 1 1 1
1 0 0 0 1
1 1 0 0 0
1 1 4 4
3
1 5
3 2
3 4

lee3.out

12
1,1
1,5
3,2
3,4
4,4

Explicație

Se pleacă din poziția (1, 1) și se merge în poziția (1, 5), apoi în (3, 2, apoi în (3, 4) și apoi ajunge la destinație în (4, 4).