問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!
paiza 君は、n 個のマスからなる環状のすごろく Ginopoly を手に入れました。このすごろくのそれぞれのマスには、時計回りに 1, 2, ..., n と番号が振られており、i 番目のマスには整数 a_i が書かれています。このすごろくは、サイコロの出目に応じて時計回りに進むことができます。
しかしなんと、このすごろくについてきたサイコロは少し特殊で、出目が 1 ~ m, 分布が b_1, b_2, ..., b_m の m 面サイコロになっており、出目 i が出る確率は b_i / (b_1 + b_2 + ... + b_m) となっていました。
paiza 君は、ここで、ふとある疑問を思いつきました。
「あるマスに止まったとき、そこでサイコロを振った場合に到達可能なマスに書かれている数字の分布と、サイコロの分布が等しいようなマスは存在するのだろうか?」
しかし、paiza 君は数学が苦手なので、この問題の答えを求めることができません。そこで、paiza 君の代わりに、この問題の答えを求めるプログラムを作成してください。
具体的には、以下のような条件をすべて満たす整数 x をすべて求め、昇順で出力してください。ただし、a_{n + i} = a_i であるものとします。(1 ≦ i ≦ n)
・ 1 ≦ x ≦ n
・ すべての i (1 ≦ i ≦ m) に対して、以下の 2 つの値が等しい
1. マスに書かれた数字の分布 a_{x + i} / (a_{x + 1} + a_{x + 2} + ... + a_{x + m})
2. サイコロの分布 b_i / (b_1 + b_2 + ... + b_m)
たとえば、n = 3, m = 2, a =〈1, 2, 4〉, b =〈1, 2〉 のとき、以下のようになります。
サイコロの分布は〈1 / (1 + 2), 2 / (1 + 2)〉=〈1 / 3, 2 / 3〉です。
x = 1 のとき、マスの分布は〈2 / (2 + 4), 4 / (2 + 4)〉=〈1 / 3, 2 / 3〉となり、サイコロの分布に一致します。
x = 2 のとき、マスの分布は〈4 / (4 + 1), 1 / (4 + 1)〉=〈4 / 5, 1 / 5〉となり、サイコロの分布に一致しません。
x = 3 のとき、マスの分布は〈1 / (1 + 2), 2 / (1 + 2)〉=〈1 / 3, 2 / 3〉となり、サイコロの分布に一致します。
よって、答えは x = 1, 3 となります。
n m
a_1 a_2 ... a_n
b_1 b_2 ... b_m
条件を満たす整数 i をすべて昇順に 1 行ずつ出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ m ≦ n ≦ 100000 = 10^5
・ 1 ≦ a_i ≦ 1000000000 = 10^9 (1 ≦ i ≦ n)
・ 1 ≦ b_i ≦ 1000000000 = 10^9 (1 ≦ i ≦ m)
5 2
1 2 4 8 16
1 2
1
2
3
5