一位广为人知的白俄罗斯体育程序员Lesha决定赚点钱买一套大一平方米的公寓。为此,他想在 Torcoder.com 网站上制作并进行超级评分比赛 (SRM)。但有一个问题——严格的 Torcoder 协调员 Ivan 不接受 Lesha 的任何问题,称他们每个人都是冒犯性的词“欺骗”(即重复)。有一天,他们差点因为另一个伊万无法接受的问题而争吵起来。
请您充当公正的法官,确定该问题是否确实是全新的,或者 Ivan 是正确的并且该问题与以前的 SRM 中使用的问题有些相似。
您将获得 Lesha 问题和每个 Torcoder.com 存档问题的描述。每个问题的描述都是一个单词序列。此外,保证Lesha的问题没有重复的单词,而存档问题的描述可能包含任意数量的重复单词。
Lesha的问题和一些存档问题之间的“相似之处”可以发现如下。在 Lesha 问题中的所有单词排列中,我们选择档案问题中出现的一个作为子序列。如果存在多个这样的排列,我们选择反转次数最少的一个。那么问题的“相似度”可以写为 $$p = \frac{n(n-1)}{2} - x + 1$$,其中 n 是 Lesha 问题中的单词数,x 是所选排列中的反转数。请注意,“相似度”p 始终是正整数。
如果 Ivan 的档案中没有一个问题包含 Lesha 问题中的单词排列作为子序列,则该问题被称为全新问题。
帮助男孩们确定所提出的问题是否是新的,或者从档案中指定与 Lesha 的问题最相似的问题,否则。
输入
第一行包含一个整数 n (1 ≤ n ≤ 15) — Lesha 问题中的单词数。第二行包含 n 个空格分隔的单词——问题的简短描述。
第三行包含一个整数 m (1 ≤ m ≤ 10) — Torcoder.com 档案中的问题数量。接下来的 m 行包含问题的描述为“ks1 s2 ... sk”,其中 k (1 ≤ k ≤ 500000) 是问题中的单词数,si 是问题描述的单词。
所有问题描述中的所有单词包含的小写英文字母不超过 10 个。保证所有问题描述的字数总长度不超过500015。
输出
如果 Lesha 的问题是全新的,则打印字符串“Brand new Problem!” (不带引号)。
否则,在第一行打印与 Lesha 问题最相似的存档问题的索引。如果存在多个此类问题,则打印索引最小的一个。在第二行打印一个由字符 [:, 字符 | 组成的字符串。重复 p 次,并包含字符 :],其中 p 是该问题与 Lesha 问题之间的“相似度”。存档问题按照输入中给出的顺序从 1 开始编号。
示例
输入 #1
4 find the next palindrome 1 10 find the previous palindrome or print better luck next time
输出 #1
1 [:||||||:]
输入 #2
3 add two numbers 3 1 add 2 two two 3 numbers numbers numbers
输出 #2
Brand new problem!
输入 #3
4 these papers are formulas 3 6 what are these formulas and papers 5 papers are driving me crazy 4 crazy into the night
输出 #3
1 [:||||:]
输入#4
3 add two decimals 5 4 please two decimals add 5 decimals want to be added 4 two add decimals add 4 add one two three 7 one plus two plus three equals six
输出#4
3 [:|||:]
注意
让我们提醒您,倒装的数量是排列中遵循的单词对的数量,而不是按照其原始顺序。因此,例如,如果原始问题是“两个数字相加”,则排列“数字相加两个”包含两个反转——词对“数字”和“加”、“数字”和“二”。
序列 b1, b2, ..., bk 是序列 a1, a2, ..., an 的子序列,如果存在这样一组索引 1 ≤ i1 < i2 < ... < ik ≤ n 且 aij = bj (换句话说,如果可以通过删除 a 的一些元素从 a 获得序列 b)。
在第一个测试用例中,第一个问题包含“查找下一个回文”排列作为子序列,其中反转数等于 1(单词“回文”和“下一个”)。
在第二个测试用例中,不存在包含 Lesha 问题中的单词排列作为子序列的问题。