G. Design Tutorial: Хязгаарлалтуудыг нэмэгдүүлэх

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

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

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

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

Хүнд бодлого зохиох аргуудын нэг нь, энгийн бодлого аваад түүнийгээ илүү хурдан алгоритм зохиож бодох хэрэгтэй болгох юм. Ерөнхийдөө ийм төрлийн даалгавар OI тэмцээнд харагддаг ба ихэвчлэн өгөгдлийн бүтэцтэй холбоотой байдаг.

Бид ч гэсэн ийм аргаар бодлого зохиохын тулд жишээ болгож "Хэммингийн зайн бодлого"-г авч үзье. Хэммингийн зай гэдэг нь ижил урттай $s$ ба $t$ тэмдэгт мөрүүдийн хоёртын (бинар) бичиглэл дэх харгалзсан байрлал дахь ялгаатай тэмдэгтүүдийн тоо юм.

Жишээлбэл, "00111" ба "10101" тэмдэгт мөрүүдийн хоорондох Хэммингийн зай нь 2-той тэнцүү (ялгаатай тэмдэгтүүдийг тодоор тэмдэглэсэн).

Бид "Хэммингийн зайн бодлого"-ыг дараах байдлаар ашиглана. Танд $a$, $b$ хоёр тэмдэгт мөр болон хэд хэдэн хүсэлтүүд өгөгдөнө. Хүсэлт бүр дараах байдлаар өгөгдөнө:

$a_{p_{1}}a_{p_{1} + 1}...a_{p_{1} + len - 1}$ ба $b_{p_{2}}b_{p_{2} + 1}...b_{p_{2} + len - 1}$ хоёр тэмдэгт мөрийн хоорондох Хэммингийн зай хэд байх вэ?

Энэ бодлогонд тэмдэгт мөр $s = s_{0}s_{1}... s_{|s| - 1}$ гэсэн тэг суурьтайг анхаарна уу .

Оролт

Эхний мөр $a$ $(1 ≤ |a| ≤ 200000)$ тэмдэгт мөрийг, хоёр дахь мөр $b$ $(1 ≤ |b| ≤ 200000)$ тэмдэгт мөрийг агуулна. Хоёр тэмдэгт мөрийн тэмдэгтүүд нь "0" эсвэл "1" байна.

Гурав дахь мөрөнд хүсэлтүүдийн тоо болох $q$ $(1 ≤ q ≤ 400000)$ бүхэл тоо байна. Үүний дараа $q$ мөрүүд байх ба мөр бүр гурван бүхэл тоо агуулна: $p_{1}$, $p_{2}$, $len$. Эдгээр тоонууд нь хүсэлтийн параметрүүдийг илэрхийлнэ. $(0 ≤ p_{1} ≤ |a| - len; 0 ≤ p_{2} ≤ |b| - len)$

Гаралт

Хүсэлтүүдийн хариултууд болох $q$ бүхэл тоо хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
101010
11110000
3
0 0 3
2 3 4
5 7 1
Гаралт
1
1
0
Оролт
10001010101011001010100101010011010
101010100101001010100100101010
5
0 0 12
3 9 7
6 4 15
12 15 10
13 3 20
Гаралт
5
4
3
5
13
Сэтгэгдлүүдийг ачааллаж байна...