C. Инна ба чихрийн хайрцаг

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

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

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

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

Инна амттанд маш их дуртай. Түүний урд нэг мөрөнд өрсөн $n$ ширхэг задлаагүй бэлэгний хайрцаг байна. Эдгээр хайрцаг бүр нэг бол чихэр агуулсан (Димагийн ажил) эсвэл юу ч байхгүй (Сережагийн ажил). Хайрцагууд зүүнээс баруун тийш 1-ээс $n$ хүртэл дугаарлагдсан гэж бод.

Хайрцагнууд задлаагүй байгаа учир Инна аль хайрцагт чихэр байгаа аль хайрцагт юу ч байхгүй вэ гэдгийг мэдэхгүй. Инна $k$ тоог сонгосон ба Димагаас $w$ асуултыг асуусан. Асуулт бүр хоёр бүхэл тоон утгаар тодорхойлогдоно: $l_{i}, r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$; $r - l + 1$ нь $k$-д хуваагдана), $i$ дугаар асуулт бол: "Дима $l_{i}$-аас $r_{i}$ дугаартай хайрцагнууд дунд $l_{i} + k - 1$, $l_{i} + 2k - 1$, $l_{i} + 3k - 1$, ..., $r_{i}$ дугаартай хайрцагнуудад л зөвхөн чихэр байрлаж байгаа нь үнэн үү?"

Дима бол гайхалтай яагаад гэвэл тэр Иннад "үгүй" гэж хэлэх дургүй. Асуулт бүрт эерэг хариулт өгөхийн тулд Дима хэдэн үйлдэл хийх хэрэгтэй вэ. Дима нэг үйлдлээр нууцаар ямар ч хайрцагнаас чихрийг авч чадах ба ямар ч хайрцаганд чихрийг хийж чадна(Димад хангалттай олон чихэр бий). Димад Иннагийн асуулт бүрт хэрэгтэй үйлдлийн тоог тоолоход туслана уу.

Иннагийн асуултын үед Дима дарааллыг өөрчилж чадахгүй. Ийм учир тухайн асуултын үед та үйлдлийн тоог тооцоолох хэрэгтэй, мөн хайрцагнуудын дараалал өөрчлөгдөхгүй.

Оролт

Оролтын эхний мөр нь гурван ширхэг бүхэл тоон утга агуулах ба эдгээр нь $n$, $k$, $w$ $(1 ≤ k ≤ min(n, 10), 1 ≤ n, w ≤ 10^{5})$. Оролтын хоёр дахь мөрөнд $n$ ширхэг тэмдэгт байна. Хэрвээ $i$-р хайрцаг чихэр агуулсан бол мөрийн $i$-р тэмдэгт 1 байна бусад тохиолдолд 0 байна.

Дараагийн $w$ мөрүүдийн мөр бүр хоёр бүхэл тоон утга $l_{i}$ ба $r_{i}$ $(1 ≤ l_{i} ≤ r_{i} ≤ n)$ агуулах ба энэ хоёр тоо нь $i$-р асуултыг тодорхойлно. $r_{i} - l_{i} + 1$ нь $k$ тоонд хуваагдах ёстой.

Гаралт

Асуулт бүр нэг шинэ мөрөнд нэг тоо хэвлэнэ. Уг тоо нь асуултын хариуг эерэг болгохын тулд Димагийн хийх хэрэгтэй үйлдлүүдийн байж болох хамгийн бага тоо байна.

Орчуулсан: Г.Мэндбаяр

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

Оролт
10 3 3
1010100011
1 3
1 6
4 9
Гаралт
1
3
2

Тэмдэглэл

Эхний асуултан дээр та эхний хайрцагнаас чихрийг авч хариуг эерэг болгоно иймд хариулт нь 1.

Хоёр дахь асуултан дээр та эхний хайрцагнаас чихрийг авна, тав дахь хайрцагнаас чихрийг авч зургаа дахь хайрцаганд хийнэ. Иймд хариулт нь 3.

Гурав дахь асуултан дээр та тав дахь хайрцагнаас чихрийг авч зургаа дахь хайрцаганд хийнэ. Иймд хариулт нь 2.

Сэтгэгдлүүдийг ачааллаж байна...