۳۰ شارپ

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

روزی ۳۰ علامت شارپ (#) برای یادگرفتن زبان سی‌شارپ راهی کوه قاف شدند. پس از طی کردن مراحلی سخت، در بالای کوه، آبی را یافتند. آن‌ها تصویر خود را در آن آب دیدند و فهمیدن که خودشان سی‌شارپ هستند!

حال فرض کنید $n$ شارپ، کنار هم قرار گرفته‌اند. ( $n$ کاراکتر #) از شما می‌خواهیم تصویری که آن‌ها در آب می‌بینند را چاپ کنید.

برای مثال اگر ۳ شارپ در کنار هم باشند، تصویر آن‌ها به صورت ### در آب دیده می‌شود. و اگر ۵ شارپ در کنار هم باشند، تصویر آن‌ها به صورت ##### در آب دیده می‌شود.

ورودی🔗

در سطر اول ورودی، عدد صحیح $n$ می‌آید. $1 \leq n \leq 30$

خروجی🔗

در تنها سطر خروجی، تصویری که $n$ شارپ در آب می‌بینند را چاپ کنید.

مثال‌ها🔗

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

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

###

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

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

#####

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

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- شاخص‌های مختلف و متنوعی برای رده‌بندی اساتید از نظر پژوهشی وجود دارد. یکی از شاخص‌های معروف `h-index` نام دارد. در هر مقاله تعدادی ارجاع به مقالات دیگر به‌عنوان منبع وجود دارد. یک مقاله ارزشمندتر است اگر تعداد مقالاتی که به آن ارجاع می‌دهند بیشتر باشد. چون منبع بهتری بوده و باعث پیشرفت کار تعداد بیشتری از اساتید شده‌است. این عدد تعداد ارجاع (`citation`) نام دارد و برای هر مقاله به‌صورت مستقل قابل محاسبه است. حال فرض کنید یک استاد، $n$ مقاله منتشر کرده است و مقاله‌ی $i$ام $a_i$ بار به‌عنوان منبع مقالات دیگر استفاده شده است. عدد `h-index` این استاد برابر $k$ است اگر حداقل $k$ مقاله داشته باشد، که حداقل $k$ بار به‌عنوان منبع به آن ارجاع داده باشند. اگر چند $k$ این ویژگی را دارد، بزرگ‌ترین آن را در نظر می‌گیرند. # ورودی در سطر اول ورودی $n$ یا تعداد مقالات می‌آید و در سطر بعد $n$ عدد می‌آید که $i$ـمین آنها $a_i$ یا تعداد ارجاعات به مقاله $i$ـم است. $$1 \leq n \leq 300 \, 000$$ $$0 \le a_i \le 300 \, 000$$ # خروجی در تنها خط خروجی `h_index` استاد مطلوب است. | زیرمسئله | امتیاز | | ----------- | ----------- | | $n \leq 1000$ | ۱۰۰ | | بدون محدودیت اضافه | ۱۰۰ | # مثال ## ورودی نمونه ۱ ``` 5 1 5 3 4 2 ``` ## خروجی نمونه ۱ ``` 3 ``` در این نمونه، ۳ عدد داریم که بزرگتر یا مساوی ۳ هستند (اعداد ۵، ۳ و ۴) ## ورودی نمونه ۲ ``` 8 1 13 1 3 5 2 21 8 ``` ## خروجی نمونه ۲ ``` 4 ``` در این نمونه، ۴ عدد داریم که بزرگتر یا مساوی ۴ هستند (اعداد ۱۳، ۵، ۲۱ و ۸)

رده‌بندی اساتید

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

شاخص‌های مختلف و متنوعی برای رده‌بندی اساتید از نظر پژوهشی وجود دارد. یکی از شاخص‌های معروف h-index نام دارد.

در هر مقاله تعدادی ارجاع به مقالات دیگر به‌عنوان منبع وجود دارد. یک مقاله ارزشمندتر است اگر تعداد مقالاتی که به آن ارجاع می‌دهند بیشتر باشد. چون منبع بهتری بوده و باعث پیشرفت کار تعداد بیشتری از اساتید شده‌است. این عدد تعداد ارجاع (citation) نام دارد و برای هر مقاله به‌صورت مستقل قابل محاسبه است.

حال فرض کنید یک استاد، $n$ مقاله منتشر کرده است و مقاله‌ی $i$ ام $a_i$ بار به‌عنوان منبع مقالات دیگر استفاده شده است. عدد h-index این استاد برابر $k$ است اگر حداقل $k$ مقاله داشته باشد، که حداقل $k$ بار به‌عنوان منبع به آن ارجاع داده باشند. اگر چند $k$ این ویژگی را دارد، بزرگ‌ترین آن را در نظر می‌گیرند.

ورودی🔗

در سطر اول ورودی $n$ یا تعداد مقالات می‌آید و در سطر بعد $n$ عدد می‌آید که $i$ ـمین آنها $a_i$ یا تعداد ارجاعات به مقاله $i$ ـم است. $1 \leq n \leq 300 \, 000$ $0 \le a_i \le 300 \, 000$

خروجی🔗

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

زیرمسئله	امتیاز
$n \leq 1000$	۱۰۰
بدون محدودیت اضافه	۱۰۰

مثال🔗

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

5
1 5 3 4 2

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

در این نمونه، ۳ عدد داریم که بزرگتر یا مساوی ۳ هستند (اعداد ۵، ۳ و ۴)

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

8
1 13 1 3 5 2 21 8

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

در این نمونه، ۴ عدد داریم که بزرگتر یا مساوی ۴ هستند (اعداد ۱۳، ۵، ۲۱ و ۸)

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- جدول کودوکو تعمیم جدول [سودوکو](https://fa.wikipedia.org/wiki/%D8%B3%D9%88%D8%AF%D9%88%DA%A9%D9%88) است. یک جدول $ab \times ab$ است. که از بلوک‌های $a \times b$ در یک جدول $b \times a$ تشکیل شده است. برای مثال شکل زیر، جدول کودوکو در حالت $a = 2$ و $b = 3$ است. ![توضیح تصویر](https://quera.org/qbox/view/wYKh9U2pAv/rsz_c.png) بازی جدول کودوکو دو نفره است. این دو نفر در ابتدا یک جدول کودوکو خالی روی میز قرار می‌دهند. بازی بین این دو نفر به نوبت انجام می‌شود. هر کس در نوبت خود یک عدد در یکی از خانه‌های خالی جدول می‌نویسد طوری که جدول معتبر بماند. کسی که نتواند چنین کاری را انجام دهد بازنده بازی است. جدول **معتبر** می‌ماند اگر هر دو عدد مساوی در سطر، ستون و بلوک متفاوت قرار گیرند. از شما می‌خواهیم این بازی را شبیه‌سازی کنید. یعنی ابعاد بازی و حرکات بازیکن‌ها به شما داده می‌شود. از شما می‌خواهیم بعد از انجام هر حرکت بگویید: + این حرکت مجاز نیست و یک خطا به بازیکنی که حرکت نادرست کرده نشان دهید. + این حرکت مجاز است و آن را اعمال کنید و عدد مورد نظر را در خانه مورد نظر قرار دهید و وضعیت جدول را چاپ کنید. **توجه کنید بعد از انجام یک حرکت اشتباه، نوبت همان بازیکنی است که حرکت اشتباه انجام داده است.** همچنین نیازی نیست جدول تکمیل شود و ممکن است بدون اینکه همه خانه‌های خالی جدول پر شود بازی به اتمام برسد. # ورودی در سطر اول دو عدد $a$ و $b$ به ترتیب می‌آید. $$ 1 \le a, b \le 3 $$ در سطر دوم عدد صحیح $n$ آمده است که نشان دهنده‌ی تعداد اتفاقاتی است که در بازی افتاده است. $$1 \le n \le 1000$$ سپس در $n$ سطر بعدی در هر سطر سه عدد $i$ و $j$ و $x$ آمده که نشان‌دهنده این است که این بازیکن می‌خواهد در خانه سطر $i$ام ستون $j$ام عدد $x$ را بنویسید. $$ 1 \le i, j, x \le a\times b$$ توجه کنید با توجه به قوانین بازی، نوبت‌ها به صورت یکتا مشخص می‌شود. # خروجی برای هر دستور اگر این دستور نشان‌دهنده حرکت نفر اول است پیام `player 1` و در صورتی که نشان‌دهنده حرکت نفر دوم است پیام `player 2` را در یک سطر مجزا چاپ کنید. برای هر دستور در صورت غیر مجاز بودن این حرکت، پیام خطای مربوطه را چاپ کنید و در غیر این صورت مشابه مثال‌های نمونه وضعیت جدول را چاپ کنید. **فاصله ها باید مطابق نمونه باشد.** # مثال ## ورودی نمونه ۱ ``` 3 3 5 1 9 5 9 1 4 1 9 3 9 9 5 9 9 6 ``` ## خروجی نمونه ۱ ``` player 1: ........5 ......... ......... ......... ......... ......... ......... ......... ......... player 2: ........5 ......... ......... ......... ......... ......... ......... ......... 4........ player 1: invalid move player 1: invalid move player 1: ........5 ......... ......... ......... ......... ......... ......... ......... 4.......6 ``` ## ورودی نمونه ۲ ``` 3 1 12 2 2 1 2 2 3 3 3 1 1 1 1 1 3 3 1 2 3 1 2 2 3 2 2 3 2 3 3 1 2 2 1 1 2 1 3 ``` ## خروجی نمونه ۲ ``` player 1: ... .1. ... player 2: invalid move player 2: ... .1. ..1 player 1: 1.. .1. ..1 player 2: 1.3 .1. ..1 player 1: invalid move player 1: 123 .1. ..1 player 2: invalid move player 2: 123 .1. .31 player 1: 123 .1. 231 player 2: invalid move player 2: 123 31. 231 ```

کودوکو

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

جدول کودوکو تعمیم جدول سودوکو است. یک جدول $ab \times ab$ است. که از بلوک‌های $a \times b$ در یک جدول $b \times a$ تشکیل شده است. برای مثال شکل زیر، جدول کودوکو در حالت $a = 2$ و $b = 3$ است.

توضیح تصویر

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

جدول معتبر می‌ماند اگر هر دو عدد مساوی در سطر، ستون و بلوک متفاوت قرار گیرند.

از شما می‌خواهیم این بازی را شبیه‌سازی کنید. یعنی ابعاد بازی و حرکات بازیکن‌ها به شما داده می‌شود. از شما می‌خواهیم بعد از انجام هر حرکت بگویید:

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

توجه کنید بعد از انجام یک حرکت اشتباه، نوبت همان بازیکنی است که حرکت اشتباه انجام داده است.

همچنین نیازی نیست جدول تکمیل شود و ممکن است بدون اینکه همه خانه‌های خالی جدول پر شود بازی به اتمام برسد.

ورودی🔗

در سطر اول دو عدد $a$ و $b$ به ترتیب می‌آید. $1 \le a, b \le 3$ در سطر دوم عدد صحیح $n$ آمده است که نشان دهنده‌ی تعداد اتفاقاتی است که در بازی افتاده است. $1 \le n \le 1000$ سپس در $n$ سطر بعدی در هر سطر سه عدد $i$ و $j$ و $x$ آمده که نشان‌دهنده این است که این بازیکن می‌خواهد در خانه سطر $i$ ام ستون $j$ ام عدد $x$ را بنویسید. $1 \le i, j, x \le a\times b$ توجه کنید با توجه به قوانین بازی، نوبت‌ها به صورت یکتا مشخص می‌شود.

خروجی🔗

برای هر دستور اگر این دستور نشان‌دهنده حرکت نفر اول است پیام player 1 و در صورتی که نشان‌دهنده حرکت نفر دوم است پیام player 2 را در یک سطر مجزا چاپ کنید.

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

فاصله ها باید مطابق نمونه باشد.

مثال🔗

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

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

player 1:
........5
.........
.........
.........
.........
.........
.........
.........
.........
player 2:
........5
.........
.........
.........
.........
.........
.........
.........
4........
player 1:
invalid move
player 1:
invalid move
player 1:
........5
.........
.........
.........
.........
.........
.........
.........
4.......6

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

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

player 1:
...
.1.
...
player 2:
invalid move
player 2:
...
.1.
..1
player 1:
1..
.1.
..1
player 2:
1.3
.1.
..1
player 1:
invalid move
player 1:
123
.1.
..1
player 2:
invalid move
player 2:
123
.1.
.31
player 1:
123
.1.
231
player 2:
invalid move
player 2:
123
31.
231

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- روی محور اعداد، $n$ بازه داریم. هر بازه به یکی از ۸ حالت زیر است: + نوع ۱. $(a, \infty)$ مجموعه همه‌ی اعداد بزرگ‌تر از $a$ است. + نوع ۲. $(-\infty, a)$ مجموعه همه‌ی اعداد کوچک‌تر از $a$ است. + نوع ۳. $[a, \infty)$ مجموعه همه‌ی اعداد بزرگ‌تر یا مساوی $a$ است. + نوع ۴. $(-\infty, a]$ مجموعه همه‌ی اعداد کوچک‌تر یا مساوی $a$ است. + نوع ۵. $(a, b)$ مجموعه همه‌ی اعداد بزرگ‌تر از $a$ و کوچکتر از $b$ است. + نوع ۶. $(a, b]$ مجموعه همه‌ی اعداد بزرگ‌تر از $a$ و کوچکتر یا مساوی $b$ است. + نوع ۷. $[a, b)$ مجموعه همه‌ی اعداد بزرگ‌تر یا مساوی $a$ و کوچکتر از $b$ است. + نوع ۸. $[a, b]$ مجموعه همه‌ی اعداد بزرگ‌تر یا مساوی $a$ و کوچکتر یا مساوی $b$ است. به شما $n$ بازه که به یکی از ۸ حالت بالا است داده می‌شود. از شما می‌خواهیم اجتماع این $n$ بازه را به روش استاندارد نمایش دهید. منظور از نمایش استاندارد یعنی تعدادی بازه ناتهی از ۸ حالت بالا انتخاب کنید و پشت سرهم بنویسید به طوری که هیچ دوتایی اشتراک نداشته باشند. برای کنار هم گذاشتن دو بازه از نماد `U` (اجتماع) استفاده کنید. (برای بهتر متوجه شدن خواسته‌ی سوال، به مثال‌ها توجه کنید.) # ورودی در سطر اول ورودی، عدد صحیح و مثبت $n$ آمده که تعداد بازه‌ها را نشان می‌دهد. $$1 \leq n \leq 100\, 000$$ در $n$ سطر بعدی، در هر سطر یک بازه از ۸ نوع معرفی شده به شما نمایش داده می‌شود. تضمین می‌شود بازه‌های داده شده درست و **ناتهی** هستند. مقدار بی‌نهایت ($\infty$) در ورودی به صورت `inf` نمایش داده می‌شود. تمامی اعداد حاضر در ورودی کوچکتر مساوی $10^9$ هستند. | زیرمسئله | امتیاز | | ----------- | ----------- | | $n \leq 500$ | ۱۵۰ | | بدون محدودیت اضافه | ۱۵۰ | # خروجی اجتماع این بازه‌ها را به روش استاندارد چاپ کنید. دقت کنید بازه‌های خروجی باید مرتب باشند. # مثال ## ورودی نمونه ۱ ``` 3 [-3, -1) (-2, 2) (4, 5] ``` ## خروجی نمونه ۱ ``` [-3, 2) U (4, 5] ``` ## ورودی نمونه ۲ ``` 3 (-inf, 3) (3, 7) [7, inf) ``` ## خروجی نمونه ۲ ``` (-inf, 3) U (3, inf) ``` ## ورودی نمونه ۳ ``` 2 (1, 2) [2, 3) ``` ## خروجی نمونه ۳ ``` (1, 3) ``` ## ورودی نمونه ۴ ``` 2 (1, 2) (2, 3) ``` ## خروجی نمونه ۴ ``` (1, 2) U (2, 3) ```

اجتماع بازه‌ها

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

روی محور اعداد، $n$ بازه داریم. هر بازه به یکی از ۸ حالت زیر است:

نوع ۱. $(a, \infty)$ مجموعه همه‌ی اعداد بزرگ‌تر از $a$ است.
نوع ۲. $(-\infty, a)$ مجموعه همه‌ی اعداد کوچک‌تر از $a$ است.
نوع ۳. $[a, \infty)$ مجموعه همه‌ی اعداد بزرگ‌تر یا مساوی $a$ است.
نوع ۴. $(-\infty, a]$ مجموعه همه‌ی اعداد کوچک‌تر یا مساوی $a$ است.
نوع ۵. $(a, b)$ مجموعه همه‌ی اعداد بزرگ‌تر از $a$ و کوچکتر از $b$ است.
نوع ۶. $(a, b]$ مجموعه همه‌ی اعداد بزرگ‌تر از $a$ و کوچکتر یا مساوی $b$ است.
نوع ۷. $[a, b)$ مجموعه همه‌ی اعداد بزرگ‌تر یا مساوی $a$ و کوچکتر از $b$ است.
نوع ۸. $[a, b]$ مجموعه همه‌ی اعداد بزرگ‌تر یا مساوی $a$ و کوچکتر یا مساوی $b$ است.

به شما $n$ بازه که به یکی از ۸ حالت بالا است داده می‌شود. از شما می‌خواهیم اجتماع این $n$ بازه را به روش استاندارد نمایش دهید.

منظور از نمایش استاندارد یعنی تعدادی بازه ناتهی از ۸ حالت بالا انتخاب کنید و پشت سرهم بنویسید به طوری که هیچ دوتایی اشتراک نداشته باشند. برای کنار هم گذاشتن دو بازه از نماد U (اجتماع) استفاده کنید. (برای بهتر متوجه شدن خواسته‌ی سوال، به مثال‌ها توجه کنید.)

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت $n$ آمده که تعداد بازه‌ها را نشان می‌دهد.

$1 \leq n \leq 100\, 000$

در $n$ سطر بعدی، در هر سطر یک بازه از ۸ نوع معرفی شده به شما نمایش داده می‌شود. تضمین می‌شود بازه‌های داده شده درست و ناتهی هستند. مقدار بی‌نهایت ( $\infty$ ) در ورودی به صورت inf نمایش داده می‌شود.

تمامی اعداد حاضر در ورودی کوچکتر مساوی $10^9$ هستند.

زیرمسئله	امتیاز
$n \leq 500$	۱۵۰
بدون محدودیت اضافه	۱۵۰

خروجی🔗

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

مثال🔗

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

3
[-3, -1)
(-2, 2)
(4, 5]

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

[-3, 2) U (4, 5]

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

3
(-inf, 3)
(3, 7)
[7, inf)

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

(-inf, 3) U (3, inf)

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

2
(1, 2)
[2, 3)

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

(1, 3)

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

2
(1, 2)
(2, 3)

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

(1, 2) U (2, 3)

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- می‌خواهیم سیستم پیشخوان یک رستوران را پیاده‌سازی کنیم. در این رستوران $n$ دستور داده می‌شود که از شما می‌خواهیم آن‌ها را مدیریت کنید. منوی غذایی که از آن سفارش می‌دهند $m$ غذای مختلف دارد که اسم و قیمت آن‌ها به شما داده می‌شود. تعداد میزهای رستوران برابر $k$ است که آن‌ها را با اعداد $1$ تا $k$ شماره‌گذاری می‌کنیم. تعداد صندلی‌های دور میز $i$ام برابر $s_i$ است. در ابتدا فرض کنید در ابتدا همه‌ی میزها آماده‌ی ارائه‌ی سرویس هستند. <details class="blue"> <summary> ثبت سفارش </summary> ساختار کلی این دستور به شکل زیر است. ``` order <food_1> <food_2> ... <seat> <timestamp> ``` در این درخواست مشتری سفارش **تعدادی** غذا می‌دهد و ما باید به این سفارش رسیدگی کنیم. رشته‌ی `<food_i>` ($i=1, 2, \dots$) از دو قسمت نام غذا و تعداد سفارش تشکیل شده که این دو قسمت با یک کاراکتر `X` از هم جدا شده‌اند. (به مثال‌ها مراجعه کنید.) در جای `<seat>` یک عدد به شما داده می‌شود و یعنی یک میز با حداقل این تعداد صندلی نیاز دارند. این سفارش در لحظه‌ی `<timestamp>` آمده است. اگر چنین میزی در رستوران نداریم، پیام `not enough seat.` را چاپ کنید. (این سفارش‌ها نباید شماره بخورند و پذیرفته شوند.) ولی اگر میزی با حداقل این تعداد صندلی در رستوران موجود است، باید این سفارش را شماره بزنید و ثبت کنید. شماره‌ی میزی را به این مشتری تخصیص دهید که حداقل تعداد صندلی مورد نیاز این مشتری را برطرف کند. همچنین این میز باید آماده ارائه سرویس شده باشد. اگر چندمیز با این ویژگی‌ها وجود داشت، میز با کمترین شماره را در قالب یک پیام `please sit at table number <t>.` اعلام کنید. ($t$ شماره‌ی میز مورد نظر است.) اگر چنین میزی در رستوران بود ولی در این لحظه آماده ارائه سرویس نبود، پیام `please wait for free table.` را اعلام کنید و این مشتری را به لیست انتظار اضافه کنید. </details> <details class="blue"> <summary> خروج یک مشتری </summary> ساختار کلی این دستور به شکل زیر است. (مواردی که داخل `<>` قرار دارند ورودی داده می‌شوند.) ``` payment <idx> <timestamp> ``` در اینجا مشتری که سفارش شماره‌ی `<idx>` را داده بود می‌خواهد از رستوران خارج شود. شما باید مجموع هزینه را به او اعلام کنید و آن مشتری پرداخت می‌کند. اگر این مشتری هنوز غذایش را نخورده و در صف انتظار میز خالی است، پولی از آن دریافت نکنید و پیام `pays after eating.` را چاپ کنید. همچنین به پرسنل رستوران اعلام می‌کنید که میزی که این سفارش را داده بودند، آماده‌ی سرویس کنند. این آماده کردن ۲ دقیقه طول می‌کشد. شما بعد از ۲ دقیقه اولین سفارشی که هنوز منتظر است و می‌تواند از آن میز استفاده کند را به میزش هدایت کنید و از صف انتظار خارج کنید. </details> <details class="blue"> <summary> گزارش وضعیت یک سفارش </summary> ``` order-status <id> <timestamp> ``` در این گزارش از شما می‌خواهیم وضعیت یک سفارش را در لحظه‌ی `<timestamp>` پیگیری کنید. + اگر مشتری در انتظار یک میز خالی است رشته‌ی `WAITING` را چاپ کنید. + اگر مشتری پشت یک میز در حال غذا خوردن است پیام `EATING` را چاپ کنید. + اگر مشتری پرداخت کرده و از رستوران خارج شده پیام `DONE` را چاپ کنید. </details> <details class="blue"> <summary> گزارش وضعیت یک میز </summary> ``` table-status <table> <timestamp> ``` در اینجا گزارش وضعیت یک میز را در لحظه‌ی `<timestamp>` پیگیری کنید. + اگر این میز آماده سرویس دهی است پیام `FREE` را چاپ کنید. + اگر این میز هنوز آماده‌ی سرویس‌دهی است پیام `PENDING` را چاپ کنید. + اگر مشتری پشت این میز مشغول غذا خوردن است پیام `BUSY` را چاپ کنید. </details> <details class="blue"> <summary> گزارش کلی </summary> ``` general-status <timestamp> ``` در این گزارش از شما می‌خواهیم موارد زیر را در لحظه‌ی `<timestamp>` حساب و به صورت ۸ عدد که با یک فاصله از هم جدا شده‌اند چاپ کنید. + درآمد امروز که پرداخت شده. + درآمد تا این لحظه که سفارش داده شده ولی هنوز پرداخت نشده. + تعداد سفارش‌های در لیست انتظار در این لحظه. + تعداد سفارش‌هایی که در این لحظه مشغول غذا خوردن هستند. + تعداد سفارش‌هایی که تا این لحظه با موفقیت کارشان تمام شده. + تعداد میزهایی که الان در آماده سرویس‌دهی هستند. + تعداد میزهایی که الان درحال آماده سازی است. + تعداد میزهایی که الان مشتری روی آن‌ها نشسته هستند. </details> ## نکات + در توضیحات پایین، مواردی که داخل `<>` قرار دارند، باید مقدار آن‌ها را در نظر بگیرید و در بقیه موارد همان کاراکترها را در نظر بگیرید. + هر `<timestamp>` در قالب `hh:mm:ss` داده می‌شود. در واقع فرض کنید همه‌ی سفارش‌ها در یک روز می‌آیند و تمام می‌شوند. + تمامی اعدادی که درباره‌ی محدودیت‌های آن صحبت نکردیم را بین ۱ تا ۲۰ در نظر بگیرید. + تضمین می‌شود در یک سفارش، دو غذا با نام یکسان ظاهر نمی‌شود. # ورودی در سطر اول ورودی، سه عدد صحیح $n$، $m$ و $k$ داده می‌شود که به ترتیب نشان دهنده‌ی تعداد اتفاقات، غذاها و میزها است. $$1 \leq n \leq 1000, \quad 1 \leq m, k \leq 100$$ در $m$ سطر بعدی، در هر سطر یک رشته $name$ و یک عدد $cost$ که با یک فاصله از هم جدا شده‌اند داده می‌شود. تضمین می‌شود رشته‌ی $name$ تنها شامل حروف کوچک انگلیسی است. $$1 \leq |name| \leq 10, \quad \quad 1 \leq cost \leq 1000 \, 000$$ در سطر بعدی، $k$ عدد صحیح در یک ردیف داده می‌شود که با یک فاصله از هم جدا می‌شوند. عدد $i$ام با $s_i$ است و نشان دهنده‌ی تعداد صندلی‌های میز $i$ام است. $$1 \leq s_i \leq 15$$ در $n$ سطر بعدی، یکی از درخواست‌های بالا با فرمت گفته شده داده می‌شود. تضمین می‌شود همه‌ی ورودی‌ها به **ترتیب زمانی** داده می‌شوند. | زیرمسئله | امتیاز | | ----------- | ----------- | | فقط دو دستور اول در ورودی داده می‌شود | ۲۰۰ | | بدون محدودیت اضافه | ۲۰۰ | # خروجی خروجی‌های درخواست‌های بالا را در یک سطر مجزا چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 9 3 4 pizza 120000 burger 80000 pasta 70000 2 1 4 2 order pizzaX1 burgerX3 3 12:00:00 order pizzaX2 2 14:00:00 order pastaX1 1 14:30:00 order pastaX1 1 14:45:00 payment 3 15:15:00 payment 1 15:30:00 payment 2 15:45:00 order burgerX2 1 16:00:00 payment 4 17:00:00 ``` ## خروجی نمونه ۱ ``` please sit at table number 3. please sit at table number 1. please sit at table number 2. please sit at table number 4. you should pay 70000 Toman. you should pay 360000 Toman. you should pay 240000 Toman. please sit at table number 2. you should pay 70000 Toman. ``` <details class="green"> <summary> توضیح نمونه ۱ </summary> در منوی رستوران، سه غذای «پیتزا»، «برگر» و «پاستا» وجود دارد که قیمت هر کدام از آن‌ها به‌ترتیب ۱۲۰، ۸۰ و ۷۰ هزار تومان است. این رستوران ۴ میز دارد که دور میز اول، ۲ صندلی، دور میز دوم، ۱ صندلی، دور میز سوم ۴ صندلی و دور میز چهارم ۲ صندلی وجود دارد. 1. ۳ نفر در ساعت ۱۲:۰۰ وارد رستوران می‌شوند. یک پیتزا و سه برگر سفارش می‌دهند. سفارش آن‌ها پذیرفته می‌شود و آن‌ها به میز شماره‌ی ۳ دعوت می‌شوند. (این سفارش شماره ۱ می‌شود.) 2. ۲ نفر در ساعت ۱۴:۰۰ وارد رستوران می‌شوند. دو پتیزا سفارش می‌دهند. سفارش آن‌ها پذیرفته می‌شود و به میز شماره ۱ دعوت می‌شوند. (این سفارش شماره ۲ می‌شود.) 3. ۱ نفر در ساعت ۱۴:۳۰ وارد رستوران می‌شود. یک پاستا سفارش می‌دهد. سفارش آن پذیرفته می‌شود و به میز شماره ۲ دعوت می‌شود. (این سفارش شماره ۳ می‌شود.) 4. ۱ نفر در ساعت ۱۴:۴۵ وارد رستوران می‌شود. یک پاستا سفارش می‌دهد. سفارش آن پذیرفته می‌شود و به میز شماره ۴ دعوت می‌شود. (این سفارش شماره ۴ می‌شود.) 5. سفارش شماره‌ی ۳ در ساعت ۱۵:۱۵ می‌خواهد از رستوران خارج شود. پس باید ۷۰ هزارتومان پرداخت کند. کارکنان رستوران میز شماره ۲ را تا ساعت ۱۵:۱۷ دقیقه آماده سرویس‌دهی می‌کنند. 6. سفارش شماره‌ی ۱ در ساعت ۱۵:۳۰ می‌خواهد از رستوران خارج شود. پس باید ۱۲۰ هزارتومان به‌علاوه‌ی سه‌تا ۸۰ هزارتومان پرداخت کند. کارکنان رستوران میز شماره ۳ را تا ساعت ۱۵:۳۲ دقیقه آماده سرویس‌دهی می‌کنند. 7. سفارش شماره‌ی ۲ در ساعت ۱۵:۴۵ می‌خواهد از رستوران خارج شود. پس باید دوتا ۱۲۰ هزارتومان پرداخت کند. کارکنان رستوران میز شماره ۱ را تا ساعت ۱۵:۴۷ دقیقه آماده سرویس‌دهی می‌کنند. 8. ۱ نفر در ساعت ۱۶:۰۰ وارد رستوران می‌شود. دو برگر سفارش می‌دهد. سفارش آن پذیرفته می‌شود و به میز شماره ۲ دعوت می‌شود. (این سفارش شماره ۴ می‌شود.) 9. سفارش شماره‌ی ۴ در ساعت ۱۷:۰۰ می‌خواهد از رستوران خارج شود. پس باید دوتا ۸۰ هزارتومان پرداخت کند. کارکنان رستوران میز شماره ۲ را تا ساعت ۱۷:۰۲ دقیقه آماده سرویس‌دهی می‌کنند. </details> ## ورودی نمونه ۲ ``` 16 4 2 joje 60000 kubide 70000 soltani 80000 negini 75000 2 4 general-status 08:00:00 table-status 1 08:30:00 table-status 2 09:00:00 order jojeX1 soltaniX1 kubideX2 neginiX1 4 09:30:00 table-status 1 10:00:00 table-status 2 10:30:00 order-status 1 11:00:00 order jojeX3 soltaniX2 kubideX3 7 11:30:00 order neginiX2 2 12:30:00 general-status 13:30:00 payment 1 14:00:00 general-status 14:30:00 order-status 1 15:00:00 payment 2 15:30:00 order-status 2 16:00:00 general-status 17:00:00 ``` ## خروجی نمونه ۲ ``` 0 0 0 0 0 2 0 0 FREE FREE please sit at table number 2. FREE BUSY EATING not enough seat. please sit at table number 1. 0 505000 0 2 0 0 0 2 you should pay 355000 Toman. 355000 150000 0 1 1 1 0 1 DONE you should pay 150000 Toman. DONE 505000 0 0 0 2 2 0 0 ``` <details class="green"> <summary> توضیح نمونه ۲ </summary> در منوی رستوران، چهار غذای «جوجه»، «کوبیده»، «سلطانی» و «نگینی» وجود دارد که قیمت هر کدام از آن‌ها به‌ترتیب ۶۰، ۷۰، ۸۰ و ۷۵ هزار تومان است. این رستوران ۲ میز دارد که دور میز اول، ۲ صندلی و دور میز دوم، ۴ صندلی وجود دارد. 1. در ساعت ۸:۰۰ هیچ پولی نیامده و هیچ پولی قرار نیست که دریافت شود پس دو عدد اول ۰ است. چون هیچ سفارشی نیامده سه عدد بعدی هم ۰ است. چون دو میز آماده‌ی سرویس‌دهی است پس عدد بعدی ۲ بقیه اعداد ۰‌اند. 2. در ساعت ۸:۳۰، وضعیت میز شماره ۱ آماده سرویس‌دهی است. 3. در ساعت ۹:۰۰، وضعیت میز شماره ۲ آماده سرویس‌دهی است. 4. ۴ نفر در ساعت ۹:۳۰ وارد رستوران می‌شوند. یک جوجه، یک سلطانی، دو کوبیده و یک نگینی سفارش می‌دهند. سفارش آن‌ها پذیرفته می‌شود و آن‌ها به میز شماره‌ی ۲ دعوت می‌شوند. (این سفارش شماره ۱ می‌شود.) 5. در ساعت ۱۰:۰۰، وضعیت میز شماره ۱ آماده سرویس‌دهی است. 6. در ساعت ۱۰:۳۰، وضعیت میز شماره ۲ مشغول است. 7. در ساعت ۱۱:۰۰، وضعیت سفارش اول مشغول غذا خوردن هستند. 8. ۷ نفر در ساعت ۱۱:۳۰ وارد رستوران می‌شوند. سه جوجه، دو سلطانی و سه کوبیده سفارش می‌دهند. سفارش آن‌ها پذیرفته نمی‌شود چون هیچ میزی با ۷ صندلی در این رستوران وجود ندارد. 9. ۲ نفر در ساعت ۱۲:۳۰ وارد رستوران می‌شوند. دو نگینی سفارش می‌دهند. سفارش آن‌ها پذیرفته می‌شود و آن‌ها به میز شماره‌ی ۱ دعوت می‌شوند. (این سفارش شماره ۲ می‌شود.) 10. در ساعت ۱۳:۳۰ دو سفارش آمده هنوز دریافت نشده مجموع مبلغ این سفارش‌ها ۵۰۵ هزار تومان است. چون هیچ سفارشی هنوز پرداخت نکرده، عدد بعدی هم ۰ است. چون دو میز آماده‌ی سرویس‌دهی است پس عدد بعدی ۲ بقیه اعداد ۰‌ اند. چون روی هر دو میز مشغول غذا خوردن هستند سه عدد بعدی ۰ ۲ ۰ است و سه عدد آخر ۰ ۰ ۲ می‌شوند. 11. سفارش شماره‌ی ۱ در ساعت ۱۴:۰۰ می‌خواهد از رستوران خارج شود. پس باید ۳۵۵ هزارتومان پرداخت کند. کارکنان رستوران میز شماره ۲ را تا ساعت ۱۴:۰۲ آماده سرویس‌دهی می‌کنند. 12. در ساعت ۱۴:۳۰ سفارش ۱ پرداخت شده پس مبلغ ۳۵۵ هزارتومان پرداخت شده و ۱۵۰ هزار تومان سفارش ۲ هنوز پرداخت نشده است. در این لحظه یک سفارش تمام شده و یک سفارش مشغول غذا خوردن است و هیچ سفارشی در انتظار نیست. روی یک میز مشغول غذا خوردن هستند و یک میز آماده‌ی سرویس‌دهی است. 13. در ساعت ۱۵:۰۰ وضعیت سفارش ۱ انجام شده است. 14. در ساعت ۱۵:۳۰ سفارش دوم پرداخت می‌کند و از رستوران خارج می‌شود. میز شماره ۱ ساعت ۱۵:۳۲ آماده سرویس‌دهی می‌شود. 15. در ساعت ۱۶:۰۰ وضعیت این سفارش نیز تمام شده است. 16. در ساعت ۱۷:۰۰ همه‌ی مبالغ پرداخت شده و هر دو میز آماده‌ی سرویس‌دهی و هر دو سفارش تمام شده. </details> ## ورودی نمونه ۳ ``` 25 1 1 omlet 10000 1 table-status 1 18:00:00 order omletX2 2 19:00:00 order omletX1 1 19:00:30 order omletX10 1 19:01:30 order omletX9 1 19:01:31 order omletX2 2 19:02:30 order-status 1 19:02:35 order-status 2 19:02:36 order-status 3 19:02:37 table-status 1 19:02:38 payment 2 19:03:00 payment 1 19:03:01 order-status 1 19:04:05 order-status 2 19:04:06 order-status 3 19:04:07 table-status 1 19:04:08 general-status 19:04:09 order-status 1 19:05:05 order-status 2 19:05:06 order-status 3 19:05:07 table-status 1 19:05:08 payment 2 19:05:09 table-status 1 19:06:18 table-status 1 19:07:18 general-status 19:20:00 ``` ## خروجی نمونه ۲ ``` FREE not enough seat. please sit at table number 1. please wait for free table. please wait for free table. not enough seat. EATING WAITING WAITING BUSY pays after eating. you should pay 10000 Toman. DONE WAITING WAITING PENDING 10000 190000 2 0 1 0 1 0 DONE EATING WAITING BUSY you should pay 100000 Toman. PENDING BUSY 110000 90000 0 1 2 0 0 1 ``` <details class="green"> <summary> توضیح نمونه ۳ </summary> در منوی رستوران، فقط غذای «املت» وجود دارد که قیمت آن ۱۰ هزار تومان است. این رستوران فقط یک میز دارد که دور میز آن ۱ صندلی وجود دارد. 1. وضعیت میز در لحظه‌ی ۱۸:۰۰:۰۰ پرسیده شد که خالی و آماده‌ی سرویس‌دهی است. 2. ۲ نفر در لحظه ۱۹:۰۰:۰۰ وارد رستوران می‌شوند و ۲ املت سفارش می‌دهند. سفارش آن‌ها پذیرفته نمی‌شود چون هیچ میزی با حداقل ۲ صندلی در این رستوران نداریم. 3. ۱ نفر در لحظه ۱۹:۰۰:۳۰ وارد رستوران می‌شوند و ۱ املت سفارش می‌دهد. سفارش او پذیرفته می‌شود و به میز شماره‌ی ۱ دعوت می‌شوند. (این سفارش شماره ۱ می‌شود.) 4. ۱ نفر در لحظه ۱۹:۰۱:۳۰ وارد رستوران می‌شوند و ۱۰ املت سفارش می‌دهد. سفارش او پذیرفته می‌شود ولی چون میز خالی وجود ندارد باید به صف انتظار اضافه شود. (این سفارش شماره ۲ می‌شود.) 5. ۱ نفر در لحظه ۱۹:۰۱:۳۱ وارد رستوران می‌شوند و ۹ املت سفارش می‌دهد. سفارش او پذیرفته می‌شود ولی چون میز خالی وجود ندارد باید به صف انتظار اضافه شود. (این سفارش شماره ۳ می‌شود.) 6. ۲ نفر در لحظه ۱۹:۰۲:۳۰ وارد رستوران می‌شوند و ۲ املت سفارش می‌دهند. سفارش آن‌ها پذیرفته نمی‌شود چون هیچ میزی با حداقل ۲ صندلی در این رستوران نداریم. 7. در لحظه ۱۹:۰۲:۳۵، سفارش شماره ۱ مشغول غذا خوردن است. 8. در لحظه ۱۹:۰۲:۳۶، سفارش شماره ۲ در صف انتظار است. 9. در لحظه ۱۹:۰۲:۳۷، سفارش شماره ۳ در صف انتظار است. 10. در لحظه ۱۹:۰۲:۳۸، روی میز شماره ۱ مشغول غذا خوردن هستند. (سفارش دهنده‌ی شماره ۱) 11. در لحظه ۱۹:۰۳:۰۰، سفارش شماره ۲ می‌خواهد پرداخت کند اما چون هنوز غذایش را نخورده و در صف انتظار است نباید از او پولی بگیریم. 12. در لحظه ۱۹:۰۳:۰۱، سفارش شماره‌ی ۱ می‌خواهد پرداخت کند. او باید مبلغ ۱۰ هزارتومان پرداخت کند و خارج شود. میز او توسط کارکنان در لحظه‌ی ۱۹:۰۵:۰۱ آماده سرویس‌دهی می‌شود. 13. در لحظه ۱۹:۰۴:۰۵، سفارش شماره ۱ مشغول خارج شده است. 14. در لحظه ۱۹:۰۴:۰۶، سفارش شماره ۲ همچنان منتظر است. (چون هنوز میز آماده نشده.) 15. در لحظه ۱۹:۰۴:۰۷، سفارش شماره ۳ همچنان در صف انتظار است. 16. در لحظه ۱۹:۰۴:۰۸، میز شماره ۱ در حال تمیز شدن است. 17. در لحظه ۱۹:۰۴:۰۹، مجموع درآمد ۱۰ هزار تومان پرداخت شده و ۱۹۰ هزارتومان قرار است پرداخت شود. ۱ سفارش کارش تمام شده است و ۲ سفارش منتظر است. یک میز در حال آماده سازی است. 18. در لحظه ۱۹:۰۵:۰۵، سفارش شماره ۱ مشغول خارج شده است. 19. در لحظه ۱۹:۰۵:۰۶، سفارش شماره ۲ مشغول غذا خوردن است. 20. در لحظه ۱۹:۰۵:۰۷، سفارش شماره ۳ در صف انتظار است. 21. در لحظه ۱۹:۰۵:۰۸، میز شماره ۱ در حال غذا خوردن است. 22. در لحظه ۱۹:۰۵:۰۹، سفارش شماره‌ی ۲ می‌خواهد پرداخت کند. او باید ۱۰ تا ۱۰ هزارتومان پرداخت کند و خارج شود. میز او توسط کارکنان در لحظه‌ی ۱۹:۰۷:۰۹ آماده سرویس‌دهی می‌شود. 23. در لحظه ۱۹:۰۶:۱۸، میز شماره ۱ در حال تمیز شدن است. 24. در لحظه ۱۹:۰۷:۱۸، میز شماره ۱ در حال غذا خوردن است. 25. مجموع درآمد ۱۱۰ هزار تومان پرداخت شده و ۹۰ هزارتومان قرار است پرداخت شود. ۱ سفارش مشغول خوردن و ۲ سفارش کارشان تمام شده است و روی یک میز مشغول غذا خوردن هستند. </details>

پیشخوان رستوران

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

می‌خواهیم سیستم پیشخوان یک رستوران را پیاده‌سازی کنیم. در این رستوران $n$ دستور داده می‌شود که از شما می‌خواهیم آن‌ها را مدیریت کنید.

منوی غذایی که از آن سفارش می‌دهند $m$ غذای مختلف دارد که اسم و قیمت آن‌ها به شما داده می‌شود.

تعداد میزهای رستوران برابر $k$ است که آن‌ها را با اعداد $1$ تا $k$ شماره‌گذاری می‌کنیم. تعداد صندلی‌های دور میز $i$ ام برابر $s_i$ است. در ابتدا فرض کنید در ابتدا همه‌ی میزها آماده‌ی ارائه‌ی سرویس هستند.

ثبت سفارش

ساختار کلی این دستور به شکل زیر است.

order <food_1> <food_2> ... <seat> <timestamp>

در این درخواست مشتری سفارش تعدادی غذا می‌دهد و ما باید به این سفارش رسیدگی کنیم. رشته‌ی <food_i> ( $i=1, 2, \dots$ ) از دو قسمت نام غذا و تعداد سفارش تشکیل شده که این دو قسمت با یک کاراکتر X از هم جدا شده‌اند. (به مثال‌ها مراجعه کنید.) در جای <seat> یک عدد به شما داده می‌شود و یعنی یک میز با حداقل این تعداد صندلی نیاز دارند. این سفارش در لحظه‌ی <timestamp> آمده است.

اگر چنین میزی در رستوران نداریم، پیام not enough seat. را چاپ کنید. (این سفارش‌ها نباید شماره بخورند و پذیرفته شوند.) ولی اگر میزی با حداقل این تعداد صندلی در رستوران موجود است، باید این سفارش را شماره بزنید و ثبت کنید.

شماره‌ی میزی را به این مشتری تخصیص دهید که حداقل تعداد صندلی مورد نیاز این مشتری را برطرف کند. همچنین این میز باید آماده ارائه سرویس شده باشد. اگر چندمیز با این ویژگی‌ها وجود داشت، میز با کمترین شماره را در قالب یک پیام please sit at table number <t>. اعلام کنید. ( $t$ شماره‌ی میز مورد نظر است.)

اگر چنین میزی در رستوران بود ولی در این لحظه آماده ارائه سرویس نبود، پیام please wait for free table. را اعلام کنید و این مشتری را به لیست انتظار اضافه کنید.

خروج یک مشتری

ساختار کلی این دستور به شکل زیر است. (مواردی که داخل <> قرار دارند ورودی داده می‌شوند.)

payment <idx> <timestamp>

در اینجا مشتری که سفارش شماره‌ی <idx> را داده بود می‌خواهد از رستوران خارج شود. شما باید مجموع هزینه را به او اعلام کنید و آن مشتری پرداخت می‌کند.

اگر این مشتری هنوز غذایش را نخورده و در صف انتظار میز خالی است، پولی از آن دریافت نکنید و پیام pays after eating. را چاپ کنید.

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

گزارش وضعیت یک سفارش

order-status <id> <timestamp>

در این گزارش از شما می‌خواهیم وضعیت یک سفارش را در لحظه‌ی <timestamp> پیگیری کنید.

اگر مشتری در انتظار یک میز خالی است رشته‌ی WAITING را چاپ کنید.
اگر مشتری پشت یک میز در حال غذا خوردن است پیام EATING را چاپ کنید.
اگر مشتری پرداخت کرده و از رستوران خارج شده پیام DONE را چاپ کنید.

گزارش وضعیت یک میز

table-status <table> <timestamp>

در اینجا گزارش وضعیت یک میز را در لحظه‌ی <timestamp> پیگیری کنید.

اگر این میز آماده سرویس دهی است پیام FREE را چاپ کنید.
اگر این میز هنوز آماده‌ی سرویس‌دهی است پیام PENDING را چاپ کنید.
اگر مشتری پشت این میز مشغول غذا خوردن است پیام BUSY را چاپ کنید.

گزارش کلی

general-status <timestamp>

در این گزارش از شما می‌خواهیم موارد زیر را در لحظه‌ی <timestamp> حساب و به صورت ۸ عدد که با یک فاصله از هم جدا شده‌اند چاپ کنید.

درآمد امروز که پرداخت شده.
درآمد تا این لحظه که سفارش داده شده ولی هنوز پرداخت نشده.
تعداد سفارش‌های در لیست انتظار در این لحظه.
تعداد سفارش‌هایی که در این لحظه مشغول غذا خوردن هستند.
تعداد سفارش‌هایی که تا این لحظه با موفقیت کارشان تمام شده.
تعداد میزهایی که الان در آماده سرویس‌دهی هستند.
تعداد میزهایی که الان درحال آماده سازی است.
تعداد میزهایی که الان مشتری روی آن‌ها نشسته هستند.

نکات🔗

در توضیحات پایین، مواردی که داخل <> قرار دارند، باید مقدار آن‌ها را در نظر بگیرید و در بقیه موارد همان کاراکترها را در نظر بگیرید.
هر <timestamp> در قالب hh:mm:ss داده می‌شود. در واقع فرض کنید همه‌ی سفارش‌ها در یک روز می‌آیند و تمام می‌شوند.
تمامی اعدادی که درباره‌ی محدودیت‌های آن صحبت نکردیم را بین ۱ تا ۲۰ در نظر بگیرید.
تضمین می‌شود در یک سفارش، دو غذا با نام یکسان ظاهر نمی‌شود.

ورودی🔗

در سطر اول ورودی، سه عدد صحیح $n$ ، $m$ و $k$ داده می‌شود که به ترتیب نشان دهنده‌ی تعداد اتفاقات، غذاها و میزها است.

$1 \leq n \leq 1000, \quad 1 \leq m, k \leq 100$

در $m$ سطر بعدی، در هر سطر یک رشته $name$ و یک عدد $cost$ که با یک فاصله از هم جدا شده‌اند داده می‌شود. تضمین می‌شود رشته‌ی $name$ تنها شامل حروف کوچک انگلیسی است.

$1 \leq |name| \leq 10, \quad \quad 1 \leq cost \leq 1000 \, 000$

در سطر بعدی، $k$ عدد صحیح در یک ردیف داده می‌شود که با یک فاصله از هم جدا می‌شوند. عدد $i$ ام با $s_i$ است و نشان دهنده‌ی تعداد صندلی‌های میز $i$ ام است.

$1 \leq s_i \leq 15$

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

زیرمسئله	امتیاز
فقط دو دستور اول در ورودی داده می‌شود	۲۰۰
بدون محدودیت اضافه	۲۰۰

خروجی🔗

خروجی‌های درخواست‌های بالا را در یک سطر مجزا چاپ کنید.

مثال‌ها🔗

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

9 3 4
pizza 120000
burger 80000
pasta 70000
2 1 4 2
order pizzaX1 burgerX3 3 12:00:00
order pizzaX2 2 14:00:00
order pastaX1 1 14:30:00
order pastaX1 1 14:45:00
payment 3 15:15:00
payment 1 15:30:00
payment 2 15:45:00
order burgerX2 1 16:00:00
payment 4 17:00:00

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

please sit at table number 3.
please sit at table number 1.
please sit at table number 2.
please sit at table number 4.
you should pay 70000 Toman.
you should pay 360000 Toman.
you should pay 240000 Toman.
please sit at table number 2.
you should pay 70000 Toman.

توضیح نمونه ۱

در منوی رستوران، سه غذای «پیتزا»، «برگر» و «پاستا» وجود دارد که قیمت هر کدام از آن‌ها به‌ترتیب ۱۲۰، ۸۰ و ۷۰ هزار تومان است.

این رستوران ۴ میز دارد که دور میز اول، ۲ صندلی، دور میز دوم، ۱ صندلی، دور میز سوم ۴ صندلی و دور میز چهارم ۲ صندلی وجود دارد.

۳ نفر در ساعت ۱۲:۰۰ وارد رستوران می‌شوند. یک پیتزا و سه برگر سفارش می‌دهند. سفارش آن‌ها پذیرفته می‌شود و آن‌ها به میز شماره‌ی ۳ دعوت می‌شوند. (این سفارش شماره ۱ می‌شود.)
۲ نفر در ساعت ۱۴:۰۰ وارد رستوران می‌شوند. دو پتیزا سفارش می‌دهند. سفارش آن‌ها پذیرفته می‌شود و به میز شماره ۱ دعوت می‌شوند. (این سفارش شماره ۲ می‌شود.)
۱ نفر در ساعت ۱۴:۳۰ وارد رستوران می‌شود. یک پاستا سفارش می‌دهد. سفارش آن پذیرفته می‌شود و به میز شماره ۲ دعوت می‌شود. (این سفارش شماره ۳ می‌شود.)
۱ نفر در ساعت ۱۴:۴۵ وارد رستوران می‌شود. یک پاستا سفارش می‌دهد. سفارش آن پذیرفته می‌شود و به میز شماره ۴ دعوت می‌شود. (این سفارش شماره ۴ می‌شود.)
سفارش شماره‌ی ۳ در ساعت ۱۵:۱۵ می‌خواهد از رستوران خارج شود. پس باید ۷۰ هزارتومان پرداخت کند. کارکنان رستوران میز شماره ۲ را تا ساعت ۱۵:۱۷ دقیقه آماده سرویس‌دهی می‌کنند.
سفارش شماره‌ی ۱ در ساعت ۱۵:۳۰ می‌خواهد از رستوران خارج شود. پس باید ۱۲۰ هزارتومان به‌علاوه‌ی سه‌تا ۸۰ هزارتومان پرداخت کند. کارکنان رستوران میز شماره ۳ را تا ساعت ۱۵:۳۲ دقیقه آماده سرویس‌دهی می‌کنند.
سفارش شماره‌ی ۲ در ساعت ۱۵:۴۵ می‌خواهد از رستوران خارج شود. پس باید دوتا ۱۲۰ هزارتومان پرداخت کند. کارکنان رستوران میز شماره ۱ را تا ساعت ۱۵:۴۷ دقیقه آماده سرویس‌دهی می‌کنند.
۱ نفر در ساعت ۱۶:۰۰ وارد رستوران می‌شود. دو برگر سفارش می‌دهد. سفارش آن پذیرفته می‌شود و به میز شماره ۲ دعوت می‌شود. (این سفارش شماره ۴ می‌شود.)
سفارش شماره‌ی ۴ در ساعت ۱۷:۰۰ می‌خواهد از رستوران خارج شود. پس باید دوتا ۸۰ هزارتومان پرداخت کند. کارکنان رستوران میز شماره ۲ را تا ساعت ۱۷:۰۲ دقیقه آماده سرویس‌دهی می‌کنند.

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

16 4 2
joje 60000
kubide 70000
soltani 80000
negini 75000
2 4
general-status 08:00:00
table-status 1 08:30:00
table-status 2 09:00:00
order jojeX1 soltaniX1 kubideX2 neginiX1 4 09:30:00
table-status 1 10:00:00
table-status 2 10:30:00
order-status 1 11:00:00
order jojeX3 soltaniX2 kubideX3 7 11:30:00
order neginiX2 2 12:30:00
general-status 13:30:00
payment 1 14:00:00
general-status 14:30:00
order-status 1 15:00:00
payment 2 15:30:00
order-status 2 16:00:00
general-status 17:00:00

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

0 0 0 0 0 2 0 0
FREE
FREE
please sit at table number 2.
FREE
BUSY
EATING
not enough seat.
please sit at table number 1.
0 505000 0 2 0 0 0 2
you should pay 355000 Toman.
355000 150000 0 1 1 1 0 1
DONE
you should pay 150000 Toman.
DONE
505000 0 0 0 2 2 0 0

توضیح نمونه ۲

در منوی رستوران، چهار غذای «جوجه»، «کوبیده»، «سلطانی» و «نگینی» وجود دارد که قیمت هر کدام از آن‌ها به‌ترتیب ۶۰، ۷۰، ۸۰ و ۷۵ هزار تومان است.

این رستوران ۲ میز دارد که دور میز اول، ۲ صندلی و دور میز دوم، ۴ صندلی وجود دارد.

در ساعت ۸:۰۰ هیچ پولی نیامده و هیچ پولی قرار نیست که دریافت شود پس دو عدد اول ۰ است. چون هیچ سفارشی نیامده سه عدد بعدی هم ۰ است. چون دو میز آماده‌ی سرویس‌دهی است پس عدد بعدی ۲ بقیه اعداد ۰‌اند.
در ساعت ۸:۳۰، وضعیت میز شماره ۱ آماده سرویس‌دهی است.
در ساعت ۹:۰۰، وضعیت میز شماره ۲ آماده سرویس‌دهی است.
۴ نفر در ساعت ۹:۳۰ وارد رستوران می‌شوند. یک جوجه، یک سلطانی، دو کوبیده و یک نگینی سفارش می‌دهند. سفارش آن‌ها پذیرفته می‌شود و آن‌ها به میز شماره‌ی ۲ دعوت می‌شوند. (این سفارش شماره ۱ می‌شود.)
در ساعت ۱۰:۰۰، وضعیت میز شماره ۱ آماده سرویس‌دهی است.
در ساعت ۱۰:۳۰، وضعیت میز شماره ۲ مشغول است.
در ساعت ۱۱:۰۰، وضعیت سفارش اول مشغول غذا خوردن هستند.
۷ نفر در ساعت ۱۱:۳۰ وارد رستوران می‌شوند. سه جوجه، دو سلطانی و سه کوبیده سفارش می‌دهند. سفارش آن‌ها پذیرفته نمی‌شود چون هیچ میزی با ۷ صندلی در این رستوران وجود ندارد.
۲ نفر در ساعت ۱۲:۳۰ وارد رستوران می‌شوند. دو نگینی سفارش می‌دهند. سفارش آن‌ها پذیرفته می‌شود و آن‌ها به میز شماره‌ی ۱ دعوت می‌شوند. (این سفارش شماره ۲ می‌شود.)
در ساعت ۱۳:۳۰ دو سفارش آمده هنوز دریافت نشده مجموع مبلغ این سفارش‌ها ۵۰۵ هزار تومان است. چون هیچ سفارشی هنوز پرداخت نکرده، عدد بعدی هم ۰ است. چون دو میز آماده‌ی سرویس‌دهی است پس عدد بعدی ۲ بقیه اعداد ۰‌ اند. چون روی هر دو میز مشغول غذا خوردن هستند سه عدد بعدی ۰ ۲ ۰ است و سه عدد آخر ۰ ۰ ۲ می‌شوند.
سفارش شماره‌ی ۱ در ساعت ۱۴:۰۰ می‌خواهد از رستوران خارج شود. پس باید ۳۵۵ هزارتومان پرداخت کند. کارکنان رستوران میز شماره ۲ را تا ساعت ۱۴:۰۲ آماده سرویس‌دهی می‌کنند.
در ساعت ۱۴:۳۰ سفارش ۱ پرداخت شده پس مبلغ ۳۵۵ هزارتومان پرداخت شده و ۱۵۰ هزار تومان سفارش ۲ هنوز پرداخت نشده است. در این لحظه یک سفارش تمام شده و یک سفارش مشغول غذا خوردن است و هیچ سفارشی در انتظار نیست. روی یک میز مشغول غذا خوردن هستند و یک میز آماده‌ی سرویس‌دهی است.
در ساعت ۱۵:۰۰ وضعیت سفارش ۱ انجام شده است.
در ساعت ۱۵:۳۰ سفارش دوم پرداخت می‌کند و از رستوران خارج می‌شود. میز شماره ۱ ساعت ۱۵:۳۲ آماده سرویس‌دهی می‌شود.
در ساعت ۱۶:۰۰ وضعیت این سفارش نیز تمام شده است.
در ساعت ۱۷:۰۰ همه‌ی مبالغ پرداخت شده و هر دو میز آماده‌ی سرویس‌دهی و هر دو سفارش تمام شده.

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

25 1 1
omlet 10000
1
table-status 1 18:00:00
order omletX2 2 19:00:00
order omletX1 1 19:00:30
order omletX10 1 19:01:30
order omletX9 1 19:01:31
order omletX2 2 19:02:30
order-status 1 19:02:35
order-status 2 19:02:36
order-status 3 19:02:37
table-status 1 19:02:38
payment 2 19:03:00
payment 1 19:03:01
order-status 1 19:04:05
order-status 2 19:04:06
order-status 3 19:04:07
table-status 1 19:04:08
general-status 19:04:09
order-status 1 19:05:05
order-status 2 19:05:06
order-status 3 19:05:07
table-status 1 19:05:08
payment 2 19:05:09
table-status 1 19:06:18
table-status 1 19:07:18
general-status 19:20:00

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

FREE
not enough seat.
please sit at table number 1.
please wait for free table.
please wait for free table.
not enough seat.
EATING
WAITING
WAITING
BUSY
pays after eating.
you should pay 10000 Toman.
DONE
WAITING
WAITING
PENDING
10000 190000 2 0 1 0 1 0
DONE
EATING
WAITING
BUSY
you should pay 100000 Toman.
PENDING
BUSY
110000 90000 0 1 2 0 0 1

توضیح نمونه ۳

در منوی رستوران، فقط غذای «املت» وجود دارد که قیمت آن ۱۰ هزار تومان است. این رستوران فقط یک میز دارد که دور میز آن ۱ صندلی وجود دارد.

وضعیت میز در لحظه‌ی ۱۸:۰۰:۰۰ پرسیده شد که خالی و آماده‌ی سرویس‌دهی است.
۲ نفر در لحظه ۱۹:۰۰:۰۰ وارد رستوران می‌شوند و ۲ املت سفارش می‌دهند. سفارش آن‌ها پذیرفته نمی‌شود چون هیچ میزی با حداقل ۲ صندلی در این رستوران نداریم.
۱ نفر در لحظه ۱۹:۰۰:۳۰ وارد رستوران می‌شوند و ۱ املت سفارش می‌دهد. سفارش او پذیرفته می‌شود و به میز شماره‌ی ۱ دعوت می‌شوند. (این سفارش شماره ۱ می‌شود.)
۱ نفر در لحظه ۱۹:۰۱:۳۰ وارد رستوران می‌شوند و ۱۰ املت سفارش می‌دهد. سفارش او پذیرفته می‌شود ولی چون میز خالی وجود ندارد باید به صف انتظار اضافه شود. (این سفارش شماره ۲ می‌شود.)
۱ نفر در لحظه ۱۹:۰۱:۳۱ وارد رستوران می‌شوند و ۹ املت سفارش می‌دهد. سفارش او پذیرفته می‌شود ولی چون میز خالی وجود ندارد باید به صف انتظار اضافه شود. (این سفارش شماره ۳ می‌شود.)
۲ نفر در لحظه ۱۹:۰۲:۳۰ وارد رستوران می‌شوند و ۲ املت سفارش می‌دهند. سفارش آن‌ها پذیرفته نمی‌شود چون هیچ میزی با حداقل ۲ صندلی در این رستوران نداریم.
در لحظه ۱۹:۰۲:۳۵، سفارش شماره ۱ مشغول غذا خوردن است.
در لحظه ۱۹:۰۲:۳۶، سفارش شماره ۲ در صف انتظار است.
در لحظه ۱۹:۰۲:۳۷، سفارش شماره ۳ در صف انتظار است.
در لحظه ۱۹:۰۲:۳۸، روی میز شماره ۱ مشغول غذا خوردن هستند. (سفارش دهنده‌ی شماره ۱)
در لحظه ۱۹:۰۳:۰۰، سفارش شماره ۲ می‌خواهد پرداخت کند اما چون هنوز غذایش را نخورده و در صف انتظار است نباید از او پولی بگیریم.
در لحظه ۱۹:۰۳:۰۱، سفارش شماره‌ی ۱ می‌خواهد پرداخت کند. او باید مبلغ ۱۰ هزارتومان پرداخت کند و خارج شود. میز او توسط کارکنان در لحظه‌ی ۱۹:۰۵:۰۱ آماده سرویس‌دهی می‌شود.
در لحظه ۱۹:۰۴:۰۵، سفارش شماره ۱ مشغول خارج شده است.
در لحظه ۱۹:۰۴:۰۶، سفارش شماره ۲ همچنان منتظر است. (چون هنوز میز آماده نشده.)
در لحظه ۱۹:۰۴:۰۷، سفارش شماره ۳ همچنان در صف انتظار است.
در لحظه ۱۹:۰۴:۰۸، میز شماره ۱ در حال تمیز شدن است.
در لحظه ۱۹:۰۴:۰۹، مجموع درآمد ۱۰ هزار تومان پرداخت شده و ۱۹۰ هزارتومان قرار است پرداخت شود. ۱ سفارش کارش تمام شده است و ۲ سفارش منتظر است. یک میز در حال آماده سازی است.
در لحظه ۱۹:۰۵:۰۵، سفارش شماره ۱ مشغول خارج شده است.
در لحظه ۱۹:۰۵:۰۶، سفارش شماره ۲ مشغول غذا خوردن است.
در لحظه ۱۹:۰۵:۰۷، سفارش شماره ۳ در صف انتظار است.
در لحظه ۱۹:۰۵:۰۸، میز شماره ۱ در حال غذا خوردن است.
در لحظه ۱۹:۰۵:۰۹، سفارش شماره‌ی ۲ می‌خواهد پرداخت کند. او باید ۱۰ تا ۱۰ هزارتومان پرداخت کند و خارج شود. میز او توسط کارکنان در لحظه‌ی ۱۹:۰۷:۰۹ آماده سرویس‌دهی می‌شود.
در لحظه ۱۹:۰۶:۱۸، میز شماره ۱ در حال تمیز شدن است.
در لحظه ۱۹:۰۷:۱۸، میز شماره ۱ در حال غذا خوردن است.
مجموع درآمد ۱۱۰ هزار تومان پرداخت شده و ۹۰ هزارتومان قرار است پرداخت شود. ۱ سفارش مشغول خوردن و ۲ سفارش کارشان تمام شده است و روی یک میز مشغول غذا خوردن هستند.