سوال ۲

یک جدول $n\times{}n$ داریم که در ابتدا در تمام خانه‌های آن، عدد ۰ نوشته شده است. خانه‌ی محل تلاقی سطر $i$ام و ستون $j$ام را با $(i, j)$ نشان می‌دهیم.

$q$ درخواست به ما داده می‌شود. هر درخواست، ۳ عدد طبیعی $x, y, m$ به ما می‌دهد که $x+m-1\le{}n$ و $y+m-1\le{}n$ است. با این درخواست، باید به عدد هر ‌خانه‌ی $(a, b)$ که عضو مجموعه‌ی \begin{equation*} \{(a, b)\ |\ x\le{}a<x+m;\ y\le{}b<y+m;\ a-x\ge{}b-y\} \end{equation*} باشد، یک واحد اضافه شود.

شما ابتدا $q$ درخواست را دریافت می‌کنید و در انتها باید بگویید اعداد خانه‌های جدول چه خواهد بود. الگوریتمی از $O(n^2+q)$ برای این کار ارائه کنید.