====== سوسک کشی ======


تعدادی سوسک سیاه و سفید در تار عنکبوت غول پیکر گیر افتاده‌اند. تار عنکبوت غول پیکر به صورت شبکه‌ای مربعی به ضلع $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$ام منفجر می‌شوند را بنویسید.

===== محدودیت‌ها =====


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

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|5 \\ 0 1 3 2 1 \\ .X.XX \\ X..XX \\ .X.XX \\ XX..X \\ X.XX. \\ 5 \\ 2 5 5 \\ 4 1 2\\ 3 3 4 \\ 1 2 3 \\ 2 1 5 | 9 \\ 5 \\ 7 \\ 9 \\ 12|
</WRAP>
  * [[سوال ۲|سوال بعد]]