乌龟大师有 $n$ 个双端队列，这些双端队列中的所有元素都是互不相同的。

阿宝想要成为神龙大侠，他需要用这些双端队列构建一个尽可能强大的数组。

在每一步中，他可以选择一个非空的双端队列（如果存在），并选择它的队首或队尾，将该值追加到数组的末尾，然后将该值从双端队列中弹出。请帮助他找到他能构建的最强大的数组。

一个数组的能量定义为它的最长上升子序列（LIS）的长度。

输入格式

输入的第一行包含一个整数 $n$，表示乌龟大师拥有的双端队列数量。

接下来的 $n$ 行中，第 $i$ 行包含一个整数 $k_i$，表示第 $i$ 个双端队列的大小，紧接着是 $k_i$ 个整数，表示第 $i$ 个双端队列中的元素。

输出格式

第一行输出你能获得的最大 LIS 长度。

第二行输出构建出的数组。如果存在多个满足条件的数组，输出其中任意一个即可。

数据范围

• $1 \le n \le 200\,000$
• $1 \le k_i \le 200\,000$
• $\sum_{i=1}^n k_i \le 200\,000$
• $a_{i_1, j_1} \ne a_{i_2, j_2}$ （对于不同的 $(i, j)$）
• $a_{i, j} \le 10^9$

子任务

样例

输入样例 1

3
4 7 2 3 5
3 1 11 9
4 10 4 8 6

输出样例 1

9
1 7 2 3 10 4 5 6 8 9 11