+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۱۲۸ مگابایت ***** اخیرا آقای ماهر دستگاهی اختراع کرده که طبق ادّعایش می‌تواند زمین‌های ناهموار را هموار کند. اگر ادّعای او درست باشد، اختراع وی، عصر جدیدی را در صنعت صاف‌سازی رقم خواهد زد. حال بزرگان این صنعت جمع شده‌اند تا ببیند ادّعای آقای ماهر درست است یا نه! آقای ماهر برای این که درست بودن دستگاهش را به دیگران ثابت کند، می‌خواهد یک کوهستان را با استفاده از دستگاهش هموار کند. کوهستانی که او برای این کار انتخاب کرده است، به شکل یک مستطیل $n \times m$ است. یعنی کوه‌ها در $n$ سطر قرار دارند و هر سطر شامل $m$ کوه است. (کوه‌های هر سطر و هر ستون در یک خط قرار گرفته‌اند) هر کوه ارتفاعی صحیح و نامنفی نیز دارد؛ ارتفاع کوه $j$ام از سطر $i$ام کوهستان را با $A_{i, j}$ نشان می‌دهیم. دستگاه آقای ماهر در هر مرحله ۴ ورودی می‌گیرد و قسمتی از کوهستان را طبق آن ۴ ورودی هموارتر می‌کند. ورودی‌هایی که دستگاه می‌گیرد در یکی از دو قالب زیر هستند: 1. R $l$ $r$ $k$ 2. C $l$ $r$ $k$ در حالت اوّل، ارتفاع هر کوهی که در یکی از سطرهای $l$ تا $r$ (شامل این دو سطر) باشد، تقسیم بر $k$ خواهد شد($1\leq l \leq r \leq n$). در حالت دوم نیز همین اتّفاق برای هر کوهی که در یکی از ستون‌های $l$ تا $r$ (شامل این دو ستون) وجود دارد می‌افتد($1 \leq l \leq r \leq m$). چنان چه ارتفاع جدید هر کوه عددی ناصحیح باشد، بر اثر عوامل طبیعی از ارتفاع کوه آن قدر کاسته می‌شود تا به اوّلین عدد صحیح کوچکتر از خودش برسد! مثلن اگر ارتفاع کوهی $9$ باشد و عملیاتی با $k=4$ روی آن اعمال شود، ارتفاع آن ابتدا برابر $2.25$ می‌شود و سپس تبدیل به $2$ می‌شود. امّا اگر عملیاتی به ازای $k=3$ روی آن اعمال شود،‌ ارتفاعش برابر $3$ می‌شود. آقای ماهر در زمینه‌ی محاسبات ماهر نیست؛ لذا ارتفاع کوه‌های کوهستان و عملیاتی که قرار است با دستگاه انجام دهد را به شما می‌گوید؛ در ازای این داده‌ها نیز می‌خواهد ارتفاع نهایی کوه‌ها را در صورتی که دستگاه درست کار کند، به او بگویید. # ورودی در سطر اوّل ورودی دو عدد $n$ و $m$ می‌آیند. در هر یک از $n$ سطر بعد، $m$ عدد آمده است. عدد $j$ام در $i$امین سطر برابر $A_{i, j}$ است. سپس در یک خط عدد $q$ می‌آید که تعداد درخواست‌هاست. در هر یک از $q$ سطر بعد، یکی از ورودی‌های سوال در قالبی که گفته شد قرار دارد. $$1 \leq n, m \leq 1\ 000$$ $$1 \leq q \leq 10\ 000$$ $$1 \leq k, A_{i, j} \leq 1\ 000\ 000\ 000$$ # خروجی در خروجی ارتفاع نهایی کوه‌ها را چاپ کنید. خروجی شما باید از $n$ سطر تشکیل شده باشد که هر کدام از آن‌ها شامل $m$ عدد هستند. .عدد $j$ام از سطر $i$ام برابر با ارتفاع نهایی کوه $j$ام از سطر $i$ام کوهستان خواهد بود. # مثال ## ورودی نمونه ۱ ``` 2 3 1 2 3 4 5 6 1 C 2 3 2 ``` ## خروجی نمونه ۱ ``` 1 1 1 4 2 3 ``` ## ورودی نمونه ۲ ``` 3 3 10 20 3 15 1000 60 16 10 20 4 R 2 3 4 C 1 2 2 R 1 2 3 R 2 2 5 ``` ## خروجی نمونه ۲ ``` 1 3 1 0 8 1 2 1 5 ```

حل سؤال در بانک سؤالات