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

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

ورودی🔗

ابتدا در یک خط $n,x$ را به شما میدهیم که $n$ تعداد حرکات نفر اول است و $x$ که یکی از کاراکترهای $L,M,R$ است که نشان میدهد در ابتدا نخود زیر لیوان چپی , وسطی یا راستی است. سپس در $n$ خط ، که هر خط نشان دهنده یک حرکت است ، در هر خط دو کاراکتر متفاوت به شما داده میشود که نشان میدهد که نفر اول در آن حرکت کدام لیوان ها را با هم عوض میکند. کاراکتر $L$ نشان دهنده لیوان چپی است. کاراکتر $M$ نشان دهده لیوان وسطی است. کاراکتر $R$ نشان دهده لیوان راستی است.

تضمین میشود که تمام کاراکتر های موجود در ورودی یکی از مقادیر $L,M,R$ را دارند و همچنین: $1 \le n \le 1\ 000$

خروجی🔗

در یک خط یک کاراکتر چاپ کنید که نشان دهد در پایان حرکات , نخود زیر کدام لیوان است. اگر در پایان نخود زیر لیوان چپ بود شما باید $L$ چاپ کنید. اگر در پایان نخود زیر لیوان وسط بود شما باید $M$ چاپ کنید. اگر در پایان نخود زیر لیوان راست بود شما باید $R$ چاپ کنید.

مثال🔗

ورودی نمونه ۱🔗

3 M
L M
R L
M L

خروجی نمونه ۱🔗

R

توضیح : ابتدا نخود زیر لیوان وسطی قرار دارد. با انجام اولین حرکت جای لیوان وسطی و چپی عوض میشود پس در پایان حرکت اول نخود زیر لیوان چپ قرار میگیرد. با انجام دومین حرکت جای لیوان راستی و چپی عوض میشود پس در پایان حرکت دوم نخود زیر لیوان راست قرار میگیرد. با انجام سومین حرکت جای لیوان چپی و وسطی عوض میشود و از آنجایی که نخود زیر لیوان راستی بود جایش تغییر نمیکند و در پایان نخود زیر لیوان راستی قرار میگیرد.

ورودی نمونه ۲🔗

5 L
L M
L M
R M
R L
R M

خروجی نمونه ۲🔗

M

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

شرکت beeptunes، در حال راه‌اندازی یک سیستم هوش مصنوعی برای پیشنهاد موسیقی به کاربرهاست. اکنون بخش هوش این سیستم به انتها رسیده، اما هنوز رابط درستی بین داده‌های موجود و بخش هوش سیستم وجود ندارد!

دو نوع داده جهت سیستم پیشنهاد موسیقی قابل استفاده است:

1. داده‌های مربوط به هر کاربر. این داده‌ها شامل نام کاربری، سن، شهر و لیست نام آلبوم‌هاییست که این کاربر خریداری کرده است.
2. داده‌های مربوط به هر آلبوم. این‌داده‌ها شامل نام آلبوم، نام خواننده، سبک و تعداد ترک‌های موسیقی این آلبوم هستند.

برای این سیستم هوش مصنوعی، خود این داده‌ها بصورت خام اهمیتی ندارند. این سیستم داده‌ها را بطور خاصی درخواست می‌کند و باید آن‌ها را در اختیارش قرار دهیم. درخواست‌ها به صورت‌های زیر ممکن است باشند:

1. درخواست تعداد آهنگ‌هایی که یک کاربر از یک خواننده خریده‌است.
2. درخواست تعداد آهنگ‌هایی که یک کاربر از یک سبک خریده‌است.
3. درخواست تعداد آهنگ‌هایی که کاربرهای با یک سن خاص، از یک خواننده خریده‌اند.
4. درخواست تعداد آهنگ‌هایی که کاربرهای با یک سن خاص، از یک سبک خریده‌اند.
5. درخواست تعداد آهنگ‌هایی که کاربرهای با یک شهر خاص، از یک خواننده خریده‌اند.
6. درخواست تعداد آهنگ‌هایی که کاربرهای با یک شهر خاص، از یک سبک خریده‌اند.

البته این سیستم خیلی هم باهوش نیست و ممکن است در سوال‌هایی که می‌پرسد نام کاربری، یا نام خواننده و یا هریک از فیلدهای مسئله اشتباه باشد و واقعاً در بین داده‌های سایت موجود نباشد.

حال به سراغ شما آمده‌ایم تا این رابط را برای ما بنویسید! برنامه‌ای بنویسید که داده‌های شرکت را *بصورت *Yaml ** دریافت کند، سپس به درخواست‌های از انواع مختلف پاسخ بدهد.

برای آشنایی با فرمت Yaml می‌توانید به مثال‌های سوال (و البته اینترنت!) مراجعه کنید. دقت کنید که ورودی‌های این سوال حالت خاص و بسیار ساده‌ای از Yaml می‌باشد.

ورودی🔗

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

پس از آن، در خط بعدی عدد $m$ آمده‌است که نمایانگر تعداد داده‌های از نوع آلبوم است. سپس این $m$ داده بصورت Yaml می‌آیند.

در این Yamlها، فیلدهای نام کاربری، سن، شهر و لیست آلبوم‌ها برای هر کاربر به همین ترتیب می‌آیند و با کلیدهای زیر مشخص می‌شوند:

• name
• age
• city
• albums

همچنین فیلدهای نام آلبوم، نام خواننده، سبک و تعداد ترک‌های یک آلبوم به همین ترتیب می‌آیند و با کلیدهای زیر مشخص می‌شوند:

• name
• singer
• genre
• tracks

در فیلدهای age و tracks حتماً یک عدد بین ۱ تا ۳۰ می‌آید و در دیگر فیلدها رشته‌های متشکل از حداکثر ۱۰ کاراکتر از حروف کوچک انگلیسی می‌آید.

و فرمت اعداد و رشته‌ها و فواصل، دقیقاً به شکل ورودی‌های نمونه خواهد بود. هر تب نیز با ۲ تا فاصله (space) مشخص می‌شود.

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

• 1 user singer
• 2 user genre
• 3 age singer
• 4 age genre
• 5 city singer
• 6 city genre

دقت کنید که ممکن است هریک از اطلاعات داخل پرسش‌ها (از قبیل نام کاربر، نام خواننده، ...) در ورودی موجود نباشد.

$1 \le n, m, q \le 100$

تضمین می‌شود که نام‌های کاربری و نام آلبوم‌ها، متفاوت هستند. همچنین تضمین می‌شود تمامی نام‌های آلبوم‌های خریده شده توسط کاربرها درست هستند و چنین آلبوم‌هایی وجود دارند. همچنین تمامی رشته‌های موجود در داده‌ها از حروف کوچک انگلیسی تشکیل شده‌اند و بین ۱ تا ۱۰ کاراکتر دارند. و تمامی اعداد موجود در داده‌ها بین ۱ تا ۳۰ هستند.

تضمین می‌شود که آلبوم‌ها و کاربرهای مختلف، نام‌های مختلف دارند. همچنین هیچیک از کلیدهای توضیحی (مانند name و albums و ...) بعنوان نام کاربر، آلبوم، خواننده، سبک و یا شهر در ورودی نمی‌آیند.

خروجی🔗

به ازای هر درخواست، برنامه‌ی شما باید یک عدد خروجی دهد که برابر با پاسخ آن درخواست است.

مثال🔗

ورودی نمونه ۱🔗

1
- name: ali
  age: 12
  city: bushehr
  albums:
    - bidad
    - blaze
2
- name: bidad
  singer: shajarian
  genre: classic
  tracks: 10
- name: blaze
  singer: ghorbani
  genre: pop
  tracks: 9
1
1 ali ghorbani

خروجی نمونه ۱🔗

9

ورودی نمونه ۲🔗

2
- name: gholi
  age: 18
  city: tehran
  albums:
    - tekunbede
    - barf
    - hoyad
- name: mehdi
  age: 20
  city: mashhad
  albums:
    - eclipse
    - barf
    - hoyad
4
- name: eclipse
  singer: malmsteen
  genre: classic
  tracks: 10
- name: barf
  singer: beeptunes
  genre: pop
  tracks: 22
- name: tekunbede
  singer: beeptunes
  genre: pop
  tracks: 14
- name: hoyad
  singer: hoyad
  genre: persian
  tracks: 5
12
1 gholi hoyad
1 gholi beeptunes
2 gholi rock
2 mehdi pop
3 20 beeptunes
4 18 malmsteen
4 19 malmsteen
5 tehran malmsteen
5 mashhad malmsteen
6 tehran pop
6 ghazvin rock
1 mehdi shajarian

خروجی نمونه ۲🔗

5
36
0
22
22
0
0
0
10
36
0
0

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

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

شکل شرکت باراز مانند یک مستطیل است که طول ضلع افقی آن $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
#..
...
##>

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

در شرکت رهنما ساعت بزرگی وجود دارد که همه‌ی زمان‌ها با آن گرفته می‌شود.(مبدا این ساعت زمان تاسیس شرکت رهنما می‌باشد) این ساعت (که تقویم نیز حساب می‌شود) دارای ۱۴ تا $seven segment$ بوده که دو تا دو تا به ترتیب برای ثانیه، دقیقه، ساعت،‌ روز، ماه، سال، قرن می‌باشند؛ در نتیجه، برای مثال اگر در زمانی باشیم که ثانیه‌ی آن ۳ می‌باشد، دو $seven segment$ مربوط به ثانیه به این صورت می‌شوند که سمت چپی صفر را نشان داده و راستی عدد ۳ را نشان می‌دهد. برای مثال، در لحظه‌ای که از تاسیس شرکت رهنما ۵ قرن و ۳۰ سال و ۳ ماه و ۲۰ روز و ۱۰ ساعت و ۵ دقیقه‌ و ۵۹ ثانیه می‌گذرد، ساعت به این شکل است:

با توجه به مشکلاتی که سیستم ساعت کاری برای پول دادن به کارمندان دارد،(مثل اینکه هر کارمندی در یک سری از ساعت‌ها بازده بیشتری دارد...) شرکت رهنما برای پول دادن به کارمندانش روش عجیبی را در پیش گرفته است:

فرض کنید شخصی قرار است از زمان $d_1$ تا زمان $d_2$ کار کند. با استفاده از ساعت بزرگ رهنما از $d_1$ به $d_2$ بروید. در این بین به ازای هر کدام از $segment$ها (هر کدام از لامپ‌های کوچک؛ هر $seven segment$ شامل هفت‌ عدد از این لامپ‌های کوچک می‌باشد یعنی در مجموع در کل ساعت ۹۸ عدد از این لامپ‌ها وجود دارد) دربیاورید که چند بار چراغ مربوط به آن تغییر وضعیت خواهد داد. جمع این اعداد مقدار پولی است که شرکت رهنما به ازای این زمان کاری به کارمندش خواهد داد. (حالت اولیه‌ی ساعت را $d_1$ در نظر گرفته بگیرید؛ یعنی اگر $d_1 = d_2$ جواب برابر صفر خواهد شد.)

آقای م.م.م مشغول کار در این شرکت است و می‌داند که باید از زمان $t1$ تا زمان $t2$ کار کند. او می‌خواهد بداند که به ازای این کار چقدر پول خواهد گرفت. به او کمک کنید تا سفارش شما را برای استخدام بکند.

در این سوال فرض کنید که هر ماه ۳۰ روز دارد.(در نتیجه هر سال ۳۶۰ روز است.)

ورودی🔗

در سطر اول ورودی هفت عدد $t1_1$ تا $t1_7$ آمده است که به ترتیب نمایانگر قرن، سال، ماه، روز، ساعت، هفته و ثانیه می‌باشد و این هفت عدد در مجموع $t_1$ را تشکیل می‌دهند.

در سطر بعدی مانند شیوه‌ای که در سطر اول ورودی گفته شده است، $t_2$ آمده است.

تضمین می‌شود که $t_1$ از $t_2$ بزرگتر نمی‌باشد. یعنی یا دو زمان با هم برابر هستند و یا :

$\exists i : ({t_1}_i < {t_2}_i) \land (\forall j < i : {t_1}_j = {t_2}_j)$

محدودیت متغیرهای ورودی:🔗

قرن و سال اعدادی صحیح بین ۰ تا ۹۹ می‌باشد.

ماه عددی صحیح بین ۱ تا ۱۲ و روز عددی صحیح بین ۱ تا ۳۰ می‌باشد.

ساعت عددی صحیح بین ۰ تا ۲۳ و دقیقه و ثانیه‌ نیز اعدادی صحیح بین ۰ تا ۵۹ می‌باشد.

$0 \le minute, second \le 59$ $0 \le hour \le 23$ $1 \le day \le 30$ $1 \le month \le 12$ $0 \le year, century \le 99$

خروجی🔗

در خروجی تنها یک عدد چاپ کنید که برابر پاسخ مسئله است.

مثال🔗

ورودی نمونه ۱🔗

1 2 3 4 4 5 6
1 2 3 4 4 5 8

خروجی نمونه ۱🔗

9

در نمونه‌ی اول(با توجه به شکل زیر) در تغییر ۶ به ۷، ۵ $segment$ و در تغییر ۷ به ۸، ۴ $segment$ تغییر وضعیت می‌دهند که در مجموع می‌شود ۹ تا.

ورودی نمونه ۲🔗

99 99 12 30 23 59 59
99 99 12 30 23 59 59

خروجی نمونه ۲🔗

0

ورودی نمونه ۳🔗

1 2 3 4 5 6 7
1 2 3 5 9 59 0

خروجی نمونه ۳🔗

352454

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

در این سوال از شما میخواهیم که در یک حرکت نمادین یک بازی ساده بنویسید. باشد که صنعت بازی‌سازی مملکت راه بیفتد...

توضیحات بازی🔗

۱- زمین بازی یک جدول $n \times m$ است و دو تیم در این زمین مشغول بازی هستند. سطر‌های این جدول را از بالا به پایین با اعداد ۱ تا $n$ و ستون‌های آن را از چپ به راست با ۱ تا $m$ شماره‌گذاری می‌کنیم. هر تیم یک امتیازی دارد که در ابتدا امتیاز هر دو تیم صفر می‌باشد. در آخر بازی هم تیمی برنده است که امتیاز آن بیشتر باشد.

۲- تیم اول $a$ و تیم دوم $b$ مهره در زمین دارند. هر کدام از این مهره‌ها در یکی از خانه‌های جدول هستند به طوری که در هر خانه حداکثر یک مهره می‌باشد. در نتیجه $n \times m \ge a + b$. حال مهره‌ها را با اعداد ۱ تا $a + b$ شماره‌گذاری میکنیم؛ به طوری که از ۱ تا $a$ اندیس مهره‌های تیم اول، و از $a + 1$ تا $a + b$ اندیس مهره‌های تیم دوم می‌باشند.

۳- هر مهره دو نوع کار می‌تواند انجام دهد. به یکی از خانه‌های مجاور ضلعی خانه‌ی الآنش برود و یا به یکی از چهار طرف خانه‌ای که در آن قرار دارد (چپ، بالا، راست، پایین) تیر شلیک کند. او در هر ثانیه می‌تواند حداکثر یک بار جابجا شود(می‌تواند هم جابجا نشود) و حداکثر یک بار شلیک کند(‌می‌تواند هم شلیک نکند). *دقت کنید که یک مهره به خانه‌ای که در آن مهره‌ای وجود دارد نمی‌تواند برود. همچنین از جدول نیز نمی‌تواند خارج شود. *

۴- در هنگام شلیک کردن یک تیر، هر مهره می‌تواند تیر خود را در یکی از چهار جهت اصلی شلیک کند. همچنین هر تیر در هر ثانیه یک خانه در جهتی که شلیک شده است جلو می‌رود؛ یعنی اگر برای مثال مهره‌ای در خانه‌ی $(tx, ty)$ باشد و تیری در جهت بالا شلیک کند، در ثانیه‌ی شلیک، ** تیر در خانه‌ی ** $(tx - 1, ty)$ ** به وجود می‌آید و از ثانیه‌ی بعدی با بردار ** $(-1, 0)$ ** حرکت خواهد کرد. ** اگر تیر به دیواره‌ی جدول یا به یکی از مهره‌های تیم حریف برخورد کند، از بین می‌رود. ** دقت کنید که در هر لحظه در هر خانه به هر تعداد می‌تواند تیر وجود داشته باشد. همچنین تیرها با هم برخورد نمی‌کند و از هم رد می‌شود.**

۵- هر مهره یک پارامتر جان و یک پارامتر قدرت دارد که برای مهره‌ی $i$، این دو را به ترتیب با $h_i$ و $d_i$ نمایش می‌دهیم. اگر جان مهره‌ای صفر یا کمتر شود، آن مهره می‌میرد و از بازی حذف خواهد شد. همچنین تیری که مهره‌ی $i$ شلیک می‌کند دارای قدرت $d_i$ است و اگر به هر کدام از مهره‌‌های تیم حریف برخورد کند از جان او به اندازه‌ی $d_i$ کم می‌کند. ** دقت کنید که تیر مهره‌ی یک تیم بر مهره‌های همان تیم اثر ندارد و بدون برخورد از آن‌ها عبور می‌کند. **

۶- هر مهره نمی‌تواند به صورت همزمان بیش از ۵ تیر در زمین بازی داشته باشد؛ دقت کنید که این جمله به این معنا نیست که هر مهره باید در کل بازی حداکثر ۵ تیر بزند.

۷- در زمان بازی و در حین انجام بازی، گاهی اوقات، یک «افزونه» در یکی از خانه‌های جدول به وجود می‌آید. افزونه یک موجودی است که اگر توسط مهره‌ای خورده شود بر آن مهره تاثیر می‌گذارد. افزونه‌ها دو نوع هستند. افزونه‌های جانی که جان مهره $(h_i)$ را زیاد می‌کنند و افزونه‌های قدرتی که مقدار قدرت مهره $(d_i)$ را زیاد می‌کنند. هر افزونه یک پارامتر «تغییر» $s$ دارد که به همان مقدار در مهره تغییر ایجاد می‌کند. اگر یک مهره در خانه‌ای برود که تعدادی افزونه در آن قرار دارد، آن مهره این افزونه‌ها را خورده و تغییرات رویش انجام می‌شود و ۱ امتیاز به امتیاز تیمش اضافه خواهد شد. ** دقت کنید که بعد از خورده شدن افزونه‌های یک خانه، در آن خانه دیگر افزونه‌ای وجود ندارد. همچنین در هر خانه‌ به تعداد دلخواه افزونه می‌تواند وجود داشته باشد‌. **

۸- همانند افزونه، چیزی به نام «بمب» وجود دارد که هر از چند گاهی در یکی از خانه‌‌های جدول به وجود می‌آید. هر بمب یک پارامتر قدرت $g$ دارد که اگر مهره‌ای به خانه‌ای برود که در آن تعدادی بمب وجود دارد، بمب‌ها ترکیده و از جان آن مهره و تمام مهره‌هایی که با بمب‌ها در یک ردیف و یا یک ستون هستند، به اندازه‌ی مجموع $g$ بمب‌ها کم می‌شود. ** دقت کنید که بعد از ترکیدن بمب‌ها، دیگر بمبی در آن خانه وجود ندارد. همچنین بمب بر روی تمام مهره‌ها تاثیر داشته و تاثیر بمب به اینکه هر مهره در کدام تیم است بستگی ندارد. **

توضیحات سوال🔗

تعدادی بازیکن در حال بازی کردن این بازی هستند و هر کدام از آن‌ها کنترل یک مهره را در اختیار دارند. حال ما حالت اولیه‌ی بازی و تغییرات زمین بازی در هر لحظه و دکمه‌هایی که این بازیکن‌ها می‌زنند را به شما می‌دهیم و شما باید در آخر بازی، امتیاز هر تیم را به ما بگویید. ‌ دقت کنید که اگر به علتی (ترکیدن بمب‌ها یا مردن توسط تیر‌های حریف) یکی از مهره‌های یک تیم بمیرد، ۱۰ امتیاز به امتیاز تیم حریف اضافه خواهد شد.

نحوه‌ی کلی ورودی دادن هم به این صورت است در هر ثانیه تغییرات بازی را به شما ورودی می‌دهیم. تغییرات بازی در هر ثانیه چهار نوع هستند:

۱- بازیکنی دکمه‌ای زده است که مهره‌ی ‌$i$ در جهت $d$ حرکت کند.($d$ نمایانگر یک از چهار جهت اصلی می‌باشد.) دقت کنید که شاید به خاطر پر بودن خانه یا خوردن به دیواره‌ی جدول مهره نتواند حرکت کند. ** همچنین دقت کنید که شاید اصلا مهره‌ی $i$ مرده باشد اما به خاطر سماجت بازیکن، همچنان دکمه حرکتش زده شود و این درخواست برای شما ارسال شود. در این حالت شما باید این را در نظر نگرفته و رد کنید. همچنین امکان دارد که بازیکنی دکمه‌ی شلیک را بزند در حالیکه مهره‌ی مربوط به او دارای بیش از ۵ تیر در زمین می‌باشد.**

۲- مهره‌ی $i$ در جهت $d$ شلیک کرد.($d$ نمایانگر یک از چهار جهت اصلی می‌باشد.) ** دقت کنید که شاید اصلا مهره‌ی $i$ مرده باشد اما به خاطر سماجت بازیکن، همچنان دکمه شلیک زده شود و این درخواست برای شما ارسال شود. در این حالت شما باید این را در نظر نگرفته و رد کنید. **

۳- یک افزونه از نوع $k$ با مقدار پارامتر «تغییر» $s$ در خانه‌ی $(x, y)$ قرار بده.( $k$ نمایانگر یکی از دو نوع جانی و قدرتی می‌باشد.)

۴- یک بمب با پارامتر قدرت $g$ در خانه‌ی $(x, y)$ قرار بده.

ترتیب اعمال اتفاقات🔗

در هر ثانیه به ترتیب زیر اتفاقات رخ می‌دهد:

ابتدا تیرهای درون زمین جابجا می‌شود. سپس گلوله‌هایی که در آن ثانیه به وجود آمده‌اند به بازی اضافه می‌شود. سپس تمام این گلوله‌ها اگر در حال حاضر به مهره‌ای برخورد می‌کنند، برخوردشان تاثیر داده شده و از جان افراد کم می‌شود. *‌دقت کنید که شاید چند گلوله به کسی بخورد. در این حالت شما باید تمام این گلوله‌ها را تاثیر دهید حتی اگر هر کدام از این گلوله‌ها به تنهایی جان مهره را صفر یا منفی کنند. *

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

حال تمام مهره‌هایی که می‌خواهند در این ثانیه جابجا شود به ترتیب از ۱ تا $a + b$ جابجایی‌شان را انجام می‌دهند. سپس دوباره تمام اتفاقات بالا(غیر از اضافه شدن بمب‌ها و افزونه‌ها) به همان ترتیبی که در بالا گفته شد انجام می‌شود.

زیرمسئله‌ها🔗

این سوال شامل سه زیرمسئله می‌باشد:

۱- اولین مورد که شامل «۲۰۰» امتیاز بوده و فقط شامل بند‌های ۱ تا ۶ بازی می‌شود؛ یعنی بند‌های ۷ و ۸ و تمام موارد مربوط به این دو بند را در نظر نگرفته و بازی را بنویسید. ** ورودی نیز شامل افزونه و بمب نیست؛ یعنی هیچ درخواستی مبنی بر اضافه کردن یک افزونه و یا بمب در آن نیامده است. **

۳- دومین زیر مسئله «۳۰۰» امتیاز دارد و شامل موارد ۱ تا ۷ می‌شود؛‌ یعنی در ورودی هیچ بمبی وجود نخواهد داشت.

۴- سومین زیر مسئله که «۴۰۰» امتیاز دارد و شامل کل بازی می‌شود؛ با تمام بند‌ها و جزئیات آن.

ورودی🔗

در خط اول ورودی دو عدد $n$ و $m$ و $a$ و $b$ آمده است که به ترتیب نمایانگر تعداد سطر‌ها و ستون‌های جدول، تعداد مهره‌های تیم اول و تعداد مهره‌های تیم دوم می‌باشد.

در $a + b$ خط بعدی، در خط $i$،‌ دو عدد $x_i$ و $y_i$ آمده است که نمایانگر مختصات اولیه‌ی مهره‌ی $i$ ام می‌باشد. مهره‌های با شمار‌ه‌ی ۱ تا $a$ متعلق به تیم اول و مهره‌های با شماره‌ی ‌$a + 1$ تا $b$ متعلق به تیم دوم می‌باشد.

در $a + b$ خط بعدی، در خط $i$،‌ دو عدد $h_i$ و $d_i$ آمده است که به ترتیب نمایانگر پارامتر جان و پارامتر قدرت مهره‌ی $i$ ام می‌باشد. مهره‌های با شمار‌ه‌ی ۱ تا $a$ متعلق به تیم اول و مهره‌های با شماره‌ی ‌$a + 1$ تا $b$ متعلق به تیم دوم می‌باشد.

در خط بعدی عدد $t$ آمده است که نمایانگر مدت زمان بازی به ثانیه می‌باشد. بازی از زمان ۰ شروع به کار می‌کند و در آخر ثانیه‌‌ی $t$ تمام می‌شود.

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

در $q$ خط بعدی، در هر خط یک تغییر به این صورت آمده است:

ابتدا $T$ می‌آید که نمایانگر این است که در چه ثانیه‌ای باید این تغییر تاثیر داده شود. تضمین می‌شود که ابتدا تغییرهای مربوط به ثانیه‌ی ۱، سپس ثانیه‌ی ۲ و... می‌آید؛ یعنی تغییرها به ترتیب زمانی می‌آیند. سپس عدد $p$ می‌آید که نمایانگر نوع تغییر است.

اگر تغییر از نوع اول باشد،($p$ = 1) در ادامه‌ی خط یک عدد $i$ می‌آید که نمایانگر مهره‌ای است که باید حرکت کند. سپس با یک فاصله یک کاراکتر $d$ می‌آید که نمایانگر جهتی است که مهره‌ی $i$ می‌خواهد حرکت کند. اگر $d$ برابر با L یا D یا R و یا U باشد، به ترتیب نمایانگر این است که مهره می‌خواهد به سمت چپ، پایین، راست و بالا برود.

اگر تغییر از نوع دوم باشد،($p$ = 2) در ادامه‌ی خط یک عدد $i$ می‌آید که نمایانگر مهره‌ای است که می‌خواهد تیر بزند. سپس با یک فاصله یک کاراکتر $d$ می‌آید که نمایانگر جهتی است که مهره‌ی $i$ می‌خواهد تیر بزند. اگر $d$ برابر با L یا D یا R و یا U باشد، به ترتیب نمایانگر این است که مهره می‌خواهد به سمت چپ، پایین، راست و بالا تیر بزند.

اگر تغییر از نوع سوم باشد،($p$ = 3) ابتدا یک عدد $j$ می‌آید که نمایانگر نوع افزونه است. اگر $j$ برابر با ۱ بود، افزونه از نوع جانی و گرنه از نوع قدرتی می‌باشد. سپس با یک فاصله عدد $s$ می‌آید که نمایانگر پارامتر تغییر افزونه می‌باشد. در نهایت دو عدد می‌آید که نمایانگر مختصات افزونه هستند.

اگر تغییر از نوع چهارم باشد،($p$ = 4) ابتدا یک عدد $g$ می‌آید که نمایانگر پارامتر قدرت بمب می‌باشد و سپس دو عدد می‌آید که نمایانگر مختصات بمب هستند.

تضمین می‌شود که مختصات داخل ورودی حتما در زمین بازی است. همچنین مکان اولیه‌ی مهره‌ها دو به دو متمایز می‌باشد. همچنین در اول بازی هیچ افزونه‌ و بمبی در جدول بازی وجود ندارد. ‌ دقت کنید که در هر لحظه می‌تواند در هر خانه به تعداد دلخواه بمب و افزونه وجود داشته باشد.

$5 \le n, m \le 12$ $1 \le a, b \le 10$ $1 \le x_i \le n$ $1 \le y_i \le m$ $3 \le h_i \le 20$ $1 \le d_i \le 5$ $2 \le t \le 1\ 000$ $1 \le q \le 5\ 000$ $1 \le T \le t$ $1 \le p \le 4$ $1 \le i \le a + b$ $1 \le j \le 2$ $1 \le s \le 5$ $1 \le g \le 5$

خروجی🔗

در تنها سطر خروجی امتیاز تیم اول و امتیاز تیم دوم را خروجی دهید.

مثال🔗

ورودی نمونه ۱ (مثالی از زیر مسئله‌ی اول)🔗

5 8 1 1
1 1
1 8
6 1
6 1
10
6
1 2 1 R
2 2 1 R
3 2 1 R
4 2 1 R
5 2 1 R
6 2 1 R

خروجی نمونه ۱ (مثالی از زیر مسئله‌ی اول)🔗

0 0

ورودی نمونه ۲ (مثالی از زیر مسئله‌ی دوم)🔗

5 8 1 1
1 1
1 8
6 1
6 1
10
7
1 3 2 5 1 1
1 2 1 R
2 2 1 R
3 2 1 R
4 2 1 R
5 2 1 R
6 2 1 R

خروجی نمونه ۲ (مثالی از زیر مسئله‌ی دوم)🔗

11 0

ورودی نمونه ۳ (مثالی از زیر مسئله‌ی سوم)🔗

8 8 5 5
7 8
5 2
3 6
7 2
1 2
4 1
1 8
7 7
5 5
2 8
4 3
4 3
4 3
4 3
3 3
4 3
4 3
4 3
4 3
4 3
10
12
1 4 4 5 4
1 3 1 2 5 6
2 1 5 D
2 2 5 R
2 1 9 R
2 2 2 U
3 1 9 L
3 1 6 R
3 2 5 R
4 1 9 L
4 2 1 U
4 2 6 D

خروجی نمونه ۳ (مثالی از زیر مسئله‌ی سوم)🔗

10 11