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 ≥ n ⋅ 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?

Input

The first line contains four integers m, k, n and s (1 ≤ n, k, m ≤ 5 ⋅ 10^5, k ⋅ n ≤ m, 1 ≤ s ≤ 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 ≤ a_i ≤ 5 ⋅ 10^5) — types of flowers on the liana.

The third line contains s integers b_1, b_2, ..., b_s (1 ≤ b_i ≤ 5 ⋅ 10^5) — the sequence in Diana's schematic.

Output

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.

Examples

Input


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


Output


1
4 


Input


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


Output


-1


Input


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


Output


9
1 2 3 4 5 9 11 12 13

Note

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.

Difficulty: HARD
Tags: Amortized analysis

Implementation

Greedy algorithms
Skill types: Amortized analysis

Greedy algorithms

Starter code:

Solutions:
def main():
	(m, k, n, s) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	b_dict = {}
	for x in b:
		b_dict.setdefault(x, 0)
		b_dict[x] += 1
	left = 0
	right = 0
	max_cut = m - n * k
	condition_not_met = len(b_dict)
	a_dict = {}
	while right < m and condition_not_met > 0:
		x = a[right]
		a_dict.setdefault(x, 0)
		a_dict[x] += 1
		if x in b_dict and a_dict[x] == b_dict[x]:
			condition_not_met -= 1
		right += 1
	if condition_not_met > 0:
		print(-1)
		return

	def num_to_remove(lft, rgt):
		lft = lft // k * k
		num_in_seq = rgt - lft
		if num_in_seq < k:
			return 0
		return num_in_seq - k

	def test_plan():
		nonlocal left
		if num_to_remove(left, right) <= max_cut:
			tot = num_to_remove(left, right)
			print(tot)
			left = left // k * k
			while tot > 0:
				x = a[left]
				if x in b_dict:
					b_dict[x] -= 1
					if b_dict[x] == 0:
						del b_dict[x]
				else:
					print(left + 1, end=' ')
					tot -= 1
				left += 1
			return True
		return False
	while True:
		while left < right:
			x = a[left]
			if x in b_dict and a_dict[x] - 1 < b_dict[x]:
				break
			else:
				a_dict[x] -= 1
				if a_dict[x] == 0:
					del a_dict[x]
				left += 1
		if test_plan():
			return
		if right < m:
			a_dict.setdefault(a[right], 0)
			a_dict[a[right]] += 1
			right += 1
		else:
			break
	print(-1)
main()


(m, k, n, s) = map(int, input().split())
ls = list(map(int, input().split()))
seq = map(int, input().split())
dseq = {}
for se in seq:
	if se not in dseq:
		dseq[se] = 0
	dseq[se] += 1
maxwindowsize = m - k * n + k
dcurr = {}
nrusefull = 0
for i in range(maxwindowsize - k):
	if ls[i] not in dcurr:
		dcurr[ls[i]] = 0
	dcurr[ls[i]] += 1
	if ls[i] in dseq and dseq[ls[i]] >= dcurr[ls[i]]:
		nrusefull += 1
for j in range(m):
	if j % k == 0 and j + k <= m:
		mini = maxwindowsize + j - k
		for i in range(mini, min(mini + k, m)):
			if ls[i] not in dcurr:
				dcurr[ls[i]] = 0
			dcurr[ls[i]] += 1
			if ls[i] in dseq and dseq[ls[i]] >= dcurr[ls[i]]:
				nrusefull += 1
	if nrusefull == s:
		printl = []
		dlast = {x: 0 for x in dcurr}
		for x in range(j, j + maxwindowsize):
			if len(printl) == maxwindowsize - k:
				break
			dlast[ls[x]] += 1
			if ls[x] not in dseq or dseq[ls[x]] < dlast[ls[x]]:
				printl.append(str(x + 1))
		break
	dcurr[ls[j]] -= 1
	if ls[j] in dseq and dcurr[ls[j]] < dseq[ls[j]]:
		nrusefull -= 1
else:
	print(-1)
	raise SystemExit()
print(len(printl))
print(' '.join(printl))


from sys import stdin, stdout, setrecursionlimit
input = stdin.readline
inf = float('inf')
from functools import cmp_to_key
from collections import defaultdict as dd
from collections import Counter, deque
from heapq import *
import math
from math import floor, ceil, sqrt

def geti():
	return map(int, input().strip().split())

def getl():
	return list(map(int, input().strip().split()))

def getis():
	return map(str, input().strip().split())

def getls():
	return list(map(str, input().strip().split()))

def gets():
	return input().strip()

def geta():
	return int(input())

def print_s(s):
	stdout.write(s + '\n')

def solve():
	(m, k, n, s) = geti()
	a = getl()
	s = Counter(getl())
	length = k + m - n * k
	val = sum(s.values())
	occur = dd(int)
	ok = 0
	i = 0
	done = 0
	start = 0
	while i < m:
		while done != length and i < m:
			occur[a[i]] += 1
			if occur[a[i]] == s[a[i]]:
				ok += 1
			done += 1
			i += 1
		if ok == len(s):
			res = []
			need = length - k
			for j in range(start, start + length):
				if not need:
					break
				if occur[a[j]] > s[a[j]]:
					occur[a[j]] -= 1
					res.append(j + 1)
					need -= 1
			print(len(res))
			print(*res)
			break
		else:
			waste = k
			while waste:
				if occur[a[start]] == s[a[start]]:
					ok -= 1
				occur[a[start]] -= 1
				waste -= 1
				start += 1
				done -= 1
	else:
		print(-1)
solve()


(m, k, n, s) = map(int, input().split())
fl = [int(x) for x in input().split()]
seq = [int(x) for x in input().split()]
d = {}
p = {}
for i in seq:
	d[i] = d.get(i, 0) + 1
	p[i] = d[i]
f = False
collect = s
keys = set(d.keys())
l = 0
r = -1
c = 0
while r != m:
	if collect:
		r += 1
		if r == m:
			break
		if fl[r] in keys:
			d[fl[r]] -= 1
			if d[fl[r]] >= 0:
				collect -= 1
	else:
		l += 1
		if fl[l - 1] in keys:
			d[fl[l - 1]] += 1
			if d[fl[l - 1]] > 0:
				collect += 1
	out = l % k + (r - l + 1 - k)
	if not collect and n * k <= m - out:
		f = True
		print(max(0, out))
		for j in range(l, r + 1):
			if c == max(0, out):
				break
			if fl[j] not in keys or p[fl[j]] == 0:
				print(j + 1, end=' ')
				c += 1
			else:
				p[fl[j]] -= 1
		break
if not f:
	print(-1)


from math import *
import os, sys
from decimal import Decimal as db
from bisect import *
from io import BytesIO
from queue import Queue
from heapq import *
(m, k, n, s) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d = {}
p = {}
kol = s
for c in b:
	d[c] = d.get(c, 0) + 1
	p[c] = d[c]
l = 0
r = -1
c = 0
while r < m:
	if kol:
		r += 1
		if r == m:
			break
		if a[r] in d:
			d[a[r]] -= 1
			if d[a[r]] >= 0:
				kol -= 1
	else:
		l += 1
		if a[l - 1] in d:
			d[a[l - 1]] += 1
			if d[a[l - 1]] > 0:
				kol += 1
	tmp = l % k + r - l - k + 1
	if not kol and n * k <= m - tmp:
		print(max(0, tmp))
		for i in range(l, r + 1):
			if c == max(0, tmp):
				exit(0)
			if a[i] not in d or p[a[i]] == 0:
				print(i + 1, end=' ')
				c += 1
			else:
				p[a[i]] -= 1
		exit(0)
print(-1)


import sys
from collections import Counter
input = sys.stdin.buffer.readline
(m, k, n, s) = map(int, input().split())
a = list(map(int, input().split()))
b = Counter(map(int, input().split()))
counts = Counter()
unsatisfied = len(b)
to_remove = m + 1
mn_len = m + 1
remove_idx = -1
j = 0
for i in range(m):
	while j < m and unsatisfied != 0:
		counts[a[j]] += 1
		if counts[a[j]] == b[a[j]]:
			unsatisfied -= 1
		j += 1
	if unsatisfied == 0:
		curr_remove = i % k + max(0, j - i - k)
		if curr_remove < to_remove:
			to_remove = curr_remove
			mn_len = j - i
			remove_idx = i
	if counts[a[i]] == b[a[i]]:
		unsatisfied += 1
	counts[a[i]] -= 1
if m - to_remove < n * k:
	print(-1)
else:
	print(to_remove)
	indexes = {}
	for i in range(remove_idx, remove_idx + mn_len):
		if a[i] in indexes:
			indexes[a[i]].append(i + 1)
		else:
			indexes[a[i]] = [i + 1]
	removed = list(range(1, remove_idx % k + 1))
	to_remove -= remove_idx % k
	for i in indexes:
		if to_remove == 0:
			break
		else:
			removed.extend(indexes[i][:min(len(indexes[i]) - b[i], to_remove)])
			to_remove -= min(len(indexes[i]) - b[i], to_remove)
	print(*removed)