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

اجاره اتوبوس در هر روز صرفنظر از آنکه چند نفر سوار اتوبوس شوند $p$ تومان است. طبق قانونی که مورد پذیرش همه است هر روز یک نفر از کسانی که در اتوبوس حاضر است کرایه را پرداخت می‌کند. نام شخص پرداخت کننده نیز روزانه منتشر می‌شود.

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

فرض کنید $L_1$, $L_2$, $\dots$ لیست کارمندان از روز اول تا روز $d$ام باشد و فرض کنید $n_i$ طول لیست $L_i$ باشد. اگر شخص $A$ از سرویس اتوبوس در روزهای $t_1, t_2,\dots, t_k$ استفاده کند سهم واقعی او از کرایه برابر $p_A = p * (1/n_{t_1} + 1/n_{t_2} + \cdots + 1/n_{t_k})$ تومان خواهد شد. اگر $A$ مجبور به پرداخت کرایه در $r$ روز شده باشد او باید $Q_A=r\times p$ تومان پرداخت کند که $E_A=Q_A-p_A$ تومان بیش از سهم واقعی‌اش است. میزان بی عدالتی یک انتصاب را برابر ماکزیمم $E_A$ بین همه‌ی کارمندان متقاضی تعریف می‌کنیم. به انتصابی که میزان بی‌عدالتی آن کمینه باشد انتصاب عادلانه می‌گوییم.

ورودی شامل چند سناریو است. برای هر سناریو، خط اول شامل سه عدد صحیح مثبت $n$، $d$ و $p$ ($1 \leq n \leq 500, 1 \leq d \leq 500, 1 \leq p \leq 10^9$) است که $n$، $d$ و $p$ به ترتیب تعداد کارمندان، تعداد روزها و کرایه اتوبوس برای هر روز می باشند. اطلاعات مربوط به هر روز در $d$ خط بعد (یک خط برای هر روز) خواهد آمد. هر خط با تعداد کارمندانی که در آن روز از سرویس اتوبوس استفاده خواهند کرد شروع می‌شود. به دنبال آن آی‌دی کارمندان که اعدادی در بازه $[1,n]$ هستند می‌آید. برای سادگی در محاسبات، عدد $p$ به گونه‌ای انتخاب شده که سهم هر شخص در هر روز عدد صحیح باشد. ورودی با 0 0 0 خاتمه می‌یابد که نیازی به پردازش آن نیست.

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

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

• سوال بعد
• سوال قبل