عدد بوگندوی رشته‌ی خفن


  • محدودیت زمان: ۳ ثانیه
  • محدودیت حافظه: ۱۲۸ مگابایت

آرایه‌ای به طول nn داریم. هر عضو از این آرایه یک رشته به طول kk است که از ۰ و ۱ تشکیل شده است (رشته باینری به طول kk).

رشته خفن یک بازه از آرایه، یک رشته به طول kk است که بیت iiام آن برابر با ۱ است اگر حداقل یکی از رشته های بازه، بیت iiامش برابر با ۱ باشد.

عدد بوگندوی یک رشته برابر با تعداد بیت های ۱ آن است.

به شما qq درخواست داده می‌شود و در هر مرحله دو عدد l,rl,r داده می‌شود و شما باید عدد بوگندوی رشته خفن بازه [l,r][l,r] را چاپ کنید.

ورودی🔗

به دلیل حجم زیاد ورودی، ورودی به یک روش غیر معمول داده می‌شود:

در سطر اول سه عدد nn و mm و kk آمده است.

در mm خط بعدی، در هر خط ابتدا یک رشته kk بیتی sis_{i} آمده. سپس یک عدد cnticnt_{i} آمده و cnticnt_{i} عدد indexijindex_{ij} آمده که بیانگر این است که رشته موجود در خانه ی indexijindex_{ij} از آرایه برابر با sis_{i} است. تضمین می‌شود که هر خانه از آرایه دقیقا یکبار به عنوان indexindex ظاهر می‌شود.

در خط بعدی عدد qq آمده است. سپس در qq خط بعدی به شما درخواست‌ها به صورت دو عدد l,rl,r داده می‌شود که باید به آنها جواب دهید. 1lrn100 0001 \le l \le r \le n \le 100 \ 000 1m1 0001 \le m \le 1\ 000 1k3 0001 \le k \le 3\ 000 1q1 000 0001 \le q \le 1\ 000\ 000

خروجی🔗

در qq خط جواب هر درخواست را چاپ کنید.

مثال🔗

ورودی نمونه🔗

8 7 5
10001 1 5
10100 1 1
10001 1 3
00100 1 8
00011 1 7
11000 2 2 4
01110 1 6
8
8 8
1 3
3 5
5 6
8 8
6 8
8 8
3 6
Plain text

خروجی نمونه🔗

1
4
3
5
1
4
1
5
Plain text

اعضای آرایه به این صورت اند : 10100,11000,10001,11000,10001,01110,00011,0010010100,11000,10001,11000,10001,01110,00011,00100 در درخواست اول فقط عضو هشتم رشته آمده که تعداد بیت‌های ۱ اش برابر با یک است.

در درخواست دوم اعضای ۱ تا ۳ درون بازه اند. رشته‌ی خفن این بازه رقم های اول، دوم، سوم و پنجم اش برابر با ۱ اند.

در درخواست سوم اعضای ۳ تا ۵ درون بازه اند. رشته‌ی خفن این بازه رقم های اول، دوم و پنجم اش برابر با ۱ اند.