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

• در سطر اول ورودی سه عدد $n$، تعداد آسان‌برها و سپس $m$، تعداد آدم‌های داخل ساختمان و نهایتاً $k$، گنجایش آسان‌برها آمده است.
• در سطر بعدی $m$ عدد آمده است که عدد $i$اُم این سطر طبقه‌ای را مشخص می‌کند که فرد $i$اُم در آن قرار دارد.
• در سطر بعدی $n$ عدد آمده است که عدد $i$اُم این سطر طبقه‌ی ابتدایی آسان‌بر $i$اُم را مشخص می‌کند.
• نهایتاً در سطر چهارم $n$ عدد $0$ یا $1$ آمده است که اگر عدد $i$اُم $0$ باشد یعنی آسان‌بر $i$اُم به سمت پایین حرکت می‌کند و اگر $1$ باشد، یعنی آسان‌بر $i$ام به سمت بالا حرکت می‌کند.
• $1 \leq n, m, k \leq 100,000$.

• در سطر اول خروجی، بیش‌ترین تعداد آدمی را که می‌توان نجات داد، بنویسید.
• در سطر بعدی $m$ عدد بنویسید که عدد $i$اُم مشخص می‌کند آدم $i$اُم با چه آسان‌بری (شماره آسان‌برها از $1$ تا $n$ هستند) باید فرار کند. اگر آدم $i$اُم موفق به فرار نشده بود عدد $0$ را برای آن نفر بنویسید.

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