Sereja has two sequences a and b and number p. Sequence a consists of n integers a_1, a_2, ..., a_{n}. Similarly, sequence b consists of m integers b_1, b_2, ..., b_{m}. As usual, Sereja studies the sequences he has. Today he wants to find the number of positions q (q + (m - 1)·p ≤ n; q ≥ 1), such that sequence b can be obtained from sequence a_{q}, a_{q} + p, a_{q} + 2p, ..., a_{q} + (m - 1)p by rearranging elements.

Sereja needs to rush to the gym, so he asked to find all the described positions of q.


-----Input-----

The first line contains three integers n, m and p (1 ≤ n, m ≤ 2·10^5, 1 ≤ p ≤ 2·10^5). The next line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9). The next line contains m integers b_1, b_2, ..., b_{m} (1 ≤ b_{i} ≤ 10^9).


-----Output-----

In the first line print the number of valid qs. In the second line, print the valid values in the increasing order.


-----Examples-----
Input
5 3 1
1 2 3 2 1
1 2 3

Output
2
1 3

Input
6 3 2
1 3 2 2 3 1
1 2 3

Output
2
1 2

Difficulty: HARD
Tags: Sorting

Data structures
Skill types: Sorting

Data structures

Starter code:

Solutions:
from sys import stdin, stdout
from math import log, sqrt
lines = stdin.readlines()
n = int(lines[0].split()[0])
m = int(lines[0].split()[1])
p = int(lines[0].split()[2])
a = [int(x) for x in lines[1].split()]
b = [int(x) for x in lines[2].split()]

def hash_elem(x):
	x = x * 1662634645 + 32544235 & 4294967295
	x = (x >> 13) + (x << 19) & 4294967295
	x = x * 361352451 & 4294967295
	return x
c = [hash_elem(elem) for elem in a]
c_new = [sum([c[q + p * i] for i in range(m)]) for q in range(min(p, max(0, n - (m - 1) * p)))]
for q in range(p, n - (m - 1) * p):
	prev = c_new[q - p]
	c_new.append(prev - c[q - p] + c[q + p * (m - 1)])
b_check = sum([hash_elem(elem) for elem in b])
ans1 = 0
ans = []
for q in range(n - (m - 1) * p):
	c_check = c_new[q]
	if b_check != c_check:
		continue
	else:
		ans1 += 1
		ans.append(q + 1)
print(ans1)
stdout.write(' '.join([str(x) for x in ans]))


from collections import Counter
(n, m, p) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

def try_from(start, a, b):
	result = []
	seq = a[start::p]
	i = 0
	if len(seq) < len(b):
		return []
	counts_a = Counter(seq[:len(b)])
	counts_b = Counter(b)
	if counts_a == counts_b:
		result.append(start)
	for i in range(1, len(seq) - len(b) + 1):
		counts_a[seq[i - 1]] -= 1
		counts_a[seq[i + len(b) - 1]] += 1
		if not counts_a[seq[i - 1]]:
			del counts_a[seq[i - 1]]
		ok = counts_a == counts_b
		if ok:
			result.append(start + p * i)
	return [x + 1 for x in result]
result = []
for start in range(p):
	result += try_from(start, a, b)
print(len(result))
print(' '.join(map(str, sorted(result))))


from collections import defaultdict
(n, m, p) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
u = defaultdict(int)
for i in b:
	u[i] += 1
ans = []
for q in range(p):
	c = a[q:n:p]
	if len(c) < m:
		break
	v = defaultdict(int)
	for i in c[:m]:
		v[i] += 1
	d = q + 1
	if u == v:
		ans.append(d)
	for (j, k) in zip(c[:len(c) - m], c[m:]):
		v[j] -= 1
		if v[j] == 0:
			v.pop(j)
		v[k] += 1
		d += p
		if u == v:
			ans.append(d)
ans.sort()
print(len(ans))
print(' '.join(map(str, ans)))


from collections import defaultdict, Counter

def solve(n, m, p, a, b):
	ans = []
	cb = Counter(b)
	for q in range(min(p, n - (m - 1) * p)):
		arr = [a[i] for i in range(q, n, p)]
		lb = len(cb.keys())
		cnt = cb.copy()
		for v in arr[:m]:
			cnt[v] -= 1
			if cnt[v] == 0:
				lb -= 1
			elif cnt[v] == -1:
				lb += 1
		j = 0
		if lb == 0:
			ans.append(q + 1)
		for (i, v) in enumerate(arr[m:], m):
			cnt[v] -= 1
			if cnt[v] == 0:
				lb -= 1
			elif cnt[v] == -1:
				lb += 1
			cnt[arr[j]] += 1
			if cnt[arr[j]] == 0:
				lb -= 1
			elif cnt[arr[j]] == 1:
				lb += 1
			j += 1
			if lb == 0:
				ans.append(q + j * p + 1)
	print(len(ans))
	print(*sorted(ans))
(n, m, p) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
solve(n, m, p, a, b)


from sys import stdin, stdout
from math import log, sqrt
lines = stdin.readlines()
n = int(lines[0].split()[0])
m = int(lines[0].split()[1])
p = int(lines[0].split()[2])
a = [int(x) for x in lines[1].split()]
b = [int(x) for x in lines[2].split()]
hash_map = {}

def hash_elem(elem):
	if hash_map.get(elem, -1) == -1:
		if elem < 1000:
			hash_map[elem] = elem // 2 + elem * 1134234546677 + int(elem / 3) + int(elem ** 2) + elem << 2 + elem >> 7 + int(log(elem)) + int(sqrt(elem)) + elem & 213213 + elem ^ 324234211323 + elem | 21319423094023
		else:
			hash_map[elem] = 3 + elem ^ 34
	return elem + hash_map[elem]
c = [hash_elem(elem) for elem in a]
c_new = [sum([c[q + p * i] for i in range(m)]) for q in range(min(p, max(0, n - (m - 1) * p)))]
for q in range(p, n - (m - 1) * p):
	prev = c_new[q - p]
	c_new.append(prev - c[q - p] + c[q + p * (m - 1)])
b_check = sum([hash_elem(elem) for elem in b])
ans1 = 0
ans = []
for q in range(n - (m - 1) * p):
	c_check = c_new[q]
	if b_check != c_check:
		continue
	else:
		ans1 += 1
		ans.append(q + 1)
print(ans1)
stdout.write(' '.join([str(x) for x in ans]))