B. Серёжа ба анаграм

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Серёжад $a$ ба $b$ хоёр дараалал болон $p$ тоо байгаа. Дараалал $a$ нь $a_1, a_2, ..., a_n$ гэх $n$ ширхэг бүхэл тоонуудаас бүрдэнэ. Үүнтэй ижилээр, дараалал $b$ нь $b_1, b_2, ..., b_m$ гэх $m$ ширхэг бүхэл тоонуудаас бүрдэнэ. Серёжа өөрт байгаа эдгээр дарааллуудыг судлахаар шийджээ. Өнөөдөр тэрбээр $(q + (m - 1) · p ≤ n; q ≥ 1)$ дээрх нөхцөлд $b$ дарааллаас $a_q, a_{q + p}, a_{q + 2p}, ..., a_{q + (m-1)p}$ хэлбэртэй дарааллыг элэментийн байрлалуудыг сольсноор гарган авч болох $q$ тооны боломжит байрлал хэд байгааг мэдэхийг хүсч байна.

Серёжа заалруу хурдан очих ёстой тул таниас $q$ тооны боломжит байрлалуудыг олж өгөхийг хүсчээ.

Оролт

Эхний мөрөнд $n, m$ болон $p$ $(1 ≤ n,m ≤ 2·10^{5}, 1 ≤ p ≤ 2·10^{5})$ тоонууд өгөгдөнө. Дараагийн мөрөнд $n$ ширхэг $a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^{9})$ бүхэл тоонууд өгөгдөнө. Дараагийн мөрөнд $m$ ширхэг $b_1, b_2, ..., b_m (1 ≤ b_i ≤ 10^{9})$ бүхэл тоонууд өгөгдөнө.

Гаралт

Эхний мөрөнд боломжит $q$ тоо хэд байгааг хэвлэнэ. Хоёр дахь мөрөнөд, Боломжит утгуудыг өсөх дарааллар хэвлэнэ.

Орчуулсан: arigato_dl

Жишээ тэстүүд

Оролт
5 3 1
1 2 3 2 1
1 2 3
Гаралт
2
1 3
Оролт
6 3 2
1 3 2 2 3 1
1 2 3
Гаралт
2
1 2
Сэтгэгдлүүдийг ачааллаж байна...