سوسک کشی

تعدادی سوسک سیاه و سفید در تار عنکبوت غول پیکر گیر افتاده‌اند. تار عنکبوت غول پیکر به صورت شبکه‌ای مربعی به ضلع $N$ است و در هر یک از $N^2$ خانه آن سوسکی گیر افتاده است. یکی از بزرگترین لذت‌های عنکبوت غول پیکر در زندگی، له کردن سوسک‌های بیچاره است. زیرا وقتی سوسکی را له می‌کند،‌ آن سوسک منفجر شده و مواد سمی بدنش بر روی تعدادی از سوسک‌های سطر پایینی می‌ریزد که باعث انفجار آن‌ها نیز می‌شود و این روند تا سطر آخر ادامه پیدا می‌کند. می‌دانیم سوسک‌هایی که در سطر $i$ام قرار دارند به هنگام انفجار مواد سمی‌شان بر روی تمام سوسک‌هایی که در پایین قرار دارند و شماره ستون شان حداکثر $r_i$ تا با سوسک منفجر شده تفاوت دارد،‌ می‌ریزد. عنکبوت از شما خواسته به ازای هر موقعیت داده شده، تعداد سوسک‌های سیاهی را پیدا کنید که منفجر می‌شوند. در موقعیت $i$ام، عنکبوت سوسک‌های $s_i$ تا $e_i$ام سطر $row_i$ را له می‌کند.

• در خط اول ورودی $N$ اندازه‌ی ضلع شبکه تار عنکبوت آمده است ($1\leq N \leq 2000$)
• در خط بعد $N$ عدد آمده است که عدد $i$ام نشان‌دهنده‌ی $r_i$ است ($1\leq r_i \leq 2000$).
• در $N$ خط بعدی در هر خط یک رشته $N$ حرفی آمده است که حرف $j$ام رشته $i$ام آن X است اگر سوسکی که در سطر $i$ام و ستون $j$ام قرار دارد، سیاه باشد و . است اگر سفید باشد.
• در خط بعدی $q$ تعداد موقعیت‌ها آمده است ($1\leq q \leq 1000000$)
• در $q$ خط بعد، در هر خط به ترتیب سه عدد $row_i$ ،$s_i$ و $e_i$ آمده‌اند که به ترتیب سطر، ابتدا و انتهای بازه موقعیت $i$ام را مشخص می کنند ($1 \leq row_i \leq n, 1 \leq s_i \leq e_i \leq n$).
• در حداقل ۳۰ درصد از ورودی‌ها $1\leq N \leq 500$ است.

در $q$ سطر خروجی در سطر $i$ام تعداد سوسک‌های سیاهی که در موقعیت $i$ام منفجر می‌شوند را بنویسید.

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

• سوال بعد