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: competition

Starter code:

Solutions:
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 Counter

n, m, p = list(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
        #ok = sorted(seq[i:i+len(b)]) == sorted(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))))





# Made By Mostafa_Khaled