MN12-A. Oraliqdagi juftlar

Massiv va q ta so‘rov berilgan: har so‘rovda [l, r] oralig‘ida nechta juft son borligini toping. Har so‘rovni sikl bilan sanash ulgurmaydi — «juftmi?» belgilari ustida prefiks yig‘indi tuzing.

Kirish ma’lumotlari

n, keyin n ta son, keyin q, keyin q qatorda l va r (1 dan).

Chiqish ma’lumotlari

q qatorda javoblar.

Cheklovlar

1 ≤ n, q ≤ 2·10⁵, 1 ≤ aᵢ ≤ 10⁹