+ محدودیت زمان: ۳ ثانیه + **محدودیت حافظه: ۱۲۸ مگابایت** ---------------- آرایه‌ای به طول $n$ داریم. هر عضو از این آرایه یک رشته به طول $k$ است که از ۰ و ۱ تشکیل شده است (رشته باینری به طول $k$). **رشته خفن** یک بازه از آرایه، یک رشته به طول $k$ است که بیت $i$ام آن برابر با ۱ است اگر حداقل یکی از رشته های بازه، بیت $i$امش برابر با ۱ باشد. **عدد بوگندوی** یک رشته برابر با تعداد بیت های ۱ آن است. به شما $q$ درخواست داده می‌شود و در هر مرحله دو عدد $l,r$ داده می‌شود و شما باید عدد بوگندوی رشته خفن بازه $[l,r]$ را چاپ کنید. # ورودی به دلیل حجم زیاد ورودی، ورودی به یک روش غیر معمول داده می‌شود: در سطر اول سه عدد $n$ و $m$ و $k$ آمده است. در $m$ خط بعدی، در هر خط ابتدا یک رشته $k$ بیتی $s_{i}$ آمده. سپس یک عدد $cnt_{i}$ آمده و $cnt_{i}$ عدد $index_{ij}$ آمده که بیانگر این است که رشته موجود در خانه ی $index_{ij}$ از آرایه برابر با $s_{i}$ است. تضمین می‌شود که هر خانه از آرایه دقیقا یکبار به عنوان $index$ ظاهر می‌شود. در خط بعدی عدد $q$ آمده است. سپس در $q$ خط بعدی به شما درخواست‌ها به صورت دو عدد $l,r$ داده می‌شود که باید به آنها جواب دهید. $$1 \le l \le r \le n \le 100 \ 000$$ $$1 \le m \le 1\ 000$$ $$1 \le k \le 3\ 000$$ $$1 \le q \le 1\ 000\ 000$$ # خروجی در $q$ خط جواب هر درخواست را چاپ کنید. # مثال ## ورودی نمونه ``` 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 ``` ## خروجی نمونه ``` 1 4 3 5 1 4 1 5 ``` اعضای آرایه به این صورت اند : $$10100,11000,10001,11000,10001,01110,00011,00100$$ در درخواست اول فقط عضو هشتم رشته آمده که تعداد بیت‌های ۱ اش برابر با یک است. در درخواست دوم اعضای ۱ تا ۳ درون بازه اند. رشته‌ی خفن این بازه رقم های اول، دوم، سوم و پنجم اش برابر با ۱ اند. در درخواست سوم اعضای ۳ تا ۵ درون بازه اند. رشته‌ی خفن این بازه رقم های اول، دوم و پنجم اش برابر با ۱ اند.

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

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

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

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

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

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

ورودی🔗

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

در سطر اول سه عدد $n$ و $m$ و $k$ آمده است.

در $m$ خط بعدی، در هر خط ابتدا یک رشته $k$ بیتی $s_{i}$ آمده. سپس یک عدد $cnt_{i}$ آمده و $cnt_{i}$ عدد $index_{ij}$ آمده که بیانگر این است که رشته موجود در خانه ی $index_{ij}$ از آرایه برابر با $s_{i}$ است. تضمین می‌شود که هر خانه از آرایه دقیقا یکبار به عنوان $index$ ظاهر می‌شود.

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

خروجی🔗

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

مثال🔗

ورودی نمونه🔗

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

خروجی نمونه🔗

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

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

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