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

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

محصولاتی که مجید قصد کاشت آن‌ها را دارد، سه نوع هستند: درختی(مثل گردو)، بوته‌ای(مثل تمشک)، ریشه‌ای(مثل هویج)

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

ابتدا تمام زمین‌های کشت عاری از هر گونه گیاه هستند. هر گیاه یک نرخ رشد(در واحد کیلوگرم) مثل $s$ دارد و هر گاه در یک زمینِ کشت، گیاهی کاشته شود، از همان روز به مدّت ۵ روز، روزانه $s$ کیلوگرم از محصولات آن گیاه، به انبار مزرعه اضافه خواهد شد.

علاوه بر موارد گفته شده، در فروشگاه محصولات کشاورزی چند نوع کود وجود دارد. هر کود یک ضریب افزایندگی و یک میزان ماندگاری دارد. اگر کودی با ضریب افزایندگی $t$ و میزان ماندگاری $d$ روز به یکی از زمین‌های کشاورزی اضافه کنیم، از آن روز به مدّت $d$ روز، هر گیاهی که در آن زمین در حال ثمردهی باشد $t$ برابر ثمر خواهد داد. مثلا اگر گیاهی با نرخ رشد ۵ در آن زمین کاشته شده باشد و ما در سومین روزی که از کشت گیاه می‌گذرد به آن کودی با ضریب افزایندگی ۶ بدهیم، در آن روز و دو روز پس از آن گیاه ۳۰ کیلوگرم بار خواهد داد و باقی مانده عمرش را مثل قبل سپری خواهد کرد.

لازم به ذکر است که در صورتی که در یک زمین چند نوع کود وجود داشته باشند، ضریب افزایندگی در آن زمین به اندازه‌ی مجموع ضریب افزایندگی آن کودها خواهد بود. مثلا اگر در روز اول کودی با ضریب افزایندگی ۴ و میزان ماندگاری ۴ روز به زمین اضافه کنیم، در روز دوم کودی با ضریب افزایندگی ۲ و میزان ماندگاری ۲ روز به زمین اضافه کنیم، در روز اول و چهارم گیاهان داخل زمین ۴ برابر و در روز دوم و سوم نیز ۶ برابر ثمر خواهند داد.

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

مجید نزد هر مشتری مقداری آب‌رو دارد. هر بار که درخواست یک مشتری رد شود، آب‌روی مجید نزد آن مشتری یک واحد کم می‌شود، در غیر این صورت نیز یک واحد افزوده می‌شود. وقتی مشتری‌ای که آب‌روی مجید نزد آن $e$ است، از مجید محصولی با قیمت پایه $p$ می‌خرد، قیمت آن گیاه برای آن مشتری $p + e$ سکه بر کیلوگرم خواهد بود. دقّت کنید قیمت تمام شده‌ی یک محصول از صفر نمی‌تواند کم‌تر باشد و آب‌رویی که مجید نزد هر مشتری دارد در ابتدا صفر است.

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

ورودی

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

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

سپس $m$ تعداد گیاهان داده می‌شود.

در خط $i$ام از هر یک از $m$ خط بعد مشخصات گیاه $i$ام می‌آید. به ازای هر گیاه، ابتدا نام آن و سپس نوع آن داده می‌شود. نوع هر گیاه یک کلمه برابر یکی از سه کلمه‌ی risheh و derakht و buteh است. بعد از یک فاصله قیمت پایه‌ی آن گیاه و بعد از یک فاصله‌ی دیگر نیز ضریب رشد آن گیاه داده می‌شود.

سپس $k$ تعداد کودها داده می‌شود.

در خط $i$ام از هر یک از $k$ خط بعد، مشخصات کود $i$ام می‌آید. ابتدا نوع آن کود(یک کلمه)، سپس ضریب افزایندگی و سپس میزان ماندگاری آن کود داده می‌شوند.

در خط بعد عدد $d$ داده می‌شود که برابر تعداد روزها است. در ادامه $d$ دسته از دستورها و پرسش‌ها داده می‌شود. دسته‌ی $i$ام پرسش‌ها و دستورهایی است که در روز $i$ام مجید به شما می‌دهد.

در هر دسته، ابتدا عددی مثل $q_1$تعداد دستورها داده می‌شود.

در هر یک $q_1$ خط بعدی، دستوراتی از انواع زیر داده می‌شود:

bekar zamin_id giyah_name

این دستور به این معنی است که در زمین شماره zamin_id گیاهی به اسم giyah_name بکارید. در صورتی که در این روز گیاهی در آن زمین باشد که عمرش هنوز تمام نشده باشد، این دستور را نادیده می‌گیریم.

kooddehi zamin_id kood_name

به این معنی است که به زمین zamin_id یک واحد از کود kood_name را اضافه کنیم.

koodgiri kood_name value

به این معنی است که value واحد از کود نوع kood_name به دست ما رسیده است. این مقدار را در انبار ذخیره می‌کنیم!

چنان چه هر یک از عملیات بالا با موفقیت انجام شد باید به ازای آن دستور عبارت done را چاپ کنید. در غیر این صورت باید عبارت failed را چاپ کنید.

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

moshtari giyah_name value

به این معنی است که مشتری‌ای به اسم moshtari درخواست داده است به او value کیلوگرم از محصول giyah_name بفروشیم. اگر قادر به انجام این کار بودیم، تعداد سکّه‌ای که از مشتری دریافت می‌شود را چاپ کنید. در غیر این صورت -1 چاپ کنید.

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

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

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

در ضمن تمام اعداد ورودی حداکثر برابر ۱۰ هستند و تمام کلمات ورودی فقط از حروف کوچک الفبای انگلیسی تشکیل شده‌اند.

خروجی

به ازای هر پرسش در هر خط جواب آن پرسش را چاپ کنید.

پس از پرسش‌های هر روز نیز در یک خط نام (حداکثر) ۵ پرسودترین مشتری را چاپ کنید. (به ترتیب از بیشترین خرید به کمترین خرید)

مثال

ورودی نمونه ۱

1
1 1 1
1
havij risheh 10 10
0
1
1
bekar 1 havij
1
havijman havij 9

خروجی نمونه ۱

done
90
havijman

ورودی نمونه ۲

7
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
3
havij risheh 10 10
gerdoo derakht 5 5
talebi buteh 2 1
2
koodone 3 2
koodtwo 3 4
6
10
bekar 1 havij
bekar 2 havij
bekar 3 havij
kooddehi 2 koodone
koodgiri koodone 3
koodgiri koodtwo 2
kooddehi 1 koodone
kooddehi 1 koodtwo
bekar 4 gerdoo
bekar 6 talebi
0
0
10
havijkhar havij 8
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 9
havijkhar havij 1
akbar talebi 2
akbar havij 5
0
2
rostam gerdoo 10
rostam gerdoo 5
1
kooddehi 4 koodone
1
mohsen talebi 5
0
1
akbar talebi 1
0
10
akbar talebi 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10
havijkhar havij 10

خروجی نمونه ۲

done
failed
done
failed
done
done
done
done
done
done
80
110
120
130
140
150
144
17
4
55
havijkhar akbar
50
30
havijkhar rostam akbar
done
-1
havijkhar rostam akbar mohsen
4
havijkhar rostam akbar mohsen
-1
180
190
200
210
220
230
240
250
260
havijkhar rostam akbar mohsen