10144번 - Ciągi 다국어

W tym zadaniu rozważamy ciągi liczb całkowitych o długości n. Odległość między dwoma takimi ciągami A = (a₁, a₂, ..., a_n) oraz B = (b₁, b₂, ..., b_n) definiujemy jako:

d(A, B) = |a₁ - b₁| + |a₂ - b₂| + ... + |a_n - b_n|,

gdzie |x| oznacza wartość bezwzględną liczby x.

Mając dane k ciągów A₁, A₂, ..., A_k, Twoim zadaniem jest znaleźć ich centrum, czyli ciąg liczb całkowitych, dla którego wartość max{d(A_i, B) : i = 1, 2, ..., k} jest możliwie najmniejsza.

Pierwszy wiersz wejścia zawiera dwie liczby całkowite n oraz k (2 ≤ n ≤ 100 000, 2 ≤ k ≤ 5). Każdy z kolejnych k wierszy zawiera opis jednego z ciągów w postaci n liczb całkowitych nieprzekraczających co do wartości bezwzględnej 10⁹.

W testach wartych 1 punkt zachodzi warunek k ≤ 2. W testach wartych łącznie 3 punkty zachodzi warunek k ≤ 3. W testach wartych łącznie 6 punktów zachodzi warunek k ≤ 4.

Jedyny wiersz wyjścia powinien zawierać n liczb całkowitych pooddzielanych pojedynczymi odstępami, opisujących centrum podanych na wejściu ciągów. Jeśli jest więcej niż jedna poprawna odpowiedź, Twój program może wypisać dowolną z nich.