lemans

Ne aflăm înainte de începutul faimoasei curse de anduranță de la Le Mans. După cum bine știți, într-o cursă de anduranță mașina care a parcurs cea mai mare distanță pe parcursul cursei este considerată câștigătoare.

Anul acesta Federația Internațională de Automobilism (FIA) a făcut câteva schimbări majore cu privire la desfășurarea cursei. Anul acesta cursa va dura exact $T$ secunde și vor participa $N$ echipe, fiecare echipă având câte o mașină, iar fiecare mașină poate pleca de pe oricare dintre cele $M$ poziții din grila de start.

De asemenea, FIA a impus câteva reguli care au nemulțumit echipele participante:

• Fiecare mașină este obligată să se deplaseze cu o viteză constantă pe parcursul întregii curse. Astfel, a $i$-a mașină se va deplasa cu viteza de $v[i]$ metri pe secundă.
• Dacă o mașină pleacă de pe o poziție $j$ din grila de start, aceasta se află la o distanță de $p[j]$ metri după linia de start, iar această distanță este luată în considerare ca o distanță deja parcursă în cadrul cursei.

Cerință

Ca semn de protest asupra noului regulament, echipele au hotărât să se așeze în grila de start astfel încât diferența maximă dintre distanțele parcurse de oricare două mașini să fie cât mai mică posibil.

Date de intrare

Pe prima linie din fișierul lemans.in se vor afla 3 numere:

• $T$ — durata cursei exprimată în secunde;
• $N$ — numărul de mașini;
• $M$ — numărul de poziții de start din grilă.

Pe a doua linie se află $N$ numere separate prin câte un spațiu, reprezentând șirul $v$ de viteze ale mașinilor.

Pe a treia linie se află $M$ numere separate prin câte un spațiu, reprezentând șirul $p$ — distanțele față de linia de start a pozițiilor de start din grilă.

Date de ieșire

Fișierul lemans.out va conține pe prima linie un singur număr, reprezentând valoarea minimă posibilă a diferenței maxime dintre distanțele parcurse de oricare două mașini. Pe a doua linie se vor afla $N$ numere între $1$ și $M$ separate prin câte un spațiu, al $i$-lea număr reprezentând poziția de start din grilă a mașinii cu numărul $i$.

Restricții și precizări

• $2 \leq N, M \leq 10^3$;
• $1 \leq T \leq 10^3$;
• $1 \leq v[i] \leq 10^6, \forall i\in \{1, 2, \dots, N\}$;
• $0 \leq p[i] \leq 10^9, \forall i, j\in \{1, 2, \dots, M\}$;
• Două sau mai multe mașini pot porni de pe aceeași poziție din grila de start;
• În grilă pot exista și poziții neocupate de o mașină;
• Pot exista mai multe distribuții ale mașinilor pe grila de start, ce oferă o soluție optimă. Se acceptă orice soluție corectă.

Exemplu

lemans.in

5 4 3
2 3 4 5
7 1 11

lemans.out

5
3 1 2 2

Explicație

Distanța minimă posibilă este $5$ și se poate obține astfel:

• Mașina $1$ pleacă de pe poziția $3$, deci va parcurge $p[3] + v[1] \cdot 5 = 11 + 2 \cdot 5 = 21$ metri;
• Mașina $2$ pleacă de pe poziția $1$, deci va parcurge $p[1] + v[2] \cdot 5 = 7 + 3 \cdot 5 = 22$ metri;
• Mașina $3$ pleacă de pe poziția $2$, deci va parcurge $p[2] + v[3] \cdot 5 = 1 + 4 \cdot 5 = 21$ metri;
• Mașina $4$ pleacă de pe poziția $2$, deci va parcurge $p[2] + v[4] \cdot 5 = 1 + 5 \cdot 5 = 26$ metri.