Евгенийд $n$ бүхэл тоонуудаас бүрдсэн $a = a_{1}, a_{2}, ..., a_{n}$ массив байгаа. Бүхэл $a_{i}$ тоо бүр нь -1 эсвэл 1-тэй тэнцүү. Энэ массивтай холбоотой $m$ ширхэг хүсэлт ирсэн байна:

• $i$-р хүсэлтэд $l_{i}$, $r_{i}$ $(1 ≤ l_{i} ≤ r_{i} ≤ n)$ гэсэн хоёр бүхэл хос тоо өгөгдөнө.
• Хэрэв тухайн хүсэлтийн хувьд $a_{l_{i}} + a_{l_{i} + 1} + ... + a_{r_{i}} = 0$ нөхцөл биелэж байвал хариулт нь $1$ үгүй бол $0$ байна.

Евгенийд бүх хүсэлтэд хариулахад нь туслаарай.

Оролт

Эхний мөрөнд бүхэл $n$ ба $m$ $(1 ≤ n, m ≤ 2*10^{5})$ тоонууд агуулагдана. Хоёр дахь мөрөнд $n$ ширхэг бүхэл $a_{1}, a_{2}, ..., a_{n}$ $(a_{i} = $-$1, 1)$ тоонууд агуулагдана. Дараагийн $m$ ширхэг мөрөнд хүсэлтүүд байна. $i$-р мөрөнд бүхэл $l_{i}, r_{i}$ $(1 ≤ l_{i} ≤ r_{i} ≤ n)$ тоонууд агуулагдана.

Гаралт

$m$ мөрөнд мөр бүрд харгалзах хүсэлтийн хариу.