تعدادی سوسک سیاه و سفید در تار عنکبوت غول پیکر گیر افتادهاند. تار عنکبوت غول پیکر به صورت شبکهای مربعی به ضلع N است و در هر یک از N2 خانه آن سوسکی گیر افتاده است. یکی از بزرگترین لذتهای عنکبوت غول پیکر در زندگی، له کردن سوسکهای بیچاره است. زیرا وقتی سوسکی را له میکند، آن سوسک منفجر شده و مواد سمی بدنش بر روی تعدادی از سوسکهای سطر پایینی میریزد که باعث انفجار آنها نیز میشود و این روند تا سطر آخر ادامه پیدا میکند. میدانیم سوسکهایی که در سطر iام قرار دارند به هنگام انفجار مواد سمیشان بر روی تمام سوسکهایی که در پایین قرار دارند و شماره ستون شان حداکثر ri تا با سوسک منفجر شده تفاوت دارد، میریزد. عنکبوت از شما خواسته به ازای هر موقعیت داده شده، تعداد سوسکهای سیاهی را پیدا کنید که منفجر میشوند. در موقعیت iام، عنکبوت سوسکهای si تا eiام سطر rowi را له میکند.
X
است اگر سوسکی که در سطر iام و ستون jام قرار دارد، سیاه باشد و .
است اگر سفید باشد.در q سطر خروجی در سطر iام تعداد سوسکهای سیاهی که در موقعیت iام منفجر میشوند را بنویسید.
ورودی نمونه | خروجی نمونه |
---|---|
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 |