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

---

آرایه‌ای به طول \(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\] در درخواست اول فقط عضو هشتم رشته آمده که تعداد بیت‌های ۱ اش برابر با یک است.

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

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