Museum Tour

Interview

Time limit2sMemory limit1024 MB

Summary

Given each kitten's viewing order, find the hall where the entrance minimizes the total walking distance for all kittens, choosing the smallest number on ties.

Level: Medium4 of 10
Topics: Prefix sum, Greedy, Array
Solved: No attempts yet

Problem

$N$ kittens are going on a museum tour, and each has planned the order in which to view the exhibits. The museum is a row of $M$ exhibit halls, and the $i$ -th hall from the left holds exhibit $i$ . $(1 \le i \le M)$

Every kitten enters through the entrance, views the exhibits in the order it wants, and then leaves through the entrance. The distance between the $i$ -th and $j$ -th halls is $|j - i|$ .

Chunbae

Chunbae, the museum director, wants to place the entrance in one of the $M$ halls. Chunbae wants the spot where the sum of all kittens' travel distances is smallest, but the museum is large and choosing that spot is hard.

Given the viewing plans of the $N$ kittens, write a program that computes where the entrance should be placed.

Input

The first line contains $N$ and $M$ , separated by a space. $(2 \le N, M \le 200\,000)$

The next $N$ lines describe the kittens' viewing plans. Each line has the following form.

$k\ p\_1\ p\_2\ \cdots\ p\_k$ : the kitten enters through the entrance, views exhibits $p\_1, p\_2, \cdots, p\_k$ in that order, and then leaves through the entrance. $(2 \le k \le 10$ , $1 \le p\_i \le M)$

Output

Print the number of the exhibit hall where the entrance should be placed. If several halls work, print the smallest number.

Examples1

Example 1
Input
```
3 5
3 1 2 4
3 3 4 2
3 3 5 4
```
Expected output
```
3
```