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

---

اخیرا دو شرکت «گوگل‌پاز» و «باراز» برای ارائه‌ی خدماتشان، با یکدیگر وارد رقابت سختی شده‌اند به طوری که هر کدام از آن‌ها برای خارج کردن رقیب خود از دور رقابت حاضر است دست به هر کاری بزند. روزی افراد شرکت گوگل‌پاز تصمیم می‌گیرند که یک مار در شرکت باراز رها کنند تا همه‌ی کارمندان آن شرکت را بخورد!

شکل شرکت باراز مانند یک مستطیل است که طول ضلع افقی آن $m$ متر و طول ضلع عمودی آن $n$ متر است و به مربّع‌های $1 \times 1$ افراز شده است. بدن مار نیز از تعدادی قطعه تشکیل شده است و هر قطعه یکی از آن مربّع‌ها را اشغال می‌کند. یعنی اگر طول مار $p$ متر باشد، دقیقا $p$ مربّع $1 \times 1$ از شرکت را اشغال خواهد کرد. (هر دو تا از آن مربّع‌ها که شامل دو قطاع متوالی بدن مار باشند، با یکدیگر مجاور ضلعی هستند.)

هر کارمند شرکت باراز در ابتدا در یکی از مربّع‌ها قرار دارد و پس از ظهور مار، از ترس سر جای خود میخ‌کوب می‌شود. آن‌ها یک میزان خوش‌مزگی نیز دارند! هر گاه مار، کارمند مشخّصی برای خوردن در نظر نداشته باشد، نگاهی به تمام کارمندانی که هنوز خورده نشده‌اند و محلشان توسّط بدن مار اشغال نشده است می‌اندازد. اگر هیچ کارمندی واجد شرایط گفته شده نباشد، مار به حرکتش ادامه خواهد داد و هیچ کارمندی را برای خوردن انتخاب نمی‌کند. در غیر این صورت از بین آن کارمندهایی که گفته شد، خوش‌مزه‌ترین را انتخاب می‌کند و تا آن را نخورد، لب به هیچ کارمند دیگری نخواهد زد؛ حتّی اگر از خانه‌ی حاوی سایر کارمندان عبور کند.

افراد شرکت گوگل‌پاز می‌توانند مار را از راه دور کنترل کنند؛ همانا شرکت گوگل‌پاز مرزهای علم و تکنولوژی را درنوردیده‌است. سرِ مار همیشه به سمت یکی از چهار جهت اصلی است: بالا، چپ، پایین و راست. مار در هر ثانیه به اندازه‌ی یک مربّع به جلو می‌رود. شرکت گوگل‌پاز در ابتدای هر ثانیه می‌تواند پیامی به مار بفرستد. اگر پیام L بفرستد، سرِ مار ۹۰ درجه پادساعتگرد خواهد چرخید و اگر پیام R بفرستد، سر مار ۹۰ درجه ساعتگرد خواهد چرخید.

پس از دریافت پیام و چرخشِ احتمالیِ سرِ مار، سر مار یک واحد در جهت فعلی‌ش به جلو خواهد رفت؛ اگر خانه‌ی جدید سر مار شامل کارمند مورد نظرش باشد، جای مکان قبلی سرِ مار با قطعه‌ای جدید از بدن مار پر خواهد شد و طول مار یک واحد زیاد می‌شود. در غیر این صورت هر قطعه از بدن مار جای قطعه‌ی جلویی‌ش را اشغال خواهد کرد. اگر پس از این حرکت سر مار روی قطعه‌ای از بدنش قرار گرفته باشد، مار جان خواهد باخت.

لازم به ذکر است در مرحله‌ی جلو رفتنِ سر، در صورتی که سر مار بخواهد از یکی از دو سر یک سطر بیرون بزند، به سر دیگر سطر منتقل خواهد شد. این امر در مورد ستون‌ها نیز برقرار است. به عبارت دیگر خانه‌های دو سر هر سطر و یا ستون، مجاور هستند.

افراد شرکت گوگل‌پاز از شما می‌خواهند برنامه‌ای بنویسید که با گرفتن مکان کارمندان باراز، ترتیب خوش‌مزگی آن‌ها و دستوراتی که از طرف شرکت گوگل‌پاز برای مار ارسال شده است، وضعیت شرکت باراز در انتهای هر ثانیه را چاپ کند.

ورودی

در خط اول ورودی $n$ و $m$ ابعاد شرکت و $T$ تعداد حرکت‌های مار آمده است.

در خط دوم $s_r$ و $s_c$ می‌آید که به ترتیب شماره‌ی سطر(با شماره‌گذاری سطرها از بالا به پایین با ۱ تا $n$) و شماره‌ی ستون(با شماره گذاری ستون‌ها از چپ به راست با ۱ تا $m$) مکان ابتدایی مار هستند. جهت ابتدایی مار به سمت بالا است و طولش ۱ است.

در خط سوم $p$ تعداد کارمندهای باراز آمده است.

در $i$امین سطر از هر یک از $p$ سطر بعد، مکان کارمند $i$ام می‌آید: دو عدد $r$ شماره‌ی سطر کارمند و $c$ شماره‌ی ستون او. کارمندها به ترتیب خوش‌مزگی داده می‌شوند؛ کارمند شماره ۱ از همه خوش‌مزه‌تر است.

در خط بعد عدد $q$ می‌آید که نشان‌دهنده‌ی تعداد دستوراتی است که از گوگل‌پاز به مار می‌رسند.

در هر یک از $q$ سطر بعد نیز یک کاراکتر و یک عدد می‌آیند. $c$ و $t$ به این معنی که در ابتدای ثانیه‌ی $t$ام، دستور $c$ به مار فرستاده شده است. دستورات به ترتیب زمان داده می‌شوند.

$$2 \leq n, m \leq 10$$

$$1 \leq T, p \leq 500$$

$$0 \leq q \leq T$$

خروجی

در خروجی حداکثر $T + 1$ جدول $n \times m$ چاپ کنید. جدول $i$ام نشان‌دهنده‌ی وضعیت بازی در انتهای لحظه‌ی $i - 1$ام خواهد بود. چنان چه در مرحله‌ای مار مُرد، لازم نیست جزییات آن مرحله و مراحل پس از آن را چاپ کنید.

به جای خانه‌های خالی باید . (نقطه) چاپ کنید. به جای محل کارمندی که مار قصد خوردنش را دارد باید A چاپ شود، اطّلاعاتی از مکان سایر کارمندان در خروجی داده نخواهد شد. به جای سر مار، در صورتی که جهت آن به سمت بالا باشد ^، در صورتی که به سمت پایین باشد v، در صورتی که به سمت چپ باشد > و در صورتی که به سمت راست باشد < چاپ کنید. به جای سایر خانه‌های شامل بدن مار نیز # چاپ کنید. پیش از هر جدول اندیس آن لحظه را باید چاپ کنید.

مثال

ورودی نمونه

3 3 20
2 2 
3
2 3
1 1
3 3
3
R 4
L 9
R 14

خروجی نمونه

0
...
.^A
...
1
.^.
..A
...
2
...
..A
.^.
3
...
.^A
...
4
A..
.#>
...
5
A..
>.#
...
6
A..
#>.
...
7
A..
.#>
...
8
A..
>.#
...
9
^..
#.#
..A
10
#..
#..
^.A
11
#..
^..
#.A
12
^..
#..
#.A
13
#..
#..
^.A
14
#..
...
#>A
15
#..
...
##>