박물관 견학

면접 대비

시간 제한2초메모리 제한1024 MB

요약

각 아이의 관람 순서를 보고, 입구를 두었을 때 모든 아이의 이동 거리 합이 가장 작은 전시관 번호를 찾습니다. 같은 값이면 가장 작은 번호를 출력합니다.

문제

$N$ 마리의 아기 고양이가 박물관 견학을 가려고 하며, 각 고양이는 전시를 관람할 순서를 미리 계획했다. 박물관은 전시관 $M$ 개가 일렬로 붙어 있고, 왼쪽에서 $i$ 번째 전시관에서는 전시 $i$ 가 진행된다. $(1 \le i \le M)$

모든 아기 고양이는 출입구로 입장한 뒤, 원하는 순서대로 전시를 관람하고 출입구로 퇴장한다. $i$ 번째 전시관과 $j$ 번째 전시관 사이의 이동 거리는 $|j - i|$ 이다.

왕 춘배

박물관 관장 춘배는 $M$ 개 전시관 중 한 곳에 출입구를 설치하려고 한다. 모든 아기 고양이의 이동 거리 합이 최소가 되는 곳에 설치하고 싶지만, 박물관이 커서 설치 위치를 정하기 어려워하고 있다.

$N$ 마리 고양이의 관람 계획이 주어졌을 때, 출입구를 설치할 위치를 계산하는 프로그램을 만들어 보자.

첫 번째 줄에 $N$ 과 $M$ 이 공백으로 구분되어 주어진다. $(2 \le N, M \le 200\,000)$

두 번째 줄부터 $N$ 개의 줄에 걸쳐 고양이들의 관람 계획이 주어진다. 각 계획은 다음 형태로 한 줄에 주어진다.

$k\ p\_1\ p\_2\ \cdots\ p\_k$ : 고양이가 출입구로 들어온 뒤 $p\_1, p\_2, \cdots, p\_k$ 순서대로 전시를 관람하고 출입구로 나간다. $(2 \le k \le 10$ , $1 \le p\_i \le M)$

출입구를 설치할 전시관 번호를 출력한다. 가능한 곳이 여러 곳이면 번호가 가장 작은 곳을 출력한다.