CF201D Brand New Problem

在白俄罗斯的一些程序员中颇有名气的 Lesha 决定赚点钱，好买一套大一平方米的公寓。为了实现这个目标，他想在 Torcoder.com 网站上策划并举办一场超级评分赛（SRM）。但问题是 Torcoder 严格的审核 Ivan 不接受 Lesha 的任何一个问题，还用带有冒犯性的词“duped”（即“重复的”）称呼每个问题。有一天，他们因为 Ivan 又一次拒绝接受 Lesha 的问题而差点吵起来。 现在请你充当公正的裁判，判断这个问题是否真的是全新的还是这个问题和之前 SRM 中用过的问题有相似之处。 你会得到 Lesha 的问题描述以及 Torcoder.com 存档中每个问题的描述。每个问题的描述都是一个单词序列。此外，可以确定的是， Lesha 的问题中没有重复的单词，而存档中问题的描述则可能包含任意数量的重复单词。 在 Lesha 的问题的所有单词排列中，选择一个能作为子序列出现在存档问题中的排列 $s_0$。如果有多个这样的排列，选择逆序数最少的那个 (逆序数即在 $s_0$ 的原排列与当前排列中相对位置发生改变的单词对数)。 Lesha 的问题与某个存档问题之间的相似度为 $p=\dfrac{n\times(n-1)}{2}-x+1$，$x$ 为满足条件的排列的逆序数。 现在需要你求出在 $m$ 个问题中与 Lesha 问题相似度最大的问题。若存在多个，则取编号最小的。

第一行包含一个整数 $n(1 \le n \le 15)$，表示 Lesha 的问题中的单词数量。 第二行包含 $n$ 个用空格分隔的单词，即该问题的简短描述。 第三行包含一个整数 $m(1 \le m \le 10)$，表示 Torcoder.com 存档中的问题数量。接下来 $m$ 行，每行描述一个问题，格式为 " $ k $ $ s_{1} $ $ s_{2} $ $ ... $ $ s_{k} $ "，其中 $k（1 \le k \le 5\times 10^5)$ 是该问题中的单词数量，$s_i$ 是该问题描述中的单词。 所有问题描述中的单词都由不超过 $10$ 个小写英文字母组成。保证所有问题描述中单词的总长度不超过 $500015$。

如果 Lesha 的问题是全新的，输出字符串 ```Brand new problem!```。 否则，第一行输出存档中与之最相似的问题的编号。如果有多个这样的问题，输出编号最小的那个。 第二行输出一个字符串，格式为 ```[:``` 紧接着 $p$ 个 ```|```，最后是```:]```，其中 $p$ 是该问题与莱沙的问题的相似度。存档中的问题按输入顺序从 $1$ 开始编号。

在第一个测试用例中，第一个问题包含```find the palindrome next```这个排列作为子序列，其中逆序数为 $1$（单词```palindrome```和```next```构成逆序对）。 在第二个测试用例中，没有任何问题包含莱沙的问题的单词的排列作为子序列。