Diana and Liana

题意翻译

Shortriver 镇举办了传统的花卉节。小镇上的居民们在节日期间都会佩戴有 $k$ 朵花的花环。共 $n$ 位居民每人都会得到一个花环。 有一条藤蔓，上面有 $m$ 朵花，这条藤蔓是一个序列 $a$，$a_i$ 表示第 $i$ 朵花的类型。有一台机器来切割这条藤蔓，它会一直切下藤蔓前端的 $k$ 朵花，直到剩下的花数量不足 $k$。 Diana 制作了一个花环示意图，是一个长度为 $s$ 的序列 $b$。Diana 要按照这个示意图制作一个花环，要求机器切割下来的花环至少有一个包含序列 $b$ 里所有类型的花。**如果一种类型的花在此序列中出现多次，则该类型的花朵数量至少应为该序列中该花的出现次数。花朵的顺序无关紧要。** 为了制作这个花环，Diana 可以取下藤蔓上的一些花朵，但又要保证每个居民都能得到一个花环（**Diana 自己也算一位居民**）。请给出一种取下花朵的方案。 输入格式： 第一行包含四个整数 $m$，$k$，$n$ 和 $s$（$1\leq n,k,m\leq 5\times 10^5$，$k\times n\leq m$，$1\leq s \leq k$），分别表示藤蔓上的花数，一个花环中的花数，居民的数量和戴安娜的示意图序列长度。 第二行包含 $m$ 个整数 $a_1,a_2,a_3,\cdots ,a_m$（$1\leq a_i\leq 5\times 10^5$），表示藤蔓上的花朵类型。 第三行包含 $s$ 个整数 $b_1,b_2,b_3,\cdots ,b_s$（$1\leq b_i\leq 5\times 10^5$），表示示意图上的花朵类型。 输出格式： 如果无法达成 Diana 的要求，输出 $-1$。 否则在第一行输出一个整数 $d$，表示 Diana 要取下的花朵数量。在下一行输出 $d$ 个整数，表示要取下的花朵的位置。

题目描述

At the first holiday in spring, the town Shortriver traditionally conducts a flower festival. Townsfolk wear traditional wreaths during these festivals. Each wreath contains exactly $ k $ flowers. The work material for the wreaths for all $ n $ citizens of Shortriver is cut from the longest flowered liana that grew in the town that year. Liana is a sequence $ a_1 $ , $ a_2 $ , ..., $ a_m $ , where $ a_i $ is an integer that denotes the type of flower at the position $ i $ . This year the liana is very long ( $ m \ge n \cdot k $ ), and that means every citizen will get a wreath. Very soon the liana will be inserted into a special cutting machine in order to make work material for wreaths. The machine works in a simple manner: it cuts $ k $ flowers from the beginning of the liana, then another $ k $ flowers and so on. Each such piece of $ k $ flowers is called a workpiece. The machine works until there are less than $ k $ flowers on the liana. Diana has found a weaving schematic for the most beautiful wreath imaginable. In order to weave it, $ k $ flowers must contain flowers of types $ b_1 $ , $ b_2 $ , ..., $ b_s $ , while other can be of any type. If a type appears in this sequence several times, there should be at least that many flowers of that type as the number of occurrences of this flower in the sequence. The order of the flowers in a workpiece does not matter. Diana has a chance to remove some flowers from the liana before it is inserted into the cutting machine. She can remove flowers from any part of the liana without breaking liana into pieces. If Diana removes too many flowers, it may happen so that some of the citizens do not get a wreath. Could some flowers be removed from the liana so that at least one workpiece would conform to the schematic and machine would still be able to create at least $ n $ workpieces?

输入输出格式

输入格式

The first line contains four integers $ m $ , $ k $ , $ n $ and $ s $ ( $ 1 \le n, k, m \le 5 \cdot 10^5 $ , $ k \cdot n \le m $ , $ 1 \le s \le k $ ): the number of flowers on the liana, the number of flowers in one wreath, the amount of citizens and the length of Diana's flower sequence respectively. The second line contains $ m $ integers $ a_1 $ , $ a_2 $ , ..., $ a_m $ ( $ 1 \le a_i \le 5 \cdot 10^5 $ ) — types of flowers on the liana. The third line contains $ s $ integers $ b_1 $ , $ b_2 $ , ..., $ b_s $ ( $ 1 \le b_i \le 5 \cdot 10^5 $ ) — the sequence in Diana's schematic.

输出格式

If it's impossible to remove some of the flowers so that there would be at least $ n $ workpieces and at least one of them fullfills Diana's schematic requirements, output $ -1 $ . Otherwise in the first line output one integer $ d $ — the number of flowers to be removed by Diana. In the next line output $ d $ different integers — the positions of the flowers to be removed. If there are multiple answers, print any.

输入输出样例

输入样例 #1

7 3 2 2
1 2 3 3 2 1 2
2 2

输出样例 #1

1
4 

输入样例 #2

13 4 3 3
3 2 6 4 1 4 4 7 1 3 3 2 4
4 3 4

输出样例 #2

-1

输入样例 #3

13 4 1 3
3 2 6 4 1 4 4 7 1 3 3 2 4
4 3 4

输出样例 #3

9
1 2 3 4 5 9 11 12 13

说明

In the first example, if you don't remove any flowers, the machine would put out two workpieces with flower types $ [1, 2, 3] $ and $ [3, 2, 1] $ . Those workpieces don't fit Diana's schematic. But if you remove flower on $ 4 $ -th place, the machine would output workpieces $ [1, 2, 3] $ and $ [2, 1, 2] $ . The second workpiece fits Diana's schematic. In the second example there is no way to remove flowers so that every citizen gets a wreath and Diana gets a workpiece that fits here schematic. In the third example Diana is the only citizen of the town and that means she can, for example, just remove all flowers except the ones she needs.